What defines a special position in a binary matrix?

A special position is any cell mat[i][j] that equals 1 and has no other 1s in its entire row i and column j.

How do row and column counts help in solving this problem?

By precomputing the number of 1s in each row and column, you can efficiently check the special position condition without scanning rows and columns repeatedly.

Can this approach handle large matrices efficiently?

Yes, the method runs in O(m * n) time with O(m + n) extra space, making it suitable for matrices up to 100x100 within constraints.

Are there variations of the special positions problem?

Yes, you can extend it to k-special positions, rectangular matrices, or sparse storage formats, all relying on the same row and column counting logic.

Why is this an 'Array plus Matrix' pattern problem?

Because the solution combines matrix traversal with array bookkeeping for rows and columns, exemplifying the array plus matrix pattern clearly.

#1582

Easy

auto_awesome数组·matrix

LeetCode 题解工作台

二进制矩阵中的特殊位置

给定一个 m x n 的二进制矩阵 mat ，返回矩阵 mat 中特殊位置的数量。如果位置 (i, j) 满足 mat[i][j] == 1 并且行 i 与列 j 中的所有其他元素都是 0 （行和列的下标从 0 开始计数），那么它被称为特殊位置。示例 1：输入： mat = [[1,0,0…

数组矩阵

题目描述

给定一个 m x n 的二进制矩阵 mat，返回矩阵 mat 中特殊位置的数量。

如果位置 (i, j) 满足 mat[i][j] == 1 并且行 i 与列 j 中的所有其他元素都是 0（行和列的下标从 0 开始计数），那么它被称为特殊位置。

示例 1：

输入：mat = [[1,0,0],[0,0,1],[1,0,0]]
输出：1
解释：位置 (1, 2) 是一个特殊位置，因为 mat[1][2] == 1 且第 1 行和第 2 列的其他所有元素都是 0。

示例 2：

输入：mat = [[1,0,0],[0,1,0],[0,0,1]]
输出：3
解释：位置 (0, 0)，(1, 1) 和 (2, 2) 都是特殊位置。

提示：

m == mat.length
n == mat[i].length
1 <= m, n <= 100
mat[i][j] 是 0 或 1。

lightbulb

解题思路

方法一：计数

我们可以用两个数组 $\textit{rows}$ 和 $\textit{cols}$ 分别记录每一行和每一列的 $1$ 的个数。

然后遍历矩阵，对于每一个 $1$ ，检查其所在的行和列是否只有一个 $1$ ，如果是则答案加一。

遍历结束后，返回答案即可。

时间复杂度 $O(m \times n)$ ，空间复杂度 $O(m + n)$ 。其中 $m$ 和 $n$ 分别是矩阵 $\textit{mat}$ 的行数和列数。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

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

speed

复杂度分析

指标	值
时间	complexity is O(m * n) because each element is visited twice: once for counting and once for validation. Space complexity is O(m + n) due to the rowCount and colCount arrays storing the number of 1s per row and column.
空间	O(m + n)

psychology

面试官常问的追问

外企场景

question_mark
Looking for awareness of how to track multiple constraints simultaneously across rows and columns.
question_mark
Checking if candidate recognizes the array plus matrix pattern to avoid repeated scanning.
question_mark
Observing if candidate correctly identifies the special position condition without unnecessary nested loops.

warning

常见陷阱

外企场景

error
Scanning rows and columns repeatedly instead of precomputing counts, leading to O(m * n * max(m,n)) complexity.
error
Forgetting that a position is only special if both its row and column have exactly one 1.
error
Modifying the matrix in-place which can invalidate other checks and result in incorrect counts.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Counting special positions in a rectangular binary matrix with unequal row and column lengths.
arrow_right_alt
Extending to k-special positions where exactly k 1s are allowed in a row or column.
arrow_right_alt
Identifying special positions in a sparse matrix stored in coordinate list format to reduce memory overhead.

help

常见问题

外企场景

继续练习

#1591 奇怪的打印机 II #1572 矩阵对角线元素的和 #1594 矩阵的最大非负积