_861. Score After Flipping Matrix.md

861. Score After Flipping Matrix

All prompts are owned by LeetCode. To view the prompt, click the title link above.

Back to top

---

First completed : June 10, 2024

Last updated : July 01, 2024

---

Related Topics : Array, Greedy, Bit Manipulation, Matrix

Acceptance Rate : 80.3 %

---

Solutions

• m861 v2.c
• m861.c
• m861.py

C

m861 v2.c

// Optimized to not have the final loop for calculating the sum

void flipCol(int** grid, int targetCol, int numRows) {
    for (int i = 0; i < numRows; i++) {
        grid[i][targetCol] = (grid[i][targetCol] == 1) ? 0 : 1;
    }
}

void flipRow(int** grid, int targetRow, int numCols) {
    for (int i = 0; i < numCols; i++) {
        grid[targetRow][i] = (grid[targetRow][i] == 1) ? 0 : 1;
    }
}

int matrixScore(int** grid, int gridSize, int* gridColSize) {
    int rows = gridSize;
    int cols = *gridColSize;

    for (int row = 0; row < rows; row++) {
        if (!grid[row][0]) {
            flipRow(grid, row, cols);
        }
    }
    int runningSum = gridSize;

    for (int col = 1; col < cols; col++) {
        int count = 0;
        runningSum *= 2;
        for (int row = 0; row < rows; row++) {
            count += grid[row][col];
        }

        if (count < gridSize / 2 || (count == gridSize / 2 && gridSize % 2 != 0)) {
            runningSum += rows - count;
            flipCol(grid, col, rows);
        } else {
            runningSum += count;
        }
    }

    return runningSum;
}

m861.c

void flipCol(int** grid, int targetCol, int numRows) {
    for (int i = 0; i < numRows; i++) {
        grid[i][targetCol] = (grid[i][targetCol] == 1) ? 0 : 1;
    }
}

void flipRow(int** grid, int targetRow, int numCols) {
    for (int i = 0; i < numCols; i++) {
        grid[targetRow][i] = (grid[targetRow][i] == 1) ? 0 : 1;
    }
}

int matrixScore(int** grid, int gridSize, int* gridColSize) {
    int rows = gridSize;
    int cols = *gridColSize;

    for (int row = 0; row < rows; row++) {
        if (!grid[row][0]) {
            flipRow(grid, row, cols);
        }
    }

    for (int col = 1; col < cols; col++) {
        int count = 0;
        for (int row = 0; row < rows; row++) {
            count += grid[row][col];
        }
        if (count < gridSize / 2 || (count == gridSize / 2 && gridSize % 2 != 0)) {
            flipCol(grid, col, rows);
        }
    }


    // convert to integer
    int runningSum = 0;
    for (int row = 0; row < rows; row++) {
        int currentVal = 0;
        for (int col = 0; col < cols; col++) {
            currentVal *= 2;
            currentVal += grid[row][col];
        }
        runningSum += currentVal;
    }

    return runningSum;
    
}

Python

m861.py

class Solution:
    def matrixScore(self, grid: List[List[int]]) -> int:
        for i in range(len(grid)) :
            if grid[i][0] == 0 :
                self.flipRow(grid, i)
        
        for col in range(1, len(grid[0])) :
            colVal = sum(grid[x][col] for x in range(len(grid)))
            if colVal < len(grid) / 2 :
                self.flipCol(grid, col)
        
        # convert from binary
        runningSum = 0

        for row in grid :
            runningSum += int(''.join([str(x) for x in row]), 2)

        return runningSum


    def flipRow(self, grid: List[List[int]], x: int) -> None :
        ref = {0: 1, 1: 0}
        for i in range(len(grid[0])) :
            grid[x][i] = ref[grid[x][i]]

    def flipCol(self, grid: List[List[int]], x: int) -> None :
        ref = {0: 1, 1: 0}
        for i in range(len(grid)) :
            grid[i][x] = ref[grid[i][x]]