There is a nuance, for the leftmost column we could either flip rows to make it all 1s, or we could flip rows to make it all 0s and then flip the first column to make it all 1s. Now the question is whether the two lead to different answers? The answer is no but this kind of elucidates that why the fact that greedy approach is working is not trivial. How do you know you get the global optimum solution rather than a local optimum one? The answer is that there is only one type of nuance and that is exactly what I mentioned above. Another question, what if we remove the fact that rows represent binary numbers and just simply want to maximize the number of 1s? I have no idea how to do this one.
I hate it when I get so close to the answer but miss some small step🤦♂ Thanks for making these videos again, it really helps to hear someone speak and go over the problem
why are we not considering the case where we flip the most significant bit column wise then the we don't have to check the most significant value while calculating the number of Zeros/ones for other columns
I clicked the logic at 5:56 then I paused the video and wrote code to implement the logic. And it was shocking that I perfectly wrote the correct code with 100% beats and readability. And it is recommended to all watchers that don't watch any solution video complete. You should stop watching when you click the logic and try to implement code yourself.
I didn't get the intuition at first, but as soon as you said first column check for 0, to flip row, I understood the problem. Anyways, here's my code - class Solution: def matrixScore(self, grid: List[List[int]]) -> int: ROWS, COLS = len(grid), len(grid[0]) res = (2 ** (COLS - 1)) * ROWS for r in range(ROWS): if grid[r][0] == 0: for c in range(COLS): if grid[r][c] == 0: grid[r][c] = 1 else: grid[r][c] = 0 for c in range(1, COLS): count1 = 0 for r in range(ROWS): if grid[r][c] == 1: count1 += 1 if count1 > (ROWS // 2): res += count1 * (2 ** (COLS - c - 1)) else: res += (ROWS - count1) * (2 ** (COLS - c - 1)) return res
There is a nuance, for the leftmost column we could either flip rows to make it all 1s, or we could flip rows to make it all 0s and then flip the first column to make it all 1s. Now the question is whether the two lead to different answers? The answer is no but this kind of elucidates that why the fact that greedy approach is working is not trivial. How do you know you get the global optimum solution rather than a local optimum one? The answer is that there is only one type of nuance and that is exactly what I mentioned above.
Another question, what if we remove the fact that rows represent binary numbers and just simply want to maximize the number of 1s? I have no idea how to do this one.
I hate it when I get so close to the answer but miss some small step🤦♂ Thanks for making these videos again, it really helps to hear someone speak and go over the problem
I gotta say your ability to explain your thought process here was really good !
Thank you so much again. Great explanation as always.
why are we not considering the case where we flip the most significant bit column wise then the we don't have to check the most significant value while calculating the number of Zeros/ones for other columns
I clicked the logic at 5:56 then I paused the video and wrote code to implement the logic. And it was shocking that I perfectly wrote the correct code with 100% beats and readability. And it is recommended to all watchers that don't watch any solution video complete. You should stop watching when you click the logic and try to implement code yourself.
We can use xor for line 9-10 like: cnt += 1^grid[r][0]^grid[r][c]
thank you
"Thank you, it was helpful."
thanks for the awesome explanation!
Thank you for the solution
yo neet, use a 2^n lookup table and reverse it. That will make the index consistent instead of COL -1 - m or whatever
Great explanation🙏
why flip rows first not column first?
Thank you sir
Thanks man❤
The NEET Streak Saver 🔥
Nice🎉🎉
2055. Plates Between Candles... Next Please..
🙏🙏 for method 2
I didn't get the intuition at first, but as soon as you said first column check for 0, to flip row, I understood the problem. Anyways, here's my code -
class Solution:
def matrixScore(self, grid: List[List[int]]) -> int:
ROWS, COLS = len(grid), len(grid[0])
res = (2 ** (COLS - 1)) * ROWS
for r in range(ROWS):
if grid[r][0] == 0:
for c in range(COLS):
if grid[r][c] == 0:
grid[r][c] = 1
else:
grid[r][c] = 0
for c in range(1, COLS):
count1 = 0
for r in range(ROWS):
if grid[r][c] == 1:
count1 += 1
if count1 > (ROWS // 2):
res += count1 * (2 ** (COLS - c - 1))
else:
res += (ROWS - count1) * (2 ** (COLS - c - 1))
return res
This is basically the same way I thought of it, but then damn your use of ternary conditions makes some lines of code so much shorter!
you can use grid[r][c] ^ 1 one line to flip
@@sathishn6708 yeah that also works!
wow brain go brrr
Neet you are natu natu 😂
2055. Plates Between Candles... Next Please..