Cells With Odd Values In A Matrix - Leetcode Solution

Problem:

Given n and m which are the dimensions of a matrix initialized by zeros and given an array indices where indices[i] = [ri, ci]. For each pair of [ri, ci] you have to increment all cells in row ri and column ci by 1.

Return the number of cells with odd values in the matrix after applying the increment to all indices.

Example 1:

Input: n = 2, m = 3, indices = [[0,1],[1,1]] Output: 6 Explanation: Initial matrix = [[0,0,0],[0,0,0]]. After applying first increment it becomes [[1,2,1],[0,1,0]]. The count of odd values in the matrix is 6.

Example 2:

Input: n = 2, m = 2, indices = [[1,1],[0,0]] Output: 0 Explanation: Initial matrix = [[0,0],[0,0]]. After applying increment it becomes [[1,0],[0,1]]. There is no odd number in the matrix.

Solution:

To solve the problem, we will initialize a matrix with all zeros. Then we will iterate through the given array indices and increment all cells in row and column by 1. After that, we will count the number of cells with odd values in the matrix and return the count.

The implementation of the above process in Python is given below:

def odd_cells(n: int, m: int, indices: List[List[int]]) -> int:
    # initialize matrix with zeros
    matrix = [[0 for j in range(m)] for i in range(n)]
    # iterate through the given array
    for index in indices:
        row = index[0]
        col = index[1]
        # increment cells in row and column
        for i in range(n):
            matrix[i][col] += 1
        for j in range(m):
            matrix[row][j] += 1
    
    # count cells with odd values
    odd_count = 0
    for i in range(n):
        for j in range(m):
            if matrix[i][j] % 2 != 0:
                odd_count += 1
    
    return odd_count

In the above implementation, we have used Python's list comprehension to initialize the matrix with all zeros. Then, we have used a nested loop to iterate through the given array indices and increment all cells in the row and column by 1. Finally, we have used another nested loop to count the number of cells with odd values in the matrix.

The time and space complexity of the above algorithm is O(nm) because we are iterating through the entire matrix and using extra space to store the matrix.

1