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

Cells with Odd Values in a Matrix

Number: 1378

Difficulty: Easy

Paid? No

Companies: Google

Problem Description

Given an m x n matrix initially filled with zeros, you are provided with a list of indices. For each index [r, c] in the list, increment all values in row r and all values in column c. The task is to return the count of cells in the matrix that contain an odd number after all operations are performed.

Key Insights

  • Instead of updating the entire matrix for each operation (which could be inefficient), count the total number of increments for each row and each column using two separate arrays.
  • For any cell (i, j), its final value will be the sum of the count from its corresponding row and column.
  • A cell is odd if the sum (rowCounts[i] + colCounts[j]) is odd.
  • Use basic arithmetic properties: odd+even or even+odd gives odd, while even+even and odd+odd give even.
  • This allows solving the problem in O(m + n + number of operations) time using O(m + n) extra space.

Space and Time Complexity

Time Complexity: O(m + n + k) where m and n are the dimensions of the matrix and k is the number of indices. Space Complexity: O(m + n) for the row and column count arrays.

Solution

We use two arrays (or lists) to track how many times each row and each column is incremented. For each operation [r, c] given in the input, we increment the count for row r and the count for column c. After processing all operations, every cell’s value in the matrix is determined by the sum of the increments for its row and column. A cell will have an odd value if the sum is odd. Finally, count such cells by iterating through all possible cells in the matrix and checking if the sum is odd.

Code Solutions

# Python solution with line-by-line comments
def oddCells(m, n, indices):
    # Initialize counters for rows and columns
    row_counts = [0] * m  # List to track increment counts for each row
    col_counts = [0] * n  # List to track increment counts for each column

    # Process each index operation
    for r, c in indices:
        # Increment the count for the given row and column
        row_counts[r] += 1
        col_counts[c] += 1

    # Initialize the odd count
    odd_count = 0

    # Check each cell in the matrix using the counts
    for i in range(m):
        for j in range(n):
            # The value of cell (i, j) is a sum of the row increment and column increment
            if (row_counts[i] + col_counts[j]) % 2 == 1:
                # Increase count if the sum is odd
                odd_count += 1

    return odd_count

# Example usage
print(oddCells(2, 3, [[0,1],[1,1]]))  # Output: 6
← Back to All Questions