LC1582: Special Positions in a Binary Matrix

Date: 2026-03-04
Difficulty: EASY
Attempts: 3
Solution link: https://leetcode.com/submissions/detail/1937285902/
Question link: https://leetcode.com/problems/special-positions-in-a-binary-matrix/description/

A few little syntax bugs in the code (unrelate to the intended algorithm) increase the number of attempt to 3. That was dumb.

Intuition

I brute-forced.

Approach

I did what the question says, basically just iterate through every number and test each of them.

A bit of cache are included to avoid testing the same column twice.

Complexity

Time complexity: $O(m*n)$
In the worst scenario (every numbers are 0), we will have to iterate through every numbers in $m*n$ matrix.

Space complexity: $O(m + n)$
Caching introduce two new arrays (visitedRow and visitedCol), each occupy $O(m)$ and $O(n)$ space, thus $O(m+n)$

Code

class Solution {
    public int numSpecial(int[][] mat) {
        int result = 0;
        boolean[] visitedCol = new boolean[mat[0].length];
        boolean[] visitedRow = new boolean[mat.length];
        for (int iRow = 0; iRow < mat.length ; iRow++) {
            if (visitedRow[iRow]) {
                continue;
            }
            int targetCol = -1;
            for (int col = 0; col < mat[0].length; col++) {
                if (mat[iRow][col] == 1) {
                    if (targetCol >= 0) {
                        visitedCol[targetCol] = true;
                        visitedCol[col] = true;
                        break;
                    }
                    if (visitedCol[col]) {
                        break;
                    }
                    targetCol = col;
                }
            }
            if (targetCol >= 0) {
                if (visitedCol[targetCol]) {
                    continue;
                }
                visitedCol[targetCol] = true;
                boolean valid = true;
                for (int r = 0; r < mat.length; r++) {
                    if (mat[r][targetCol] == 1 && (r != iRow || visitedRow[r])) {
                        valid = false;
                        visitedRow[r] = true;
                    }
                }
                if (valid) {
                    result++;
                } else {
                    visitedRow[iRow] = true;
                }
            }
        }
        return result;
    }
}