Skip to main content

Matrix

Difference Between Ones and Zeros in Row and Column Solution In C++/Python/java/JS

Problem Description

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 ith row be onesRow_i.
Let the number of ones in the jth column be onesCol_j.
Let the number of zeros in the ith row be zerosRow_i.
Let the number of zeros in the jth column be zerosCol_j.

diff[i][j] = onesRow_i + onesCol_j - zerosRow_i - zerosCol_j.

Return the difference matrix diff.

Examples

Input: grid = [[0,1,1],[1,0,1],[0,0,1]]
Output: [[0,0,4],[0,0,4],[-2,-2,2]]
Explanation:

Input: grid = [[1,1,1],[1,1,1]]
Output: [[5,5,5],[5,5,5]]
Explanation:

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

Brute Force approach

When reading the problem, it tells us to calculate a new matrix (the "difference matrix") based on the given grid.

To do this, for each cell in the grid, we need to count how many 1's and 0's are in its row and column.

Using these counts, we calculate the value of that cell in the new matrix with the formula: (1's in the row + 1's in the column) - (0's in the row + 0's in the column).

We repeat this for every cell in the grid in order to find the difference matrix.

Let's understand it with an example: grid = [[0,1,1],[1,0,1],[0,0,1]]

Steps to Write Code

Input Dimensions:

  • The number of rows (m) and columns (n) in the grid are determined to handle the input matrix.

Initialize the Result Matrix:

  • The diff matrix is created with the same dimensions as grid, initialized with zeros. This will store the final difference values.

Iterate Through Each Cell:

  • The function uses two nested loops to visit every cell (i, j) in the grid.

Count Ones and Zeros in Row and Column:

  • For each cell (i, j), two additional loops are used:
    • The first loop counts the number of 1s and 0s in the current row i.
    • The second loop counts the number of 1s and 0s in the current column j.

Apply the Formula:

  • The value for diff[i][j] is calculated using:
    diff[i][j]=(onesRow+onesCol)−(zerosRow+zerosCol)

Store the Result:

  • The computed value is stored in the corresponding cell of the diff matrix.

Return the Result:

  • After processing all cells, the diff matrix is returned as the final result.

Code for All Languages
C++ 
class Solution {
public:
    vector<vector<int>> onesMinusZeros(vector<vector<int>>& grid) {
        // Get the number of rows (m) and columns (n) in the grid
        int m = grid.size(); 
        int n = grid[0].size();

        // Initialize the difference matrix with the same dimensions as grid
        vector<vector<int>> diff(m, vector<int>(n, 0));

        // Iterate through each cell in the grid
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                // Variables to count the number of ones and zeros in the ith row and jth column
                int onesRow = 0, zerosRow = 0;
                int onesCol = 0, zerosCol = 0;

                // Calculate the number of ones and zeros in the ith row
                for (int k = 0; k < n; ++k) {
                    if (grid[i][k] == 1) {
                        ++onesRow;  // Increment ones count if cell value is 1
                    } else {
                        ++zerosRow; // Increment zeros count otherwise
                    }
                }

                // Calculate the number of ones and zeros in the jth column
                for (int k = 0; k < m; ++k) {
                    if (grid[k][j] == 1) {
                        ++onesCol;  // Increment ones count if cell value is 1
                    } else {
                        ++zerosCol; // Increment zeros count otherwise
                    }
                }

                // Compute the difference value for cell (i, j) using the given formula
                diff[i][j] = onesRow + onesCol - zerosRow - zerosCol;
            }
        }

        // Return the computed difference matrix
        return diff;
    }
};

Java 
class Solution {
    public int[][] onesMinusZeros(int[][] grid) {
        // Get the dimensions of the grid
        int m = grid.length;        // Number of rows
        int n = grid[0].length;     // Number of columns

        // Initialize the difference matrix with the same dimensions as the grid
        int[][] diff = new int[m][n];

        // Iterate through each cell in the grid
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                // Variables to count ones and zeros in the ith row and jth column
                int onesRow = 0, zerosRow = 0;
                int onesCol = 0, zerosCol = 0;

                // Calculate the number of ones and zeros in the ith row
                for (int k = 0; k < n; k++) {
                    if (grid[i][k] == 1) {
                        onesRow++; // Increment ones count if the value is 1
                    } else {
                        zerosRow++; // Increment zeros count otherwise
                    }
                }

                // Calculate the number of ones and zeros in the jth column
                for (int k = 0; k < m; k++) {
                    if (grid[k][j] == 1) {
                        onesCol++; // Increment ones count if the value is 1
                    } else {
                        zerosCol++; // Increment zeros count otherwise
                    }
                }

                // Calculate the difference value for cell (i, j)
                diff[i][j] = onesRow + onesCol - zerosRow - zerosCol;
            }
        }

        // Return the computed difference matrix
        return diff;
    }
}

