Special Positions in a Binary Matrix — LeetCode 1582 Python Solution

The problem

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 (rows and columns are 0-indexed).

Example

Input

mat = [[1,0,0],[0,0,1],[1,0,0]]

Output

1

Explanation

(1, 2) is a special position because mat[1][2] == 1 and all other elements in row 1 and column 2 are 0.

Python solution

class Solution:
    def numSpecial(self, mat: List[List[int]]) -> int:
        rows = [0] * len(mat)
        cols = [0] * len(mat[0])
        for i, row in enumerate(mat):
            for j, x in enumerate(row):
                rows[i] += x
                cols[j] += x
        ans = 0
        for i, row in enumerate(mat):
            for j, x in enumerate(row):
                ans += x == 1 and rows[i] == 1 and cols[j] == 1
        return ans

Complexity

Pattern: Matrix and Grid

Treat a 2-D grid as a graph whose neighbours are the four adjacent cells. LeetCode 1582. Special Positions in a Binary Matrix is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Matrix.

The matrix and grid guide has the Python template for the pattern and the 216 LeetCode problems that use it.

Related problems