1582. Special Positions in a Binary Matrix

Array
Matrix

TIME

O(m × n)

SPACE

O(m + n)

Intuition

A position is special if it's a 1 and it's the only 1 in both its row and column. Pre-compute the count of 1s in each row and column, then check each 1 against these counts.

Solution

First pass: Count the number of 1s in each row and column
- rowCount[i] = number of 1s in row i
- colCount[j] = number of 1s in column j
Second pass: For each cell with value 1, check if:
- rowCount[i] == 1 (only one 1 in this row)
- colCount[j] == 1 (only one 1 in this column)
If both conditions are true, it's a special position.

Complexity

Time: O(m × n), two passes through the matrix
Space: O(m + n), arrays for row and column counts

Edge Cases

All zeros → return 0
Identity matrix → return min(m, n)
Single row/column → at most 1 special position
All ones → return 0

Code

from typing import List


class Solution:
    def numSpecial(self, mat: List[List[int]]) -> int:
        """
        1582. Special Positions in a Binary Matrix
        Time: O(m × n)
        Space: O(m + n)
        """
        m, n = len(mat), len(mat[0])

        row_count = [0] * m
        col_count = [0] * n

        for i in range(m):
            for j in range(n):
                if mat[i][j] == 1:
                    row_count[i] += 1
                    col_count[j] += 1

        ans = 0
        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:
                    ans += 1

        return ans

/**
 * 1582. Special Positions in a Binary Matrix
 * Time: O(m × n)
 * Space: O(m + n)
 */
class Solution {
    public int numSpecial(int[][] mat) {
        int m = mat.length;
        int n = mat[0].length;

        int[] rowCount = new int[m];
        int[] colCount = new int[n];

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (mat[i][j] == 1) {
                    rowCount[i]++;
                    colCount[j]++;
                }
            }
        }

        int ans = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (mat[i][j] == 1 && rowCount[i] == 1 && colCount[j] == 1) {
                    ans++;
                }
            }
        }

        return ans;
    }
}