Domain 1EasyCORE

Special Positions in a Binary Matrix

The problem requires us to find special positions in a binary matrix. A position `(i, j)` is considered special if `mat[i][j] == 1` and all other elements in row `i` and column `j` are `0`. The input is a matrix of size `rows x cols` where each element is either `0` or `1`. The output should be the count of such special positions.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Array

1582. Special Positions in a Binary Matrix

Model: qwen2.5-coder:14b
Topics: Array
FAANG asked: 1
Acceptance rate: 64.3%


Problem Breakdown

The problem requires us to find special positions in a binary matrix. A position (i, j) is considered special if mat[i][j] == 1 and all other elements in row i and column j are 0. The input is a matrix of size rows x cols where each element is either 0 or 1. The output should be the count of such special positions.

Inputs:

  • A binary matrix mat with dimensions rows x cols.

Outputs:

  • An integer representing the number of special positions in the matrix.

Implicit Constraints:

  • The matrix can have up to 100 rows and columns.
  • All elements are either 0 or 1.
  • Edge cases include matrices with all zeros, a single row/column, and matrices where no special positions exist.

Intuition

The brute-force approach would involve checking each element in the matrix. If an element is 1, we then check if all other elements in its row and column are 0. This approach has a time complexity of O(rows * cols * (rows + cols)), which is inefficient for larger matrices.

A better approach involves using auxiliary arrays to keep track of the number of 1s in each row and each column. By precomputing these counts, we can determine if a position is special in constant time after the initial pass through the matrix. This reduces the overall time complexity to O(rows * cols).

Approach

  1. Initialize two arrays: row_counts of size rows and col_counts of size cols. These will store the count of 1s for each row and column, respectively.
  2. Traverse the matrix once:
    • For each element mat[i][j] that is 1, increment row_counts[i] and col_counts[j].
  3. Traverse the matrix again:
    • For each element mat[i][j] that is 1, check if row_counts[i] == 1 and col_counts[j] == 1. If both conditions are met, it means this position is special.
  4. Count all such special positions and return the count.

Complexity Analysis

  • Time Complexity: O(rows * cols). We traverse the matrix twice: once to compute row and column counts, and once to check for special positions.
  • Space Complexity: O(rows + cols) for storing the row and column counts.

Solution

def numSpecial(mat):
    rows = len(mat)
    cols = len(mat[0])
    
    # Step 1: Initialize row and column count arrays
    row_counts = [0] * rows
    col_counts = [0] * cols
    
    # Step 2: Compute the counts of 1s in each row and column
    for i in range(rows):
        for j in range(cols):
            if mat[i][j] == 1:
                row_counts[i] += 1
                col_counts[j] += 1
    
    # Step 3: Count special positions
    special_count = 0
    for i in range(rows):
        for j in range(cols):
            if mat[i][j] == 1 and row_counts[i] == 1 and col_counts[j] == 1:
                special_count += 1
    
    return special_count

Edge Cases Handled

  • All zeros matrix: The function will correctly return 0 as there are no 1s to check.
  • Single row/column matrix: The function will handle this by simply counting the number of 1s in the single row or column and checking if they meet the criteria for being special.
  • No special positions: If no position meets the criteria, the function will return 0.
  • Matrix with all ones: The function will correctly identify each 1 as a special position only if it is the only 1 in its row and column.