Scale Engineer

Special Positions in a Binary Matrix

Easy
#1455Time: 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: O(1). We only use a few variables to keep track of the count and loop indices, which is constant extra space.
Data structures
ArrayMatrix

Prompt

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

2 approaches with complexity analysis and trade-offs.

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.

Walkthrough

The algorithm proceeds as follows:

  1. Initialize a counter specialCount to 0.
  2. Iterate through each cell (i, j) of the matrix mat, where i is the row index and j is the column index.
  3. If mat[i][j] is 1, we need to verify if it's a special position.
  4. 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.
  5. If both the row and column checks pass (meaning no other 1s were found), it means (i, j) is a special position. Increment specialCount.
  6. 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

Time

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

O(1). We only use a few variables to keep track of the count and loop indices, which is constant extra space.

Trade-offs

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.

Solutions

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 walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem