2482. Difference Between Ones and Zeros in Row and Column

MediumArrayMatrixSimulation
Leetcode Link

Problem Description

In this LeetCode problem, we're tasked with creating a difference matrix diff from a given binary matrix grid. The grid is a matrix composed of 0s and 1s with m rows and n columns, and both matrices are 0-indexed, which means that counting starts from the top-left cell (0,0).

To construct the diff matrix, we follow these steps for each cell at position (i, j):

  1. Calculate the total number of 1s (onesRow_i) in the ith row.
  2. Calculate the total number of 1s (onesCol_j) in the jth column.
  3. Calculate the total number of 0s (zerosRow_i) in the ith row.
  4. Calculate the total number of 0s (zerosCol_j) in the jth column.
  5. Set diff[i][j] to the sum of onesRow_i and onesCol_j subtracted by the sum of zerosRow_i and zerosCol_j.

Our goal is to return the diff matrix after performing these calculations for every cell in the grid.

Intuition

The intuition behind the solution is to use a straightforward approach by first calculating the sum of 1s in every row and column and storing them in two separate lists, rows and cols. This can be done by iterating over each element of the grid. If we encounter a 1, we increase the count for the respective row and column.

Once we have the sums of 1s for all rows and columns, we can calculate the difference matrix diff. For each cell in diff[i][j], we want to add the number of 1s in the ith row and jth column, and then subtract the number of 0s in the ith row and jth column.

However, we can cleverly calculate the number of 0s by subtracting the number of 1s from the total number of elements in the row or column because the row sum of ones and zeros will always equal the total number of elements in that row or column.

For example, to get the number of 0s in the ith row, we subtract the number of 1s in that row from the total number of columns n (because each row has n elements), which gives us zerosRow_i = n - onesRow_i. Similarly, we get zerosCol_j = m - onesCol_j.

The final diff matrix value at diff[i][j] is then computed as onesRow_i + onesCol_j - zerosRow_i - zerosCol_j, which simplifies to r + c - (n - r) - (m - c) when plugging in the sums and the number of 0s. This computation is performed for all cells (i, j) in the grid to obtain the complete diff matrix.

Solution Approach

The implementation involves two main parts: first, computing the sum of 1s for each row and column; second, using these sums to calculate the diff matrix.

Let's break down the implementation step by step:

  1. Initialize two lists rows and cols with length m and n, respectively, filled with zeros. These lists will keep track of the sum of 1s in each row and column. Initialize them with zeros as we haven't started counting yet.

  2. Iterate over each cell in grid using nested loops. For each cell (i, j), if the cell value is 1 (v in the code), increment rows[i] and cols[j] by 1. This loop runs through every element, ensuring that rows and cols accurately represent the number of 1s in their respective rows and columns.

  3. After completing the sum of 1s, we initialize the diff matrix with zeros, creating an m by n matrix using list comprehension.

  4. Now we iterate over each cell in the diff matrix. For every pair (i, j), we calculate the value of diff[i][j] using the sums obtained previously. As derived before, the difference r + c - (n - r) - (m - c) simplifies to 2 * (r + c) - m - n. This is because subtracting the zeros is the same as subtracting m or n and then adding back the number of ones in row r and column c.

  5. The previous calculation is applied to all elements in the diff matrix by iterating through the ranges of m for rows and n for columns. This modifies the diff matrix to contain the correct difference values per the problem's definition.

In terms of algorithms and patterns, the solution uses a simple brute-force approach which runs in O(m*n) time because it requires iterating over all elements of the initial matrix to compute the sums, and then once more to compute the diff matrix.

The data structures are simple lists for tracking the sums of ones in rows and columns, and a 2D list for the diff matrix. No additional complex data structures or algorithms are needed, making the implementation both straightforward and efficient for the problem at hand.

Example Walkthrough

Let's consider a small example to illustrate the solution approach with a binary grid of size m x n where m = 2 and n = 3:

1grid = [
2  [1, 0, 1],
3  [0, 1, 0]
4]

