Sponsored
Sponsored
To maximize the score, we should ensure that the leftmost bit (most significant bit) of each binary number (row) is 1. If the first bit of any row is 0, we can flip that entire row.
Once the leading bits are all 1, we maximize further by toggling columns where the count of 0s is more than 1s. This ensures that the binary numbers are as large as possible.
Time Complexity: O(m * n), where m is the number of rows and n is the number of columns in the grid. Space Complexity: O(1), using inplace modifications.
1class Solution:
2 def matrixScore(self, grid):
3 m, n = len(grid), len(grid[0])
4
5 for i in range(m):
6 if grid[i][0] == 0:
7 for j in range(n):
8 grid[i][j] ^= 1
9
10 score = 0
11 for j in range(n):
12 col_count = sum(grid[i][j] for i in range(m))
13 col_count = max(col_count, m - col_count)
14 score += col_count * (1 << (n - j - 1))
15
16 return score
17The Python solution uses a nested loop to first convert any row with a zero as its first column value into a row starting with one. Then, it optimizes each column to ensure maximum contribution to the score.
This approach differs slightly by treating the majority of 1s per column as more influential. Instead of flipping rows first, the solution primarily ensures maximal 1 presence per column, beginning with the columns themselves.
Time Complexity: O(m * n), as each element in the matrix grid is visited once. Space Complexity: O(1), operating in-place.
1
In Python, the algorithm immediately accounts for the most significant bit interactions and adjusts subsequent digits based on perception and binary values.