EasyNo. 1582
Special Positions in a Binary Matrix — LeetCode 1582 Python Solution
- Pattern
- Matrix and Grid
- Topics
- Array, Matrix
- Reading time
- 2 min
- Source
- leetcode.com
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 ansComplexity
- Time
- O(m × n)
- Space · auxiliary
- O(m + n)
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
| No. | Problem | Difficulty |
|---|---|---|
| 1572 | Matrix Diagonal Sum | Easy |
| 0054 | Spiral Matrix | Medium |
| 0059 | Spiral Matrix II | Medium |
| 0289 | Game of Life | Medium |
| 0498 | Diagonal Traverse | Medium |
| 0566 | Reshape the Matrix | Easy |
Frequently asked questions
- How hard is LeetCode 1582. Special Positions in a Binary Matrix?
LeetCode 1582. Special Positions in a Binary Matrix is rated Easy on LeetCode.
- What is the time complexity of LeetCode 1582. Special Positions in a Binary Matrix?
The Python solution on this page runs in O(m × n).
- What is the space complexity of LeetCode 1582. Special Positions in a Binary Matrix?
The Python solution on this page uses O(m + n) auxiliary space.
- What topics does LeetCode 1582. Special Positions in a Binary Matrix cover?
LeetCode 1582. Special Positions in a Binary Matrix is tagged Array and Matrix on LeetCode.