algoadvance

You are given m and n which represent the number of rows and columns in a matrix initialized with all 0s and a list indices where indices[i] = [ri, ci] represents incrementing the i-th row (ri) and column (ci) by 1. Your task is to return the number of cells with odd values in the matrix after applying all the increments to the indices.

Example

Input: m = 2, n = 3, indices = [[0,1],[1,1]]
Output: 6

Input: m = 2, n = 2, indices = [[1,1],[0,0]]
Output: 0

Clarifying Questions

1. Can we assume that m and n will always be positive integers?
2. Will indices always have valid rows and columns within the bounds of m and n?
3. Are there constraints on the size of m, n, and the length of indices?

Strategy

1. Initialization: Create a matrix of size m x n initialized to 0.
2. Increment Rows and Columns: For each pair [ri, ci] in indices, increment all elements of row ri and all elements of column ci.
3. Count Odd Cells: Iterate through the matrix and count cells with odd values.

Time Complexity

• The overall complexity will be O(m * n + k * (m + n)), where k is the length of indices. In each of the k operations, incrementing rows and columns will take O(m + n) time, and we need to visit each cell once to count the odd values.

Code

def oddCells(m, n, indices):
    # Step 1: Initialize the m x n matrix with zeros
    matrix = [[0] * n for _ in range(m)]
    
    # Step 2: Apply the increments
    for r, c in indices:
        # Increment the entire row r
        for j in range(n):
            matrix[r][j] += 1
        # Increment the entire column c
        for i in range(m):
            matrix[i][c] += 1
    
    # Step 3: Count the odd values in the matrix
    odd_count = 0
    for i in range(m):
        for j in range(n):
            if matrix[i][j] % 2 != 0:
                odd_count += 1
    
    return odd_count

# Example usage
print(oddCells(2, 3, [[0, 1], [1, 1]])) # Output: 6
print(oddCells(2, 2, [[1, 1], [0, 0]])) # Output: 0

This code follows the strategy of incrementing rows and columns based on the indices, then counting the number of odd-valued cells in the matrix. Each increment operation may touch multiple elements, leading to a time complexity that scales with the matrix size and the number of indices.

Let me know if you need further assistance with this solution or have additional questions!

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?