Special Positions in a Binary Matrix

Easy
307.

Special Positions in a Binary Matrix

Special Positions in a Binary Matrix is an easy coding problem on arrays and matrix, asked in Amazon and Microsoft interviews.

Given an m × n binary matrix mat, return the number of special positions.

A position (i, j) is special if mat[i][j] == 1 and every other element in row i and column j is 0.

Example 1

Input
mat = [[1,0,0],[0,0,1],[1,0,0]]
Output
1
Explanation
Only (1,2) is alone in both its row and its column.

Example 2

Input
mat = [[1,0,0],[0,1,0],[0,0,1]]
Output
3

Example 3

Input
mat = [[0,0],[0,0]]
Output
0

Constraints

  • 1 <= mat.length, mat[i].length <= 8
  • mat[i][j] is 0 or 1.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} mat
 * @return {number}
 */
var numSpecial = function(mat) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Special Positions in a Binary Matrix — Problem & Solution

Special Positions in a Binary Matrix solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Special Positions in a Binary Matrix is an easy coding problem on arrays and matrix, asked in Amazon and Microsoft interviews.

  • Difficulty: Easy
  • Topics: Arrays, Matrix
  • Asked at: Amazon, Microsoft
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Given an m × n binary matrix mat, return the number of special positions.

A position (i, j) is special if mat[i][j] == 1 and every other element in row i and column j is 0.

Example 1

Input: mat = [[1,0,0],[0,0,1],[1,0,0]]
Output: 1
Explanation: Only (1,2) is alone in both its row and its column.

Example 2

Input: mat = [[1,0,0],[0,1,0],[0,0,1]]
Output: 3

Example 3

Input: mat = [[0,0],[0,0]]
Output: 0

Constraints

  • 1 <= mat.length, mat[i].length <= 8
  • mat[i][j] is 0 or 1.

Hints for Special Positions in a Binary Matrix

  1. Hint 1

    Precompute the sum of every row and every column in one pass.

  2. Hint 2

    A cell is special exactly when it holds a 1 and both of those sums equal 1.

How to solve Special Positions in a Binary Matrix

Precompute row and column sums; a cell is special iff it holds a 1 and both its row sum and column sum equal 1.

Approach

  1. Compute rowSum and colSum.
  2. Count cells with mat[r][c] == 1, rowSum[r] == 1, colSum[c] == 1.

Why it works

"Every other element in the row and column is 0" is equivalent to the sums being exactly 1 when the cell itself is 1.

Complexity

  • Time — O(m · n)
  • Space — O(m + n)

Pitfalls

  • Rechecking the row and column per cell is O(m·n·(m+n)) — precompute instead.

Reference solution

Python

def numSpecial(mat) -> int:
    m, n = len(mat), len(mat[0])
    row_sum = [sum(row) for row in mat]
    col_sum = [sum(mat[r][c] for r in range(m)) for c in range(n)]
    return sum(1 for r in range(m) for c in range(n)
               if mat[r][c] == 1 and row_sum[r] == 1 and col_sum[c] == 1)

Java

public static int numSpecial(int[][] mat) {
    int m = mat.length, n = mat[0].length;
    int[] rowSum = new int[m];
    int[] colSum = new int[n];
    for (int r = 0; r < m; r++) {
        for (int c = 0; c < n; c++) {
            rowSum[r] += mat[r][c];
            colSum[c] += mat[r][c];
        }
    }
    int count = 0;
    for (int r = 0; r < m; r++) {
        for (int c = 0; c < n; c++) {
            if (mat[r][c] == 1 && rowSum[r] == 1 && colSum[c] == 1) count++;
        }
    }
    return count;
}

C++

int numSpecial(vector<vector<int>>& mat) {
    int m = (int) mat.size(), n = (int) mat[0].size();
    vector<int> rowSum(m, 0), colSum(n, 0);
    for (int r = 0; r < m; r++) {
        for (int c = 0; c < n; c++) {
            rowSum[r] += mat[r][c];
            colSum[c] += mat[r][c];
        }
    }
    int count = 0;
    for (int r = 0; r < m; r++) {
        for (int c = 0; c < n; c++) {
            if (mat[r][c] == 1 && rowSum[r] == 1 && colSum[c] == 1) count++;
        }
    }
    return count;
}

JavaScript

var numSpecial = function(mat) {
    const m = mat.length, n = mat[0].length;
    const rowSum = new Array(m).fill(0);
    const colSum = new Array(n).fill(0);
    for (let r = 0; r < m; r++) {
        for (let c = 0; c < n; c++) {
            rowSum[r] += mat[r][c];
            colSum[c] += mat[r][c];
        }
    }
    let count = 0;
    for (let r = 0; r < m; r++) {
        for (let c = 0; c < n; c++) {
            if (mat[r][c] === 1 && rowSum[r] === 1 && colSum[c] === 1) count++;
        }
    }
    return count;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Matrix and Grid Traversal