Special Positions in a Binary Matrix solution and explanation
Google
9 more videos on this problem
Special Positions in a Binary Matrix | 2 Approaches | Leetcode 1582 | codesrorywithMIKcodestorywithMIK · 16:10 · 9K views
Special Positions in a Binary Matrix - Leetcode 1582Algorial · 4:59 · 639 views
1582. Special Positions in a Binary Matrix | Leetcode Daily - PythonLeetcode Daily · 6:51 · 628 views
LeetCode 1582 Special Positions in a Binary Matrix | Easy | Beginner Friendly | DetailedCode Harmony · 14:11 · 552 views
Leetcode 1582. Special Positions in a Binary MatrixElite Code · 15:47 · 341 views
Daily Leetcode #2164: Mar 04, 2026 - 1582. Special Positions in a Binary MatrixProgramming Live with Larry · 3:23 · 321 views
Special Positions in a Binary Matrix | LeetCode 1582 | 2 Approaches | Java Code | Developer CoderDeveloper Coder · 14:24 · 248 views
Solving LeetCode 1582 Special Positions in a Binary Matrix | Array | Google | BloombergCode Harmony · 11:40 · 156 views
Special Positions in a Binary Matrix | LeetCode 1582 - Pythonimpoldev · 6:25 · 142 views
Special Positions in a Binary Matrix - LeetCode 1582 - PythonAlpha-Code · 7:51 · 135 views
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 1:
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.
Example 2:
Input: mat = [[1,0,0],[0,1,0],[0,0,1]] Output: 3 Explanation: (0, 0), (1, 1) and (2, 2) are special positions.
Constraints:
m == mat.lengthn == mat[i].length1 <= m, n <= 100mat[i][j]is either0or1.
Approach overview
Problem Overview: You are given an m x n binary matrix. A position (i, j) is considered special if mat[i][j] == 1 and every other element in row i and column j is 0. The task is to count how many such positions exist in the matrix.
Approach 1: Naive Iteration Approach (O(m * n * (m + n)) time, O(1) space)
Scan every cell in the matrix. When you encounter a 1, verify whether it is the only 1 in its row and column. This requires iterating across the entire row and then the entire column to ensure no other 1 exists. If both checks pass, increment the result. The logic is straightforward and requires no extra memory, but the repeated row and column scans make it slower for larger matrices. This approach is useful when you want a quick brute-force implementation using basic array traversal.
Approach 2: Row and Column Preprocessing (O(m * n) time, O(m + n) space)
Instead of repeatedly scanning rows and columns, precompute the number of 1s in each row and each column. First pass: iterate through the matrix and store counts in two arrays, rowCount[m] and colCount[n]. Second pass: check every cell again. If mat[i][j] == 1 and rowCount[i] == 1 and colCount[j] == 1, the position is special. This removes redundant work and guarantees linear traversal of the matrix. The technique is a common optimization pattern when working with matrix problems where repeated row or column checks occur.
Recommended for interviews: The row and column preprocessing approach is the expected solution. Interviewers want to see that you recognize repeated scans and eliminate them with simple counting arrays. Mentioning the brute-force solution first demonstrates understanding of the problem constraints, but implementing the preprocessing optimization shows stronger problem-solving skills and awareness of time complexity improvements.
Approach 1: Naive Iteration Approach
This approach involves iterating through each element of the matrix and checking if it is '1'. For each such element, all other elements in its row and column are checked to ensure they are '0'. This approach is straightforward but can be optimized.
def numSpecial(mat):
m, n = len(mat), len(mat[0])
special_count = 0
for i in range(m):
for j in range(n):
if mat[i][j] == 1:
if sum(mat[i][k] for k in range(n)) == 1 and sum(mat[k][j] for k in range(m)) == 1:
special_count += 1
return special_countclass Solution {
public int numSpecial(int[][] mat) {
int m = mat.length;
int n = mat[0].length;
int specialCount = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (mat[i][j] == 1) {
boolean isSpecial = true;
for (int k = 0; k < m; k++) {
if (k != i && mat[k][j] == 1) {
isSpecial = false;
break;
}
}
for (int k = 0; k < n; k++) {
if (k != j && mat[i][k] == 1) {
isSpecial = false;
break;
}
}
if (isSpecial) specialCount++;
}
}
}
return specialCount;
}
}#include <vector>
using namespace std;
class Solution {
public:
int numSpecial(vector<vector<int>>& mat) {
int m = mat.size(), n = mat[0].size();
int specialCount = 0;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (mat[i][j] == 1) {
bool isSpecial = true;
for (int k = 0; k < m; ++k) {
if (k != i && mat[k][j] == 1) {
isSpecial = false;
break;
}
}
for (int k = 0; k < n; ++k) {
if (k != j && mat[i][k] == 1) {
isSpecial = false;
break;
}
}
if (isSpecial) specialCount++;
}
}
}
return specialCount;
}
};function numSpecial(mat) {
const m = mat.length;
const n = mat[0].length;
let specialCount = 0;
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (mat[i][j] === 1) {
let isSpecial = true;
for (let k = 0; k < m; k++) {
if (k !== i && mat[k][j] === 1) {
isSpecial = false;
break;
}
}
for (let k = 0; k < n; k++) {
if (k !== j && mat[i][k] === 1) {
isSpecial = false;
break;
}
}
if (isSpecial) specialCount++;
}
}
}
return specialCount;
}#include <stdio.h>
int numSpecial(int** mat, int matSize, int* matColSize){
int specialCount = 0;
for (int i = 0; i < matSize; ++i) {
for (int j = 0; j < matColSize[i]; ++j) {
if (mat[i][j] == 1) {
int isSpecial = 1;
for (int k = 0; k < matSize; ++k) {
if (k != i && mat[k][j] == 1) {
isSpecial = 0;
break;
}
}
for (int k = 0; k < matColSize[i]; ++k) {
if (k != j && mat[i][k] == 1) {
isSpecial = 0;
break;
}
}
if (isSpecial) specialCount++;
}
}
}
return specialCount;
}public class Solution {
public int NumSpecial(int[][] mat) {
int m = mat.Length;
int n = mat[0].Length;
int specialCount = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (mat[i][j] == 1) {
bool isSpecial = true;
for (int k = 0; k < m; k++) {
if (k != i && mat[k][j] == 1) {
isSpecial = false;
break;
}
}
for (int k = 0; k < n; k++) {
if (k != j && mat[i][k] == 1) {
isSpecial = false;
break;
}
}
if (isSpecial) specialCount++;
}
}
}
return specialCount;
}
}The function numSpecial iterates through the matrix. For each '1', it checks if the sum of the row and column (excluding the current element) is zero. If both are zero, the position is special.
Time Complexity: O(m * n * (m + n))
Space Complexity: O(1)
Approach 2: Row and Column Preprocessing
In this approach, two auxiliary arrays are used to track the number of '1's in each row and column. The matrix is then iterated to find the positions where both the row and column contain exactly one '1'. This approach reduces the need for repeatedly checking rows and columns.
def numSpecial(mat):
m, n = len(mat), len(mat[0])
row_ones = [0] * m
col_ones = [0] * n
for i in range(m):
for j in range(n):
if mat[i][j] == 1:
row_ones[i] += 1
col_ones[j] += 1
special_count = 0
for i in range(m):
for j in range(n):
if mat[i][j] == 1 and row_ones[i] == 1 and col_ones[j] == 1:
special_count += 1
return special_countclass Solution {
public int numSpecial(int[][] mat) {
int m = mat.length;
int n = mat[0].length;
int[] rowOnes = new int[m];
int[] colOnes = new int[n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (mat[i][j] == 1) {
rowOnes[i]++;
colOnes[j]++;
}
}
}
int specialCount = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (mat[i][j] == 1 && rowOnes[i] == 1 && colOnes[j] == 1) {
specialCount++;
}
}
}
return specialCount;
}
}#include <vector>
using namespace std;
class Solution {
public:
int numSpecial(vector<vector<int>>& mat) {
int m = mat.size(), n = mat[0].size();
vector<int> rowOnes(m, 0), colOnes(n, 0);
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (mat[i][j] == 1) {
rowOnes[i]++;
colOnes[j]++;
}
}
}
int specialCount = 0;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (mat[i][j] == 1 && rowOnes[i] == 1 && colOnes[j] == 1) {
specialCount++;
}
}
}
return specialCount;
}
};function numSpecial(mat) {
const m = mat.length;
const n = mat[0].length;
const rowOnes = Array(m).fill(0);
const colOnes = Array(n).fill(0);
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (mat[i][j] === 1) {
rowOnes[i]++;
colOnes[j]++;
}
}
}
let specialCount = 0;
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (mat[i][j] === 1 && rowOnes[i] === 1 && colOnes[j] === 1) {
specialCount++;
}
}
}
return specialCount;
}#include <stdio.h>
int numSpecial(int** mat, int matSize, int* matColSize){
int rowOnes[matSize];
int colOnes[*matColSize];
for (int i = 0; i < matSize; ++i) rowOnes[i] = 0;
for (int i = 0; i < *matColSize; ++i) colOnes[i] = 0;
for (int i = 0; i < matSize; ++i) {
for (int j = 0; j < matColSize[i]; ++j) {
if (mat[i][j] == 1) {
rowOnes[i]++;
colOnes[j]++;
}
}
}
int specialCount = 0;
for (int i = 0; i < matSize; ++i) {
for (int j = 0; j < matColSize[i]; ++j) {
if (mat[i][j] == 1 && rowOnes[i] == 1 && colOnes[j] == 1) {
specialCount++;
}
}
}
return specialCount;
}public class Solution {
public int NumSpecial(int[][] mat) {
int m = mat.Length;
int n = mat[0].Length;
int[] rowOnes = new int[m];
int[] colOnes = new int[n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (mat[i][j] == 1) {
rowOnes[i]++;
colOnes[j]++;
}
}
}
int specialCount = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (mat[i][j] == 1 && rowOnes[i] == 1 && colOnes[j] == 1) {
specialCount++;
}
}
}
return specialCount;
}
}This Python function collects the '1' counts for each row and column, allowing efficient checks to determine if a given position is special.
Time Complexity: O(m * n)
Space Complexity: O(m + n)
Approach 3: Counting
We can use two arrays, rows and cols, to record the number of 1s in each row and each column, respectively.
Then, we traverse the matrix. For each 1, we check whether there is only one 1 in its row and column. If so, we increment the answer by one.
After the traversal, we return the answer.
The time complexity is O(m times n), and the space complexity is O(m + n). Here, m and n are the number of rows and columns of the matrix mat, respectively.
function numSpecial(mat: number[][]): number {
const m = mat.length;
const n = mat[0].length;
const rows: number[] = Array(m).fill(0);
const cols: number[] = Array(n).fill(0);
for (let i = 0; i < m; ++i) {
for (let j = 0; j < n; ++j) {
rows[i] += mat[i][j];
cols[j] += mat[i][j];
}
}
let ans = 0;
for (let i = 0; i < m; ++i) {
for (let j = 0; j < n; ++j) {
if (mat[i][j] === 1 && rows[i] === 1 && cols[j] === 1) {
++ans;
}
}
}
return ans;
}func numSpecial(mat [][]int) (ans int) {
rows := make([]int, len(mat))
cols := make([]int, len(mat[0]))
for i, row := range mat {
for j, x := range row {
rows[i] += x
cols[j] += x
}
}
for i, row := range mat {
for j, x := range row {
if x == 1 && rows[i] == 1 && cols[j] == 1 {
ans++
}
}
}
return
}impl Solution {
pub fn num_special(mat: Vec<Vec<i32>>) -> i32 {
let m = mat.len();
let n = mat[0].len();
let mut rows = vec![0; m];
let mut cols = vec![0; n];
for i in 0..m {
for j in 0..n {
rows[i] += mat[i][j];
cols[j] += mat[i][j];
}
}
let mut ans = 0;
for i in 0..m {
for j in 0..n {
if mat[i][j] == 1 && rows[i] == 1 && cols[j] == 1 {
ans += 1;
}
}
}
ans
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Naive Iteration Approach | Time Complexity: O(m * n * (m + n)) |
| Row and Column Preprocessing | Time Complexity: O(m * n) |
| Counting | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Naive Iteration | O(m * n * (m + n)) | O(1) | When writing a quick brute-force solution or when matrix size is very small |
| Row and Column Preprocessing | O(m * n) | O(m + n) | General case and interview-preferred approach that avoids repeated row/column scans |
Frequently asked questions
Is Special Positions in a Binary Matrix easy or hard?
LeetCode classifies this problem as Easy because it mainly requires matrix traversal and simple counting. The key idea is recognizing that preprocessing rows and columns avoids repeated checks and improves performance.
Special Positions in a Binary Matrix Python/Java solution
Most implementations follow the same logic: compute row and column counts, then verify each cell. The approach translates directly into Python, Java, C++, and other languages using simple loops and integer arrays.
How to solve Special Positions in a Binary Matrix in O(n)?
For an m x n matrix, the optimal solution is O(m*n). First compute row and column counts in one pass, then check each cell in a second pass. A position is special if it contains 1 and both its row and column counts equal 1.
What is the best approach for Special Positions in a Binary Matrix?
The best approach is row and column preprocessing. Count the number of 1s in each row and each column using two arrays, then scan the matrix again and check if mat[i][j] == 1 with rowCount[i] == 1 and colCount[j] == 1. This reduces the complexity to O(m*n) time with O(m+n) extra space.
Is Special Positions in a Binary Matrix asked at Google/Amazon/Meta?
This problem represents a common matrix counting pattern used in interviews at companies like Amazon and Google. Variations often appear where candidates must preprocess rows or columns to avoid repeated scans.
What data structure is used in Special Positions in a Binary Matrix?
The solution primarily uses arrays for row and column counting along with standard matrix traversal. Two auxiliary arrays store the number of 1s in each row and column to enable constant-time checks.
What is the time complexity of Special Positions in a Binary Matrix?
The optimal solution runs in O(m*n) time because each cell in the matrix is visited a constant number of times. A brute-force approach that scans the entire row and column for every 1 takes O(m*n*(m+n)) time.