Python 
class Solution(object):
    def onesMinusZeros(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: List[List[int]]
        """
        # Get the dimensions of the grid
        m = len(grid)       # Number of rows
        n = len(grid[0])    # Number of columns

        # Initialize the difference matrix with the same dimensions as grid
        diff = [[0] * n for _ in range(m)]

        # Iterate through each cell in the grid
        for i in range(m):
            for j in range(n):
                # Variables to count the number of ones and zeros in the ith row and jth column
                onesRow = zerosRow = onesCol = zerosCol = 0

                # Calculate the number of ones and zeros in the ith row
                for k in range(n):
                    if grid[i][k] == 1:
                        onesRow += 1  # Increment ones count
                    else:
                        zerosRow += 1  # Increment zeros count

                # Calculate the number of ones and zeros in the jth column
                for k in range(m):
                    if grid[k][j] == 1:
                        onesCol += 1  # Increment ones count
                    else:
                        zerosCol += 1  # Increment zeros count

                # Compute the difference value for cell (i, j)
                diff[i][j] = onesRow + onesCol - zerosRow - zerosCol

        # Return the computed difference matrix
        return diff

Javascript 
/**
 * @param {number[][]} grid
 * @return {number[][]}
 */
var onesMinusZeros = function(grid) {
    // Get the dimensions of the grid
    const m = grid.length;       // Number of rows
    const n = grid[0].length;    // Number of columns

    // Initialize the difference matrix with the same dimensions as the grid
    const diff = Array.from({ length: m }, () => Array(n).fill(0));

    // Iterate through each cell in the grid
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            // Variables to count ones and zeros in the ith row and jth column
            let onesRow = 0, zerosRow = 0;
            let onesCol = 0, zerosCol = 0;

            // Calculate the number of ones and zeros in the ith row
            for (let k = 0; k < n; k++) {
                if (grid[i][k] === 1) {
                    onesRow++;
                } else {
                    zerosRow++;
                }
            }

            // Calculate the number of ones and zeros in the jth column
            for (let k = 0; k < m; k++) {
                if (grid[k][j] === 1) {
                    onesCol++;
                } else {
                    zerosCol++;
                }
            }

            // Compute the difference value for cell (i, j)
            diff[i][j] = onesRow + onesCol - zerosRow - zerosCol;
        }
    }

    // Return the computed difference matrix
    return diff;
};

Time Complexity

Outer Loops:

  • The algorithm uses two nested loops to traverse each cell in the grid. The outer loop iterates over the rows (m rows), and the inner loop iterates over the columns (n columns).
  • Therefore, the total number of iterations for these loops is m * n.

Counting Operations for Each Cell:

  • Inside the inner loop, for each cell at position (i, j), the algorithm performs two counting operations:
    • Row Counting: It counts how many 1s and 0s are in the entire ith row. This takes O(n) time because it involves iterating over all columns in the row.
    • Column Counting: It counts how many 1s and 0s are in the entire jth column. This takes O(m) time because it involves iterating over all rows in the column.

Total Work for Each Cell:

  • For each cell (i, j), the total work done consists of:
    • O(n) for counting in the row.
    • O(m) for counting in the column.
  • Therefore, for each cell, the algorithm performs O(m + n) work.

Final Total Time Complexity:

  • Since there are m * n cells in the grid, and for each cell the work done is O(m + n),
    the total time complexity of the algorithm is: O(m×n×(m+n))

Space Complexity

Space complexity refers to the amount of memory or space the algorithm uses during its execution. In this problem, we need to consider the following aspects of space usage:

  1. Input Grid (grid):
    • The input grid is a 2D array with m rows and n columns. So, the space required for the grid is O(m * n) because it contains m * n elements.
  3. Difference Matrix (diff):
    • The algorithm creates a new matrix (diff) of the same size as the input grid to store the results. This matrix will also have m rows and n columns, so the space required for the diff matrix is O(m * n).
  5. Temporary Variables(Auxiliary Space):
    • The algorithm uses some additional variables to store intermediate results, such as the counts of 1s and 0s in the rows and columns. These variables are just simple integers and require constant space, i.e., O(1).

Total Space Complexity:

  • The space complexity is dominated by the storage requirements of the input grid and the difference matrix.
  • The grid takes O(m * n) space, and the difference matrix also takes O(m * n) space.

Therefore, the total space complexity of the algorithm is: O(m×n)

Will this run under the given constraints?

The constraints are not explicitly mentioned in the problem, but let's assume typical grid size constraints, such as:

  • m, n ≤ 1000

Time Complexity for Large Inputs:

  • If both m and n are at their maximum value (1000), the time complexity becomes: O(1000×1000×(1000+1000))=O(1000×1000×2000)=O(2×10⁹)
  • In practical terms, a time complexity of O(2×10⁹) is too large to run efficiently within a reasonable time limit for competitive programming or real-world applications, where time limits are usually in the order of 1 to 2 seconds.

Space Complexity for Large Inputs:

  • For m = 1000 and n = 1000, the space complexity becomes: O(1000×1000)=O(10⁶)
  • This is about 1 million elements, which is manageable in most systems, and should not pose a problem in terms of memory usage.

Optimize Approach

In the brute force solution, for each cell in the grid, we are counting the number of ones and zeros in the same row and column, which leads to unnecessary recomputations.

The optimization of the brute force approach focuses on reducing redundant calculations by pre-computing values that are repeatedly used.

The optimized approach uses precomputation to avoid repeatedly calculating the number of 1's and 0's for each cell in the grid. The first step is to precompute the number of 1's in each row and each column.
To do this, two arrays, onesRow and onesCol, are created. The onesRow array stores the count of 1's for each row, and the onesCol array stores the count of 1's for each column.

These arrays are populated by iterating over the grid once, which allows us to calculate the number of 1's for every row and column efficiently. Once we have these precomputed arrays, we can calculate the difference for each cell (i, j) using the formula:

diff[i][j]=(onesRow[i]+onesCol[j])−(n−onesRow[i])−(m−onesCol[j])

Where onesRow[i] gives the number of 1's in the i-th row, onesCol[j] gives the number of 1's in the j-th column, n is the total number of columns, and m is the total number of rows.
This formula computes the difference between the number of 1's and 0's for each cell by summing up the 1's in the row and column, then subtracting the number of 0's. With the precomputation, each cell's result can be computed in constant time, avoiding the need to count 1's and 0's for every individual cell repeatedly.

Let's understand it with an example: grid = [[0,1,1],[1,0,1],[0,0,1]]

Steps to write Code

Step 1: Initialize Variables:

  • Get the dimensions of the grid (number of rows m and columns n).
  • Initialize arrays to store counts of 1's in rows (onesRow) and columns (onesCol).

Step 2: Count 1's in Rows and Columns:

  • Loop through the grid to calculate the number of 1's in each row and column.

Step 3: Create Result Grid:

  • Initialize a new 2D grid diff to store the calculated differences.

Step 4: Calculate the Difference:

  • For each cell (i, j), calculate the difference between the number of 1's and 0's in its row and column using the formula.

Step 5: Return the Result:

  • Return the result grid diff containing the calculated differences.
Code for All Languages
C++ 
class Solution {
public:
    vector<vector<int>> onesMinusZeros(vector<vector<int>>& grid) {
        int m = grid.size(); // Get the number of rows
        int n = grid[0].size(); // Get the number of columns
        
        // Step 1: Initialize arrays to store count of 1's in each row and column
        vector<int> onesRow(m, 0); // Array for row counts
        vector<int> onesCol(n, 0); // Array for column counts
        
        // Step 2: Calculate the number of 1's in each row and each column
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                onesRow[i] += grid[i][j]; // Count 1's in row i
                onesCol[j] += grid[i][j]; // Count 1's in column j
            }
        }
        
        // Step 3: Initialize a result grid to store the differences
        vector<vector<int>> diff(m, vector<int>(n, 0)); // Initialize grid with 0's
        
        // Step 4: Calculate the difference for each cell
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                // Formula: (ones in row) + (ones in column) - (zeros in row) - (zeros in column)
                diff[i][j] = (onesRow[i] + onesCol[j]) - (n - onesRow[i]) - (m - onesCol[j]);
            }
        }
        
        // Step 5: Return the result grid
        return diff;
    }
};

Java 
class Solution {
    public int[][] onesMinusZeros(int[][] grid) {
        int m = grid.length; // Number of rows
        int n = grid[0].length; // Number of columns
        
        int[] onesRow = new int[m]; // Array to store count of 1's in each row
        int[] onesCol = new int[n]; // Array to store count of 1's in each column
        
        // Calculate the number of 1's in each row and column
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                onesRow[i] += grid[i][j];
                onesCol[j] += grid[i][j];
            }
        }
        
        int[][] diff = new int[m][n]; // Result grid to store the differences
        
        // Calculate the difference for each cell
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                diff[i][j] = (onesRow[i] + onesCol[j]) - (n - onesRow[i]) - (m - onesCol[j]);
            }
        }
        
        return diff;
    }
}

Python 
class Solution(object):
    def onesMinusZeros(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: List[List[int]]
        """
        m = len(grid)  # Number of rows
        n = len(grid[0])  # Number of columns
        
        onesRow = [0] * m  # List to store count of 1's in each row
        onesCol = [0] * n  # List to store count of 1's in each column
        
        # Calculate the number of 1's in each row and column
        for i in range(m):
            for j in range(n):
                onesRow[i] += grid[i][j]
                onesCol[j] += grid[i][j]
        
        diff = [[0] * n for _ in range(m)]  # Result grid to store the differences
        
        # Calculate the difference for each cell
        for i in range(m):
            for j in range(n):
                diff[i][j] = (onesRow[i] + onesCol[j]) - (n - onesRow[i]) - (m - onesCol[j])
        
        return diff

Javascript 
var onesMinusZeros = function(grid) {
    let m = grid.length;  // Number of rows
    let n = grid[0].length;  // Number of columns
    
    let onesRow = new Array(m).fill(0);  // Array to store count of 1's in each row
    let onesCol = new Array(n).fill(0);  // Array to store count of 1's in each column
    
    // Calculate the number of 1's in each row and column
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            onesRow[i] += grid[i][j];
            onesCol[j] += grid[i][j];
        }
    }
    
    let diff = Array.from({ length: m }, () => new Array(n).fill(0));  // Result grid to store the differences
    
    // Calculate the difference for each cell
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            diff[i][j] = (onesRow[i] + onesCol[j]) - (n - onesRow[i]) - (m - onesCol[j]);
        }
    }
    
    return diff;
};

