algoadvance

Leetcode 1252. Cells with Odd Values in a Matrix

Problem Statement

You are given m x n matrix indices, where indices[i] = [ri, ci] indicates a row number ri and a column number ci. Each time you are given a row and column, you increment all elements in the row ri and column ci by 1. Return the number of cells with odd values in the matrix after applying all the increments to the matrix.

Example

Input: m = 2, n = 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]].
After applying the second increment it becomes [[1,3,1],[1,3,1]].

Clarifying Questions

  1. Can m or n be zero?
  2. What is the size range of indices?
  3. Can the entries in indices be out of bounds with respect to m and n?

Strategy

  1. Initialization: Create an m x n matrix initialized to zero.
  2. Apply Increments: For each pair [ri, ci] in indices, increment all elements in row ri and column ci.
  3. Count Odd Values: Iterate through the matrix to count the number of cells with odd values.
  4. Optimized Approach: Instead of maintaining and updating a full m x n matrix, use arrays to track the number of increment operations for each row and each column, reducing the complexity.

Code

Here is the implementation in C++:

#include <vector>

class Solution {
public:
    int oddCells(int m, int n, std::vector<std::vector<int>>& indices) {
        // Arrays to track the number of increments for each row and column
        std::vector<int> row_increments(m, 0);
        std::vector<int> col_increments(n, 0);
        
        // Apply increments as specified by indices
        for (const auto& index : indices) {
            int ri = index[0];
            int ci = index[1];
            row_increments[ri]++;
            col_increments[ci]++;
        }

        // Count the number of odd-value cells
        int odd_count = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                // The value at cell (i, j) is the sum of row and column increments
                if ((row_increments[i] + col_increments[j]) % 2 != 0) {
                    odd_count++;
                }
            }
        }
        
        return odd_count;
    }
};

Time Complexity

Time Complexity Analysis:

Overall Time Complexity: O(m * n + k), but since k is expected to be much smaller compared to m*n, the primary complexity is O(m * n).

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI