Problem

You are given an m x n binary matrix grid.

A move consists of choosing any row or column and toggling each value in that row or column (i.e., changing all 0’s to 1’s, and all 1’s to 0’s).

Every row of the matrix is interpreted as a binary number, and the score of the matrix is the sum of these numbers.

Return the highest possible score after making any number of moves (including zero moves).

Examples

Example 1:

$$ grid = \begin{bmatrix} 0 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 0 \end{bmatrix} \Longrightarrow \begin{bmatrix} \color{red} 1 & \color{red} 1 & \color{red} 0 & \color{red} 0 \\ 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 0 \end{bmatrix} \Longrightarrow $$

$$ \Longrightarrow \begin{bmatrix} 1 & 1 & \color{red} 1 & 0 \\ 1 & 0 & \color{red} 0 & 0 \\ 1 & 1 & \color{red} 1 & 0 \end{bmatrix} \Longrightarrow \begin{bmatrix} 1 & 1 & 1 & \color{red} 1 \\ 1 & 0 & 0 & \color{red} 1 \\ 1 & 1 & 1 & \color{red} 1 \end{bmatrix} $$

Input: grid = [ [0,0,1,1],[1,0,1,0],[1,1,0,0] ]
Output: 39
Explanation: 0b1111 + 0b1001 + 0b1111 = 15 + 9 + 15 = 39

Example 2:

Input: grid = [ [0] ]
Output: 1

Solution

This is a greedy problem. Please refer the video explanation here:

Method 1 - Multi-pass Solution

We know that the number is bigger when it has 1 in the most significant bit. For eg. 0b10 > 0b01.

Now, that we fixed the order in rows, we can flip as many 0s as possible in columns. So, we can do following:

  1. Flip all rows that start with zero;
  2. Flip all columns where the number of zeros is larger than the number of ones;

Code

Java
public int matrixScore(int[][] grid) {
	int m = grid.length, n = grid[0].length;
	
	for (int i = 0; i < m; i++) {
		if (grid[i][0] == 0) {
			flipRow(grid, i);
		}
	}
	// we start with j = 1, as j = 0 is 
	// taken care off in previous loop
	for (int j = 1; j < n; j++) {
		int colSum = 0;
		for (int i = 0; i < m; i++) {
			colSum += grid[i][j];
		}
			
		
		if (colSum * 2 < m) {
			flipCol(grid, j);		
		} 
		
	}
	
	int sum = 0;
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			sum += grid[i][j] * (1 << (n - 1 - j));
		}
	}

	return sum;
}

private void flipRow(int[][] grid, int r) {
	for (int j = 0; j < grid[r].length; j++) {
		grid[r][j] ^= 1;
	}
}

private void flipCol(int[][] grid, int c) {
	for (int i = 0; i < grid.length; i++) {
		grid[i][c] ^= 1;
	}
}

Complexity

  • ⏰ Time complexity: O(m*n)
  • 🧺 Space complexity: O(1)

Method 2 - Without Flipping

We can build on previous solution, and reduce the number of loops.

  • Initialise ans to (1<<(n-1))*m as all 0th columns are flipped to 1
  • Now traverse in each column and count number of 1s.
  • If a[i][j] == a[i][0] then we can say a[i][j] will be 1 why??
    • If a[i][0] == 0 then a[i][j] will flipped so it will become 1 if its initial value is 0 so it satisfies our condition
    • If a[i][0] == 1 then a[i][j] wont change so if it is 1 then it will be 1
  • We can use above to find 1s in every column and decide whether to flip that column if number of 1s is exceeding 0

Code

Java
public int matrixScore(int[][] grid) {
	int m = grid.length, n = grid[0].length;
	int ans = (1 << (n - 1)) * m;

	for (int j = 1; j < n; j++) {
		int colSum = 0;
		for (int i = 0; i < m; i++) {
			if (grid[i][j] == grid[i][0]) {
				colSum++;
			}
		}
		ans += (1 << (n - 1 - j)) * Math.max(colSum, m - colSum);
	}
	return ans;
}

Complexity

  • ⏰ Time complexity: O(m*n)
  • 🧺 Space complexity: O(1)