We are expected to create the diff matrix following the steps described in the content. Here's the step-by-step breakdown:

  1. Initialize two lists rows and cols with m and n zeros respectively, where m is the number of rows and n is the number of columns:

    rows = [0, 0] (for 2 rows)

    cols = [0, 0, 0] (for 3 columns)

  2. Loop over each cell in grid. If we find a 1, increase the respective count in rows and cols:

    • For cell (0, 0), grid[0][0] = 1, increment rows[0] and cols[0]: rows = [1, 0], cols = [1, 0, 0]
    • For cell (0, 1), grid[0][1] = 0, no increments.
    • For cell (0, 2), grid[0][2] = 1, increment rows[0] and cols[2]: rows = [2, 0], cols = [1, 0, 1]
    • For cell (1, 0), grid[1][0] = 0, no increments.
    • For cell (1, 1), grid[1][1] = 1, increment rows[1] and cols[1]: rows = [2, 1], cols = [1, 1, 1]
    • For cell (1, 2), grid[1][2] = 0, no increments.
  3. Now that we have the sums of 1s in each row and column, we can initialize the diff matrix filled with zeros:

    1diff = [
    2  [0, 0, 0],
    3  [0, 0, 0]
    4]
  4. Next, iterate over each cell (i, j) in the diff matrix to calculate its value:

    • For cell (0, 0), diff[0][0] = 2 * (rows[0] + cols[0]) - m - n = 2 * (2 + 1) - 2 - 3 = 4
    • For cell (0, 1), diff[0][1] = 2 * (rows[0] + cols[1]) - m - n = 2 * (2 + 1) - 2 - 3 = 4
    • For cell (0, 2), diff[0][2] = 2 * (rows[0] + cols[2]) - m - n = 2 * (2 + 1) - 2 - 3 = 4
    • For cell (1, 0), diff[1][0] = 2 * (rows[1] + cols[0]) - m - n = 2 * (1 + 1) - 2 - 3 = 0
    • For cell (1, 1), diff[1][1] = 2 * (rows[1] + cols[1]) - m - n = 2 * (1 + 1) - 2 - 3 = 0
    • For cell (1, 2), diff[1][2] = 2 * (rows[1] + cols[2]) - m - n = 2 * (1 + 1) - 2 - 3 = 0

The diff matrix after setting the values is:

1diff = [
2  [4, 4, 4],
3  [0, 0, 0]
4]

This diff matrix represents the sum of 1s in each row and column, minus the sum of 0s for each respective cell in grid.

Python Solution

1class Solution:
2    def onesMinusZeros(self, grid: List[List[int]]) -> List[List[int]]:
3        # Determine the number of rows (m) and columns (n) in the grid
4        num_rows, num_cols = len(grid), len(grid[0])
5      
6        # Initialize lists to store the sum of '1's in each row and column
7        sum_rows = [0] * num_rows
8        sum_cols = [0] * num_cols
9      
10        # Calculate the sum of '1's for each row and column
11        for i in range(num_rows):
12            for j in range(num_cols):
13                sum_rows[i] += grid[i][j]  # Sum '1's for row i
14                sum_cols[j] += grid[i][j]  # Sum '1's for column j
15      
16        # Initialize a list to store the resulting differences for each cell
17        differences = [[0] * num_cols for _ in range(num_rows)]
18      
19        # Compute the differences for each cell in the grid
20        for i in range(num_rows):
21            for j in range(num_cols):
22                # Calculate the difference by adding the sum of '1's in the current row and column
23                # and subtracting the sum of '0's (computed by subtracting the sum of '1's from the total count)
24                differences[i][j] = sum_rows[i] + sum_cols[j] - (num_cols - sum_rows[i]) - (num_rows - sum_cols[j])
25      
26        # Return the list containing the differences for each cell
27        return differences
28

Java Solution

1class Solution {
2    public int[][] onesMinusZeros(int[][] grid) {
3        // Get the dimensions of the grid
4        int rowCount = grid.length;
5        int colCount = grid[0].length;
6      
7        // Create arrays to hold the count of 1s in each row and column
8        int[] rowOnesCount = new int[rowCount];
9        int[] colOnesCount = new int[colCount];
10      
11        // Calculate the total number of 1s in each row and column
12        for (int i = 0; i < rowCount; ++i) {
13            for (int j = 0; j < colCount; ++j) {
14                int value = grid[i][j];
15                rowOnesCount[i] += value;
16                colOnesCount[j] += value;
17            }
18        }
19      
20        // Initialize a matrix to store the difference between ones and zeros for each cell
21        int[][] differences = new int[rowCount][colCount];
22      
23        // Calculate the difference for each cell and populate the differences matrix
24        for (int i = 0; i < rowCount; ++i) {
25            for (int j = 0; j < colCount; ++j) {
26                int onesTotal = rowOnesCount[i] + colOnesCount[j]; // Total number of 1s in the row i and column j
27                int zerosTotal = (colCount - rowOnesCount[i]) + (rowCount - colOnesCount[j]); // Total number of 0s in the row i and column j
28                differences[i][j] = onesTotal - zerosTotal;
29            }
30        }
31      
32        // Return the final matrix of differences
33        return differences;
34    }
35}
36

