Special Positions in a Binary Matrix: Row and Column Sum Trick

Given an m x n binary matrix mat, return the number of special positions in mat. A position (i, j) is called special if mat[i][j] == 1 and all other elements in row i and column j are 0. In other words, the value at (i, j) must be the only 1 in its entire row and the only 1 in its entire column.

This is LeetCode 1582: Special Positions in a Binary Matrix, and it is a clean introduction to the row and column precomputation pattern that shows up across many matrix problems.

Why this problem matters

Matrix problems often ask you to make decisions about individual cells based on information that spans entire rows or columns. The brute force approach of scanning the full row and full column for every cell leads to redundant work. This problem teaches you the precomputation pattern: calculate aggregate information (sums, counts, flags) for each row and column once upfront, then use those precomputed values to answer per-cell questions in constant time.

You will see this same pattern in problems like "Set Matrix Zeroes" (LeetCode 73), "Valid Sudoku" (LeetCode 36), and "Matrix Diagonal Sum" (LeetCode 1572). Once the precomputation instinct is automatic, you recognize it immediately whenever a cell's answer depends on its row or column.

The key insight

Instead of checking every element in the row and column for each 1 you find, precompute the sum of each row and each column. If mat[i][j] == 1, it is the only 1 in its row exactly when rowSum[i] == 1, and it is the only 1 in its column exactly when colSum[j] == 1. Three conditions, all checked in O(1) per cell.

The algorithm:

1. Compute rowSum[i] for every row (sum of all values in row i).
2. Compute colSum[j] for every column (sum of all values in column j).
3. Scan every cell. If mat[i][j] == 1 and rowSum[i] == 1 and colSum[j] == 1, increment the count.

The solution

def num_special(mat: list[list[int]]) -> int:
    rows = len(mat)
    cols = len(mat[0])
    row_sum = [sum(mat[i]) for i in range(rows)]
    col_sum = [sum(mat[i][j] for i in range(rows)) for j in range(cols)]

    count = 0
    for i in range(rows):
        for j in range(cols):
            if mat[i][j] == 1 and row_sum[i] == 1 and col_sum[j] == 1:
                count += 1

    return count

The first two lines measure the matrix dimensions. Then we build row_sum and col_sum in two list comprehensions. Each row_sum[i] is the total number of 1s in row i. Each col_sum[j] is the total number of 1s in column j.

The final nested loop visits every cell. For a cell to be special, three things must all be true: the cell itself holds a 1, its row contains exactly one 1, and its column contains exactly one 1. Because we already precomputed the sums, each of those checks is a simple comparison against 1.

Visual walkthrough

Let's trace through a 3x3 matrix step by step. Watch how the precomputed row and column sums make each cell check instant.

Notice that only position (1,2) passes all three conditions. The two 1s in column 0 disqualify both (0,0) and (2,0) even though their row sums are fine. The precomputed column sum catches this immediately without rescanning.

Complexity analysis

Time is O(m * n) where m is the number of rows and n is the number of columns. Building row_sum takes O(m * n) total work (summing each row). Building col_sum also takes O(m * n). The final scan visits every cell once. All three passes are O(m * n), so the total is O(m * n).

Space is O(m + n) for the two sum arrays. The row_sum array has m entries and the col_sum array has n entries. No additional data structures are needed.

The building blocks

1. Row and column sum precomputation

The pattern of computing an aggregate value for each row and each column before processing individual cells:

row_sum = [sum(mat[i]) for i in range(rows)]
col_sum = [sum(mat[i][j] for i in range(rows)) for j in range(cols)]

This is the core technique. You compute the information you need about each row and column in advance, then query it in O(1) per cell. The same idea works for row maximums, column minimums, or any per-row/per-column aggregate. You will use this in "Set Matrix Zeroes," "Valid Sudoku," and any problem where a cell's answer depends on its row or column neighbors.

2. Multi-condition cell check

The pattern of combining precomputed values to make a per-cell decision:

if mat[i][j] == 1 and row_sum[i] == 1 and col_sum[j] == 1:
    count += 1

This is where the precomputation pays off. Without row_sum and col_sum, you would need to scan the entire row and column for each candidate cell. With them, the check is three comparisons. The pattern generalizes: anytime you need to test a cell against its row and column context, precompute the context first and reduce the check to a constant-time lookup.

Edge cases

Before submitting, think through these scenarios:

• All zeros: every row sum and column sum is 0. No cell has mat[i][j] == 1, so the count is 0.
• Single 1 in the entire matrix: that cell's row sum is 1 and its column sum is 1. It is special. Return 1.
• Every cell is 1: every row sum and column sum is greater than 1. No position can be special. Return 0.
• One row, multiple columns: [[1, 0, 0]]. Row sum is 1, and each column sum is either 0 or 1. Position (0,0) has colSum[0] == 1, so it is special. Return 1.
• One column, multiple rows: [[1], [0], [1]]. Column sum is 2. Neither (0,0) nor (2,0) is special despite both having row sum 1.
• Identity matrix: in an n x n identity matrix, every diagonal cell is the only 1 in its row and the only 1 in its column. All n positions are special.

From understanding to recall

You have seen how precomputed row and column sums reduce each cell check to three comparisons. The logic is clean and the code is short. But reproducing it under interview pressure is a different challenge.

The details that trip people up are small but costly. Do you compute row sums and column sums separately, or try to do both in one pass? Do you check row_sum[i] == 1 or row_sum[i] == 0? Do you iterate over all cells, or only over cells that are 1? These are not conceptual gaps. They are recall gaps, and they cost time in interviews.

Spaced repetition closes them. You practice writing the precomputation step and the multi-condition check from memory at increasing intervals. After a few rounds, you see "check row and column" in a problem description and the template flows out automatically. No re-derivation needed.

Related posts

• Valid Sudoku - Another matrix problem checking row and column constraints
• Set Matrix Zeroes - Matrix manipulation using row and column markers
• Search a 2D Matrix - Efficient searching in a structured matrix

CodeBricks breaks Special Positions in a Binary Matrix into its row-column precomputation and multi-condition check building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a matrix precomputation problem shows up in your interview, you do not hesitate. You just write it.