Cells with Odd Values in a Matrix - Practice Coding Problems

Cells with Odd Values in a Matrix - Problem

Given an m x n matrix initialized to all zeros, and a 2D array indices where each indices[i] = [r_i, c_i] represents a location to perform increment operations.

For each location indices[i], do both of the following:

Increment all cells in row r_i
Increment all cells in column c_i

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

Input & Output

Example 1 — Basic Case

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

› Output: 6

💡 Note: Matrix starts as zeros. After [0,1]: increment row 0 and column 1. After [1,1]: increment row 1 and column 1 again. Final matrix [[1,3,1],[1,3,1]] has 6 odd values.

Example 2 — Single Operation

$ Input: m = 2, n = 2, indices = [[1,1]]

› Output: 4

💡 Note: After [1,1]: increment row 1 and column 1. Final matrix [[0,1],[1,2]] has 4 cells, but only 2 are odd: positions (0,1) and (1,0). Wait, let me recalculate: [[0,1],[1,2]] has values 0,1,1,2 so 2 odd values.

Example 3 — No Operations

$ Input: m = 2, n = 2, indices = []

› Output: 0

💡 Note: No operations performed, matrix remains all zeros, so 0 odd values.

Constraints

1 ≤ m, n ≤ 50
1 ≤ indices.length ≤ 100
0 ≤ r_i < m
0 ≤ c_i < n

Visualization

Tap to expand

Understanding the Visualization

Input

Matrix dimensions m×n and increment indices

Process

Each index [r,c] increments entire row r and column c

Output

Count cells with odd final values

Key Takeaway

🎯 Key Insight: A cell's value equals row increments + column increments. It's odd when exactly one of these counts is odd.

Asked in

G Google 15 a Amazon 12 M Microsoft 8

The key insight is that a cell's final value equals the number of times its row was incremented plus the number of times its column was incremented. A cell has an odd value when this sum is odd, which happens when exactly one of (row count, column count) is odd. The optimal approach uses the mathematical formula: odd_rows × even_cols + even_rows × odd_cols. Time: O(k), Space: O(m + n)

Common Approaches

Approach	Time	Space	Notes
✓ Mathematical Formula	O(k)	O(m + n)	Use mathematical insight: odd_rows × even_cols + even_rows × odd_cols
Count Row/Column Increments	O(k + m×n)	O(m + n)	Count how many times each row and column gets incremented
Simulate Matrix Operations	O(k×(m+n))	O(m×n)	Create the matrix and simulate all increment operations

Mathematical Formula — Algorithm Steps

Step 1: Count how many rows have odd increments
Step 2: Count how many columns have odd increments
Step 3: Result = odd_rows × even_cols + even_rows × odd_cols

Visualization

Tap to expand

Step-by-Step Walkthrough

Count

Count odd/even rows and columns

Formula

odd_rows × even_cols + even_rows × odd_cols

Result

Calculate final answer

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int m, int n, int indices[][2], int indicesSize) {
    int* rowCount = (int*)calloc(m, sizeof(int));
    int* colCount = (int*)calloc(n, sizeof(int));
    
    // Count increments for each row and column
    for (int k = 0; k < indicesSize; k++) {
        rowCount[indices[k][0]]++;
        colCount[indices[k][1]]++;
    }
    
    // Count odd rows and columns
    int oddRows = 0;
    for (int i = 0; i < m; i++) {
        if (rowCount[i] % 2 == 1) oddRows++;
    }
    
    int oddCols = 0;
    for (int j = 0; j < n; j++) {
        if (colCount[j] % 2 == 1) oddCols++;
    }
    
    // Even rows and columns
    int evenRows = m - oddRows;
    int evenCols = n - oddCols;
    
    free(rowCount);
    free(colCount);
    
    // A cell is odd when exactly one of (row_count, col_count) is odd
    return oddRows * evenCols + evenRows * oddCols;
}

int main() {
    int m, n;
    scanf("%d", &m);
    scanf("%d", &n);
    
    char line[1000];
    fgets(line, sizeof(line), stdin);
    fgets(line, sizeof(line), stdin);
    
    int indices[100][2];
    int indicesSize = 0;
    
    char* ptr = line;
    while (*ptr && indicesSize < 100) {
        if (*ptr == '[') {
            ptr++;
            if (*ptr != '[') {
                int r, c;
                sscanf(ptr, "%d,%d", &r, &c);
                indices[indicesSize][0] = r;
                indices[indicesSize][1] = c;
                indicesSize++;
                while (*ptr && *ptr != ']') ptr++;
            }
        }
        ptr++;
    }
    
    printf("%d\n", solution(m, n, indices, indicesSize));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(k)

Only iterate through k indices once to count increments

✓ Linear Growth

Space Complexity

O(m + n)

Arrays to store row and column increment counts

⚡ Linearithmic Space

125.0K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Mathematical Formula — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler