Special Positions in a Binary Matrix

easy array matrix

Problem

Given a matrix of 0s and 1s, a position (i, j) is special if mat[i][j] = 1 and all other entries in row i and column j are 0. Return the number of special positions.

Inputmat = [[1,0,0],[0,0,1],[1,0,0]]

Output1

Only (1,2) has a lone 1 in its row and column.

mat (rows by ;)

def num_special(mat):
    rows = [sum(r) for r in mat]
    cols = [sum(c) for c in zip(*mat)]
    count = 0
    for i in range(len(mat)):
        for j in range(len(mat[0])):
            if mat[i][j] == 1 and rows[i] == 1 and cols[j] == 1:
                count += 1
    return count

function numSpecial(mat) {
  const m = mat.length, n = mat[0].length;
  const rows = mat.map(r => r.reduce((a, b) => a + b, 0));
  const cols = Array.from({ length: n }, (_, j) => mat.reduce((a, r) => a + r[j], 0));
  let count = 0;
  for (let i = 0; i < m; i++)
    for (let j = 0; j < n; j++)
      if (mat[i][j] === 1 && rows[i] === 1 && cols[j] === 1) count++;
  return count;
}

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

int numSpecial(vector<vector<int>>& mat) {
    int m = mat.size(), n = mat[0].size();
    vector<int> rows(m), cols(n);
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++) { rows[i] += mat[i][j]; cols[j] += mat[i][j]; }
    int count = 0;
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
            if (mat[i][j] == 1 && rows[i] == 1 && cols[j] == 1) count++;
    return count;
}

Explanation

A position is special when it is a 1 that is the only 1 in its row and the only 1 in its column. Checking the whole row and column for every cell would be wasteful, so we precompute the totals once.

We build rows[i] = number of 1s in row i and cols[j] = number of 1s in column j. Because the matrix is binary, a sum of exactly 1 means that line contains a single 1.

Then we scan every cell. Cell (i, j) is special precisely when mat[i][j] == 1 and both rows[i] == 1 and cols[j] == 1 — that one 1 is alone in both directions.

Computing the sums takes one full pass, and the counting takes another, so the total work is O(m·n) time with O(m + n) extra space for the two sum arrays.

Example: [[1,0,0],[0,0,1],[1,0,0]]. Row sums are [1,1,1], column sums are [2,0,1]. The 1 at (1,2) sits in a row summing to 1 and a column summing to 1, so it is special; the answer is 1.

Time: O(m · n) Space: O(m + n)