Special Positions in a Binary Matrix

EASY

Description

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.length
n == mat[i].length
1 <= m, n <= 100
mat[i][j] is either 0 or 1.

Approaches

Checkout 2 different approaches to solve Special Positions in a Binary Matrix. Click on different approaches to view the approach and algorithm in detail.

Brute Force Iteration

This approach involves iterating through every single cell of the matrix. For each cell that contains a 1, we then perform a check to see if it qualifies as a "special" position. This check involves scanning the entire corresponding row and column to ensure all other elements are 0.

Algorithm

Initialize specialCount = 0.
Get matrix dimensions m (rows) and n (columns).
For i from 0 to m-1:
- For j from 0 to n-1:
  - If mat[i][j] == 1:
    - Set a flag isSpecial = true.
    - Check the row: For k from 0 to n-1:
      - If k != j and mat[i][k] == 1, set isSpecial = false and break the loop.
    - If isSpecial is false, continue to the next j.
    - Check the column: For k from 0 to m-1:
      - If k != i and mat[k][j] == 1, set isSpecial = false and break the loop.
    - If isSpecial is still true, increment specialCount.
Return specialCount.

The algorithm proceeds as follows:

Initialize a counter specialCount to 0.
Iterate through each cell (i, j) of the matrix mat, where i is the row index and j is the column index.
If mat[i][j] is 1, we need to verify if it's a special position.
To do this, we check two conditions: a. Row Check: Iterate through all elements in row i. If we find another 1 (at a column k where k != j), then this position is not special. b. Column Check: Iterate through all elements in column j. If we find another 1 (at a row k where k != i), then this position is not special.
If both the row and column checks pass (meaning no other 1s were found), it means (i, j) is a special position. Increment specialCount.
After checking all cells, the value of specialCount is the result.

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) {
                    boolean isSpecial = true;
                    
                    // Check row i
                    for (int k = 0; k < n; k++) {
                        if (k != j && mat[i][k] == 1) {
                            isSpecial = false;
                            break;
                        }
                    }
                    
                    if (!isSpecial) continue;

                    // Check column j
                    for (int k = 0; k < m; k++) {
                        if (k != i && mat[k][j] == 1) {
                            isSpecial = false;
                            break;
                        }
                    }

                    if (isSpecial) {
                        specialCount++;
                    }
                }
            }
        }
        return specialCount;
    }
}

Complexity Analysis

Time Complexity: O(m * n * (m + n)). For each of the `m * n` cells, if it's a `1`, we scan its row (size `n`) and its column (size `m`). In the worst case, this leads to the specified complexity.Space Complexity: O(1). We only use a few variables to keep track of the count and loop indices, which is constant extra space.

Pros and Cons

Pros:

Simple to understand and implement.
Requires no extra space beyond the input matrix.

Cons:

Highly inefficient due to redundant computations. The same row or column is scanned multiple times for different 1s within them.

Code Solutions

Checking out 3 solutions in different languages for Special Positions in a Binary Matrix. Click on different languages to view the code.

class Solution {
public
  int numSpecial(int[][] mat) {
    int m = mat.length, n = mat[0].length;
    int[] r = new int[m];
    int[] c = new int[n];
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        r[i] += mat[i][j];
        c[j] += mat[i][j];
      }
    }
    int ans = 0;
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        if (mat[i][j] == 1 && r[i] == 1 && c[j] == 1) {
          ++ans;
        }
      }
    }
    return ans;
  }
}

Video Solution

Watch the video walkthrough for Special Positions in a Binary Matrix

Data Structures:

ArrayMatrix