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.
1public class Solution {
2 public int MatrixScore(int[][] grid) {
3 int m = grid.Length, n = grid[0].Length;
4 int score = 0;
5
6 for (int i = 0; i < m; ++i) {
7 if (grid[i][0] == 0) {
8 for (int j = 0; j < n; ++j) {
9 grid[i][j] ^= 1;
10 }
11 }
12 }
13
14 for (int j = 0; j < n; ++j) {
15 int colCount = 0;
16 for (int i = 0; i < m; ++i) {
17 if (grid[i][j] == 1) {
18 colCount++;
19 }
20 }
21 colCount = Math.Max(colCount, m - colCount);
22 score += colCount * (1 << (n - j - 1));
23 }
24
25 return score;
26 }
27}The C# implementation ensures the highest binary score by flipping rows to start with 1 and maximizing the number of 1s in each column after that.
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
Java's solution leans on using column information where it attempts to match the leading bit in delivering 1s across grid lines.