C++ Solution

1#include <vector>
2using namespace std;
3
4class Solution {
5public:
6    // This function takes a 2D grid of binary values and calculates the new grid
7    // such that each cell in the new grid will contain the number of 1s minus the
8    // number of 0s in its row and column in the original grid.
9    vector<vector<int>> onesMinusZeros(vector<vector<int>>& grid) {
10        // Dimensions of the original grid
11        int rowCount = grid.size();
12        int colCount = grid[0].size();
13      
14        // Vectors to store the sums of values in each row and column
15        vector<int> rowSums(rowCount, 0);
16        vector<int> colSums(colCount, 0);
17      
18        // Calculate the sums of 1s in each row and column
19        for (int i = 0; i < rowCount; ++i) {
20            for (int j = 0; j < colCount; ++j) {
21                int value = grid[i][j];
22                rowSums[i] += value;
23                colSums[j] += value;
24            }
25        }
26      
27        // Create a new 2D grid to store the differences
28        vector<vector<int>> differenceGrid(rowCount, vector<int>(colCount, 0));
29      
30        // Calculate the ones minus zeros difference for each cell
31        for (int i = 0; i < rowCount; ++i) {
32            for (int j = 0; j < colCount; ++j) {
33                // The difference is the sum of ones in the row and column
34                // minus the number of zeroes (which is rows/cols minus the sum of ones)
35                differenceGrid[i][j] = rowSums[i] + colSums[j] - (colCount - rowSums[i]) - (rowCount - colSums[j]);
36            }
37        }
38      
39        // Return the new grid with the calculated differences
40        return differenceGrid;
41    }
42};
43

Typescript Solution

1// Counts the number of 1's minus the number of 0's in each row and column for a 2D grid
2function onesMinusZeros(grid: number[][]): number[][] {
3    // Determine the number of rows and columns in the grid
4    const rowCount = grid.length;
5    const colCount = grid[0].length;
6
7    // Initialize arrays to keep the counts of 1's for each row and column
8    const rowOnesCount = new Array(rowCount).fill(0);
9    const colOnesCount = new Array(colCount).fill(0);
10
11    // First pass: Count the number of 1's in each row and column
12    for (let i = 0; i < rowCount; i++) {
13        for (let j = 0; j < colCount; j++) {
14            if (grid[i][j] === 1) {
15                rowOnesCount[i]++;
16                colOnesCount[j]++;
17            }
18        }
19    }
20
21    // Prepare the answer grid with the same dimensions as the input grid
22    const answerGrid = Array.from({ length: rowCount }, () => new Array(colCount).fill(0));
23
24    // Second pass: Calculate ones minus zeros for each cell
25    for (let i = 0; i < rowCount; i++) {
26        for (let j = 0; j < colCount; j++) {
27            // Sum the counts of 1's for the current row and column
28            let sumOnes = rowOnesCount[i] + colOnesCount[j];
29            // Count the zeros by subtracting the number of 1's from total row and column counts
30            let sumZeros = (rowCount - rowOnesCount[i]) + (colCount - colOnesCount[j]);
31            // Subtract the count of zeros from the number of ones and assign it to the answer grid
32            answerGrid[i][j] = sumOnes - sumZeros;
33        }
34    }
35
36    // Return the answer grid containing ones minus zeros for each cell
37    return answerGrid;
38}
39

Time and Space Complexity

Time Complexity

The given code consists of three distinct loops that iterate over the elements of the grid:

  1. The first two loops (nested) are executed to calculate the sum of the values in each row and column. These loops go through all the elements of the matrix once. Therefore, for a matrix of size m x n, the time complexity of this part is O(m * n).

  2. The third set of nested loops is used to calculate the diff matrix. They also iterate over every element in the matrix, leading to a time complexity of O(m * n) for this part as well.

Adding both parts together doesn't change the overall time complexity since they are sequential, not nested within each other. Hence, the overall time complexity of the algorithm is O(m * n).

Space Complexity

Analyzing the space complexity:

  1. Two additional arrays rows and cols are created, which have lengths m and n, respectively. This gives a space complexity of O(m + n).

  2. A new matrix diff of size m x n is allocated to store the results. This contributes O(m * n) to the space complexity.

  3. The space taken up by variables m, n, i, j, r, c, and v is constant, O(1).

Therefore, the total space complexity of the algorithm is O(m * n + m + n). Since m * n dominates for large matrices, the overall space complexity can be simplified to O(m * n).


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