algoadvance

Leetcode 1252. Cells with Odd Values in a Matrix

Problem Statement

You’re given m and n, the dimensions of a matrix, and an array indices where indices[i] = [ri, ci] represents that the i-th increment operation is applied on the matrix. Specifically, all cells in row ri and all cells in column ci are incremented by 1.

Return the number of cells with odd values in the matrix after performing all the given increment operations.

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 second increment it becomes [[1,3,1],[1,3,1]].
So, there are 6 cells with odd values.

Clarifying Questions

  1. Can m and n be zero?
    • Typically matrix dimensions will be >= 1. But if zero dimensions are considered, no cells would be present.
  2. Are ri and ci guaranteed to be within bounds?
    • Yes, ri is between 0 and m-1 and ci is between 0 and n-1.

Strategy

  1. Initialize the Matrix:
    • Start with an m x n matrix initialized with zeros.
  2. Increment Rows and Columns:
    • For each pair [ri, ci] in indices, increment every element in row ri and column ci by 1.
  3. Count Odd Values:
    • Traverse the matrix to count how many cells contain odd values.

Here’s a more optimized strategy to avoid directly manipulating the matrix:

  1. Track Row and Column Increments:
    • Use two arrays rowCount and colCount to keep track of the increments for the rows and columns, respectively.
  2. Apply Increments:
    • For each [ri, ci] in indices, increment the respective rowCount[ri] and colCount[ci].
  3. Calculate Odd Cells:
    • Traverse through all cells using the row and column increment counts to determine if they end up odd.

Code

public class Solution {
    public int oddCells(int m, int n, int[][] indices) {
        int[] rowCount = new int[m];
        int[] colCount = new int[n];
        
        // Increment counts based on the indices operations
        for (int[] index : indices) {
            int row = index[0];
            int col = index[1];
            rowCount[row]++;
            colCount[col]++;
        }
        
        // Calculate the number of odd cells
        int oddCellsCount = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if ((rowCount[i] + colCount[j]) % 2 != 0) {
                    oddCellsCount++;
                }
            }
        }
        
        return oddCellsCount;
    }
}

Time Complexity

Thus, overall time complexity is O(m * n + k).

This solution efficiently tracks the increments and avoids the direct manipulation of every matrix cell, ensuring a concise and effective implementation.

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