Time Complexity

Initialization of Arrays:

  • We initialize two arrays: onesRow and onesCol. The size of onesRow is m (number of rows), and the size of onesCol is n (number of columns).
  • Initializing these arrays takes O(m) and O(n) time, respectively.

Filling onesRow and onesCol Arrays:

  • We loop through each cell in the grid to calculate the number of 1's in each row and each column.
  • For each cell (i, j) in the grid, we update onesRow[i] and onesCol[j] based on the value of the grid cell.
  • This involves two nested loops: the outer loop iterates over m rows, and the inner loop iterates over n columns. Thus, we are iterating over every cell in the grid once.
  • The time complexity for this step is O(m * n), where m is the number of rows and n is the number of columns in the grid.

Computing the Difference for Each Cell:

  • After we have populated onesRow and onesCol, we calculate the difference for each cell (i, j) using the precomputed values.
  • For each cell, the calculation involves accessing values in the onesRow and onesCol arrays and performing some arithmetic, which takes constant time O(1).
  • Since we have to calculate the difference for all m * n cells, this step also takes O(m * n) time.

Total Time Complexity:

  • Adding up the time complexities of all steps, we get: O(m+n)+O(m∗n)+O(m∗n)
    • The initialization takes O(m) and O(n), but this is dominated by the larger term O(m * n).
    • Thus, the total time complexity is O(m * n).

