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 either 0 or 1.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'.
C++
Java
Python
C#
JavaScript
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.
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'.
C++
Java
Python
C#
JavaScript
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 | 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. |
Shortest Path in a Binary Matrix - Leetcode 1091 - Python • NeetCodeIO • 34,602 views views
Watch 9 more video solutions →Practice Special Positions in a Binary Matrix with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor