1582. Special Positions in a Binary Matrix

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.

 

Solutions

Solution: Hash Table

• Time complexity: O(mn)
• Space complexity: O(m+n)

 

JavaScript

/**
 * @param {number[][]} mat
 * @return {number}
 */
const numSpecial = function (mat) {
  const m = mat.length;
  const n = mat[0].length;
  const rows = Array.from({ length: m }, () => 0);
  const cols = Array.from({ length: n }, () => 0);
  let result = 0;

  for (let row = 0; row < m; row++) {
    for (let col = 0; col < n; col++) {
      const value = mat[row][col];

      rows[row] += value;
      cols[col] += value;
    }
  }

  for (let row = 0; row < m; row++) {
    for (let col = 0; col < n; col++) {
      const value = mat[row][col];

      if (value === 1 && rows[row] === 1 && cols[col] === 1) {
        result += 1;
      }
    }
  }

  return result;
};