Space Complexity

1. Input Space:

This refers to the space used by the input data.

  • Input Data: The input to the function is the grid, which is a 2D array with dimensions m * n, where m is the number of rows and n is the number of columns.
  • Input Space Complexity: The input space is O(m * n) because the grid has m * n elements.

2. Auxiliary Space:

Auxiliary space is the extra space used by the algorithm to store variables and data structures that are not part of the input.

  • onesRow Array: This array stores the count of 1's for each row, with a size of m. Thus, it takes O(m) space.
  • onesCol Array: This array stores the count of 1's for each column, with a size of n. Thus, it takes O(n) space.
  • diff Array: This is the 2D array that stores the difference between the count of 1's and 0's for each cell. It has a size of m * n. Thus, it takes O(m * n) space.
  • Other Variables: The rest of the variables, such as m, n, i, j, and intermediate calculations, take constant space, i.e., O(1).

Total Space Complexity:

Now, let's calculate the total space complexity:

Input Space Complexity:

  • The input grid takes O(m * n) space.

Auxiliary Space Complexity:

  • The onesRow array takes O(m) space.
  • The onesCol array takes O(n) space.
  • The diff array takes O(m * n) space.
  • Other variables take O(1) space.

Thus, the Auxiliary Space Complexity is: O(m)+O(n)+O(m∗n)=O(m∗n)

The O(m * n) term dominates because the diff array is the largest data structure in terms of space.

Total Space Complexity:

To calculate the Total Space Complexity, we sum the Input Space Complexity and the Auxiliary Space Complexity:

Total Space Complexity=O(m∗n) (Input)+O(m∗n) (Auxiliary)=O(m∗n)

Learning Tip

Now we have successfully tackled this problem, let's try more matrix problems.

Rotate Image

You are given an n x n 2D matrix representing an image, rotate the image by 90 degrees (clockwise).

You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.

Reshape the Matrix

In MATLAB, there is a handy function called reshape which can reshape an m x n matrix into a new one with a different size r x c keeping its original data.

You are given an m x n matrix mat and two integers r and c representing the number of rows and the number of columns of the wanted reshaped matrix.

The reshaped matrix should be filled with all the elements of the original matrix in the same row-traversing order as they were.

If the reshape operation with given parameters is possible and legal, output the new reshaped matrix; Otherwise, output the original matrix.