Subramanya's Digital Garden

Recent Notes

861. Score After Flipping Matrix

2 min read

links: Algorithms MOC

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).

Approach

  1. One thing from additions is the left most is the most significant, so toggling all 0’s in the left most row to 1 will always increase the total sum
  2. For rest of the columns, if a column has more 0’s than 1’s those can be toggled to derive maximum number

Solution

/**
 * @param {number[][]} grid
 * @return {number}
 */
var matrixScore = function (grid) {
  // Step 1: flip the first element of each row to 1
  flipRowsStartingWithZero(grid);
  // Step 2: count the number of 0s in each column
  // if number of 0s is more than number of 1s, flip the column
  flipCols(grid);
  return binaryToDecimalSum(grid);
};
 
function flipRowsStartingWithZero(grid) {
  for (let i = 0; i < grid.length; i++) {
    let rowLength = grid[i].length;
    if (grid[i][0] === 0) {
      for (let j = 0; j < rowLength; j++) {
        flipVal(grid, i, j);
      }
    }
  }
}
 
function countZerosInColumn(grid, j) {
  let count = 0;
  for (let i = 0; i < grid.length; i++) {
    if (grid[i][j] === 0) {
      count++;
    }
  }
  return count;
}
 
function flipCols(grid) {
  for (let j = 0; j < grid[0].length; j++) {
    const zeros = countZerosInColumn(grid, j);
    for (let i = 0; i < grid.length; i++) {
      if (zeros > grid.length / 2) {
        flipVal(grid, i, j);
      }
    }
  }
}
 
function flipVal(grid, m, n) {
  let val = grid[m][n];
  grid[m][n] = Math.abs(val - 1);
}
 
function binaryToDecimalSum(grid) {
  return grid.reduce((acc, row) => {
    return acc + parseInt(row.join(""), 2);
  }, 0)
}

tags: array greedy-algo bit-manipulation matrix

source:

Graph View