Special Positions in a Binary Matrix - Solution & Explanation
Problem Statement
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.
The function numSpecial iterates over each element in the matrix. For each '1' found, it checks the entire row and column to identify if it's a special position by ensuring all other elements in the row and column are '0'.
Complexity
Time Complexity: O(m * n * (m + n)), where m is the number of rows and n is the number of columns.
Space Complexity: O(1), since we use a constant amount of space.
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.
This function first calculates the number of '1's in each row and column using two arrays. A second iteration through the matrix identifies special positions by checking if the respective row and column have exactly one '1'.
Complexity
Time Complexity: O(m * n), because we only iterate through the matrix twice.
Space Complexity: O(m + n), for storing row and column counts.
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.
Complexity Comparison
| Approach | Complexity |
|---|---|
| Naive Iteration Approach | Time Complexity: O(m * n * (m + n)), where m is the number of rows and n is the number of columns. |
| Row and Column Preprocessing | Time Complexity: O(m * n), because we only iterate through the matrix twice. |
| Counting | — |
Detailed 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 |
Video Solution
Special Positions in a Binary Matrix | 2 Approaches | Leetcode 1582 | codesrorywithMIK • codestorywithMIK • 9,095 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Special Positions in a Binary Matrix easy or hard?
Special Positions in a Binary Matrix Python/Java solution
How to solve Special Positions in a Binary Matrix in O(n)?
What is the best approach for Special Positions in a Binary Matrix?
Is Special Positions in a Binary Matrix asked at Google/Amazon/Meta?
What data structure is used in Special Positions in a Binary Matrix?
What is the time complexity of Special Positions in a Binary Matrix?
Ready to solve this problem?
Practice Special Positions in a Binary Matrix with our built-in code editor and test cases.
Practice on FleetCodeTable of Contents
Practice this problem
Open in Editor