We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Difference Between Ones and Zeros in Row and Column

Number: 2606

Difficulty: Medium

Paid? No

Companies: Amazon

Problem Description

Given an m x n binary matrix grid, create a difference matrix diff where each cell diff[i][j] is defined as: onesRow[i] + onesCol[j] - zerosRow[i] - zerosCol[j] Here, onesRow[i] is the number of ones in the ith row, onesCol[j] is the number of ones in the jth column, zerosRow[i] is the number of zeros in the ith row, and zerosCol[j] is the number of zeros in the jth column.

Key Insights

  • Precompute the number of ones in each row and each column to avoid recomputation.
  • Compute the number of zeros for each row and column based on the total number of elements in that row/column.
  • Use these precomputed values to compute the diff matrix in a single pass.
  • The problem can be solved in O(m*n) time, which is efficient given the limit on total elements.

Space and Time Complexity

Time Complexity: O(m*n) where m is the number of rows and n is the number of columns.
Space Complexity: O(m + n) for the auxiliary arrays to store row and column counts (excluding the output matrix).

Solution

The approach leverages precomputation of the count of ones for each row and column. For each row i, calculate onesRow[i] by summing up the values. Similarly, for each column j, calculate onesCol[j] by iterating over every row’s jth element.
Since each row contains n elements and each column contains m elements, zerosRow[i] can be obtained as n - onesRow[i] and zerosCol[j] as m - onesCol[j].
Then iterate through each cell (i, j) in grid and compute:   diff[i][j] = onesRow[i] + onesCol[j] - zerosRow[i] - zerosCol[j].
Using this approach allows a single pass over the matrix to compute the desired value for each cell.

Code Solutions

# Python solution

def onesMinusZeros(grid):
    # Number of rows and columns
    m, n = len(grid), len(grid[0])
    
    # Precompute ones count in each row
    onesRow = [sum(row) for row in grid]
    # Precompute ones count in each column
    onesCol = [sum(grid[i][j] for i in range(m)) for j in range(n)]
    
    # Initialize the difference matrix with zeros
    diff = [[0] * n for _ in range(m)]
    
    # Construct the diff matrix using precomputed ones and zeros counts
    for i in range(m):
        # Compute zeros for current row
        zerosRow = n - onesRow[i]
        for j in range(n):
            # Compute zeros for current column
            zerosCol = m - onesCol[j]
            diff[i][j] = onesRow[i] + onesCol[j] - zerosRow - zerosCol
    return diff

# Example usage:
grid = [[0,1,1],[1,0,1],[0,0,1]]
print(onesMinusZeros(grid))
← Back to All Questions