Difference Between Ones and Zeros in Row and Column

Difference Between Ones and Zeros in Row and Column - Problem

You are given a 0-indexed m x n binary matrix grid.

A 0-indexed m x n difference matrix diff is created with the following procedure:

Let the number of ones in the i^th row be onesRow_i.
Let the number of ones in the j^th column be onesCol_j.
Let the number of zeros in the i^th row be zerosRow_i.
Let the number of zeros in the j^th column be zerosCol_j.
diff[i][j] = onesRow_i + onesCol_j - zerosRow_i - zerosCol_j

Return the difference matrix diff.

Input & Output

Example 1 — Basic 2x2 Matrix

$ Input: grid = [[0,1,1],[1,0,1],[0,0,1]]

› Output: [[0,0,4],[0,0,4],[-2,-2,2]]

💡 Note: For cell (0,0): Row 0 has 2 ones and 1 zero, Column 0 has 1 one and 2 zeros. Formula: 2+1-1-2 = 0

Example 2 — Simple 2x2

$ Input: grid = [[1,1,1],[1,1,1]]

› Output: [[5,5,5],[5,5,5]]

💡 Note: All ones matrix: Each row has 3 ones, each column has 2 ones. Formula: 3+2-0-0 = 5 for every cell

Example 3 — All Zeros

$ Input: grid = [[0,0],[0,0]]

› Output: [[-4,-4],[-4,-4]]

💡 Note: All zeros: Each row has 0 ones and 2 zeros, each column has 0 ones and 2 zeros. Formula: 0+0-2-2 = -4

Constraints

m == grid.length
n == grid[i].length
1 ≤ m, n ≤ 10⁵
1 ≤ m * n ≤ 10⁵
grid[i][j] is either 0 or 1

Visualization

Tap to expand

Understanding the Visualization

Input Matrix

Binary matrix with 0s and 1s

Count Statistics

Count ones/zeros per row and column

Apply Formula

Calculate onesRow + onesCol - zerosRow - zerosCol

Key Takeaway

🎯 Key Insight: Precompute row/column statistics once, then apply formula to each cell

Asked in

M Microsoft 15 a Amazon 12

The key insight is to precompute row and column statistics to avoid redundant counting. The optimal approach first counts ones in each row and column, then uses these precomputed values to calculate the difference formula for each cell. Time: O(mn), Space: O(m + n)

Common Approaches

Approach	Time	Space	Notes
✓ Precompute Row/Column Stats	O(mn)	O(m + n)	Pre-calculate all row and column statistics, then fill result matrix
Brute Force	O(m²n + mn²)	O(1)	For each cell, count ones and zeros in its row and column

Precompute Row/Column Stats — Algorithm Steps

Step 1: Count ones in each row (zeros = n - ones)
Step 2: Count ones in each column (zeros = m - ones)
Step 3: For each cell, use precomputed values in formula
Step 4: Return the difference matrix

Visualization

Tap to expand

Step-by-Step Walkthrough

Count Rows

Calculate ones in each row

Count Columns

Calculate ones in each column

Use Precomputed

Apply formula using stored values

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int** solution(int** grid, int m, int n, int* returnSize, int** returnColumnSizes) {
    *returnSize = m;
    *returnColumnSizes = (int*)malloc(m * sizeof(int));
    
    // Precompute ones in each row
    int* rowOnes = (int*)calloc(m, sizeof(int));
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            rowOnes[i] += grid[i][j];
        }
    }
    
    // Precompute ones in each column
    int* colOnes = (int*)calloc(n, sizeof(int));
    for (int j = 0; j < n; j++) {
        for (int i = 0; i < m; i++) {
            colOnes[j] += grid[i][j];
        }
    }
    
    // Build result matrix
    int** diff = (int**)malloc(m * sizeof(int*));
    for (int i = 0; i < m; i++) {
        (*returnColumnSizes)[i] = n;
        diff[i] = (int*)malloc(n * sizeof(int));
        
        for (int j = 0; j < n; j++) {
            int onesRow = rowOnes[i];
            int zerosRow = n - onesRow;
            int onesCol = colOnes[j];
            int zerosCol = m - onesCol;
            diff[i][j] = onesRow + onesCol - zerosRow - zerosCol;
        }
    }
    
    free(rowOnes);
    free(colOnes);
    return diff;
}

int main() {
    int m = 2, n = 2;
    int** grid = (int**)malloc(m * sizeof(int*));
    grid[0] = (int*)malloc(n * sizeof(int));
    grid[1] = (int*)malloc(n * sizeof(int));
    grid[0][0] = 0; grid[0][1] = 1;
    grid[1][0] = 1; grid[1][1] = 1;
    
    int returnSize, *returnColumnSizes;
    int** result = solution(grid, m, n, &returnSize, &returnColumnSizes);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("[");
        for (int j = 0; j < returnColumnSizes[i]; j++) {
            printf("%d", result[i][j]);
            if (j < returnColumnSizes[i] - 1) printf(",");
        }
        printf("]");
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(mn)

Single pass to count (mn) + single pass to fill result (mn) = O(mn)

✓ Linear Growth

Space Complexity

O(m + n)

Arrays to store row counts (m elements) and column counts (n elements)

⚡ Linearithmic Space

23.4K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Precompute Row/Column Stats — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler