LeetCode 1582 - Special Positions in a Binary Matrix

LeetCode Problem 1582

Difficulty: 🟢 Easy
Topics: Array, Matrix

Solution

Here is a complete, detailed technical solution guide for LeetCode 1582 - Special Positions in a Binary Matrix, following your formatting and content requirements precisely.

Problem Understanding

The problem provides an m x n binary matrix mat consisting only of 0s and 1s, and asks us to find the number of special positions. A position (i, j) is special if mat[i][j] == 1 and all other elements in row i and column j are 0. In other words, a 1 is special if it is the only 1 in its row and its column.

The input constraints are 1 <= m, n <= 100, which tells us the matrix is relatively small and that a simple O(m × n × max(m, n)) brute-force solution might work but is inefficient. The output is a single integer representing the total number of special positions.

Edge cases to consider include: matrices with all zeros (should return 0), matrices where all ones lie in the same row or column (none are special), or a matrix with a single element (either 0 or 1). The problem guarantees that the matrix contains only 0s and 1s, so we do not need to handle other data types.

Approaches

Brute Force Approach:

The simplest approach is to iterate over each cell (i, j). For every 1 found, scan the entire row i and column j to ensure there are no other 1s. If both checks pass, the position is special.

This approach works because it directly implements the definition, but it is inefficient. For each 1, we may scan up to m + n elements, leading to a worst-case complexity of O(m × n × (m + n)) if almost all elements are 1. This is unnecessary given the input size.

Optimal Approach:

The key insight is that for a position (i, j) to be special, its entire row and column must contain exactly one 1. We can precompute the number of ones in each row and each column using two arrays: row_count and col_count. After counting, we iterate over the matrix, and any position (i, j) where mat[i][j] == 1, row_count[i] == 1, and col_count[j] == 1 is special.

This approach is efficient because counting rows and columns takes O(m × n) time and checking each element afterward takes another O(m × n), resulting in an overall O(m × n) time complexity. Space complexity is O(m + n) for the two count arrays.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(m × n × (m + n))	O(1)	Scan each row and column for each 1
Optimal	O(m × n)	O(m + n)	Precompute row and column counts, then check conditions

Algorithm Walkthrough

1. Initialize two arrays, row_count of size m and col_count of size n, to store the number of ones in each row and column, respectively.
2. Iterate over each cell (i, j) in the matrix. If mat[i][j] == 1, increment row_count[i] and col_count[j]. This counts the total number of ones per row and per column.
3. Initialize a counter special_positions to 0.
4. Iterate over the matrix again. For each cell (i, j) where mat[i][j] == 1, check if row_count[i] == 1 and col_count[j] == 1. If both conditions are true, increment special_positions.
5. Return special_positions.

Why it works:

By counting the number of ones in each row and column upfront, we reduce the problem to a simple check per cell. Any 1 with a unique row and column count is guaranteed to be the only 1 in its row and column, fulfilling the special position condition.

Python Solution

from typing import List

class Solution:
    def numSpecial(self, mat: List[List[int]]) -> int:
        m, n = len(mat), len(mat[0])
        row_count = [0] * m
        col_count = [0] * n

        # Count ones in each row and column
        for i in range(m):
            for j in range(n):
                if mat[i][j] == 1:
                    row_count[i] += 1
                    col_count[j] += 1

        special_positions = 0
        # Check for special positions
        for i in range(m):
            for j in range(n):
                if mat[i][j] == 1 and row_count[i] == 1 and col_count[j] == 1:
                    special_positions += 1

        return special_positions

Explanation:

The first nested loop counts the number of ones in each row and column. The second nested loop checks the condition for a special position by leveraging the precomputed counts. Using arrays for counting ensures we do not repeatedly scan rows or columns, which keeps the time complexity optimal.

Go Solution

func numSpecial(mat [][]int) int {
    m, n := len(mat), len(mat[0])
    rowCount := make([]int, m)
    colCount := make([]int, n)

    // Count ones in each row and column
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if mat[i][j] == 1 {
                rowCount[i]++
                colCount[j]++
            }
        }
    }

    specialPositions := 0
    // Check for special positions
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if mat[i][j] == 1 && rowCount[i] == 1 && colCount[j] == 1 {
                specialPositions++
            }
        }
    }

    return specialPositions
}

Go-specific Notes:

In Go, slices are used for the rowCount and colCount arrays. Indexing and iteration are similar to Python. There is no need to handle nil matrices because the problem constraints guarantee at least 1 row and 1 column.

Worked Examples

Example 1: mat = [[1,0,0],[0,0,1],[1,0,0]]

Step 1: Count ones:

Row	Count
0	1
1	1
2	1

Col	Count
0	2
1	0
2	1

Step 2: Check special positions:

• (0,0) → row_count[0]=1, col_count[0]=2 → not special
• (1,2) → row_count[1]=1, col_count[2]=1 → special
• (2,0) → row_count[2]=1, col_count[0]=2 → not special

Result = 1

Example 2: mat = [[1,0,0],[0,1,0],[0,0,1]]

Row counts: [1,1,1]

Column counts: [1,1,1]

All diagonal positions (0,0), (1,1), (2,2) satisfy the condition → result = 3

Complexity Analysis

Measure	Complexity	Explanation
Time	O(m × n)	Count ones in rows and columns (O(m × n)) and check conditions (O(m × n))
Space	O(m + n)	Arrays to store row counts and column counts

This complexity is optimal given that every element must be examined at least once. Memory usage is minimal, only two arrays proportional to the number of rows and columns.

Test Cases

# Provided examples
assert Solution().numSpecial([[1,0,0],[0,0,1],[1,0,0]]) == 1  # only (1,2)
assert Solution().numSpecial([[1,0,0],[0,1,0],[0,0,1]]) == 3  # diagonal

# Edge cases
assert Solution().numSpecial([[0]]) == 0  # single element zero
assert Solution().numSpecial([[1]]) == 1  # single element one
assert Solution().numSpecial([[1,1],[1,0]]) == 0  # multiple ones in row/column

# Larger test
assert Solution().numSpecial([[0,1,0],[0,0,0],[0,0,1]]) == 2  # (0,1) and (2,2)

Test	Why
[[1,0,0],[0,0,1],[1,0,0]]	Example with overlapping column ones
[[1,0,0],[0,1,0],[0,0,1]]	Diagonal ones, all special
[[0]]	Minimum size, zero
`[[1