Special Positions in a Binary Matrix - Practice Coding Problems

Special Positions in a Binary Matrix - Problem

Array Matrix Easy

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).

Input & Output

Example 1 — Basic Matrix

$ Input: mat = [[1,0,0],[0,0,1],[1,0,0]]

› Output: 1

💡 Note: Position (1,2) is special: mat[1][2]=1, row 1 has sum 1, column 2 has sum 1

Example 2 — No Special Positions

$ Input: mat = [[1,0,0],[0,1,0],[0,0,1]]

› Output: 3

💡 Note: All three positions (0,0), (1,1), and (2,2) are special - each has unique row and column

Example 3 — Multiple 1s in Row/Column

$ Input: mat = [[0,0,0,1],[1,0,0,0],[0,1,1,0],[0,0,0,0]]

› Output: 2

💡 Note: Positions (0,3) and (1,0) are special, but (2,1) and (2,2) are not because row 2 has multiple 1s

Constraints

m == mat.length
n == mat[i].length
1 ≤ m, n ≤ 100
mat[i][j] is either 0 or 1

Visualization

Tap to expand

Understanding the Visualization

Input Matrix

Binary matrix with 1s and 0s

Check Conditions

Find 1s that are alone in row and column

Count Special

Count positions meeting both conditions

Key Takeaway

🎯 Key Insight: Pre-calculating row and column sums eliminates redundant work

Asked in

G Google 12 A Amazon 8 M Microsoft 6

The key insight is that a position is special only when both its row sum and column sum equal 1. The optimized approach pre-calculates all row and column sums to avoid redundant calculations. Time: O(m×n), Space: O(m+n)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Check	O(m²×n²)	O(1)	For each 1, check if it's the only 1 in its row and column
Pre-calculate Sums	O(m×n)	O(m+n)	First calculate row and column sums, then find special positions

Brute Force Check — Algorithm Steps

Iterate through each cell (i,j)
If mat[i][j] == 1, check entire row i and column j
Count if it's the only 1 in both row and column

Visualization

Tap to expand

Step-by-Step Walkthrough

Find 1

Located mat[0][1] = 1

Check Row

Row 0: [1,0,0] sum = 1 ✓

Check Column

Column 1: [0,1,1] sum = 2 ✗

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int** mat, int m, int n) {
    int count = 0;
    
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (mat[i][j] == 1) {
                // Check if this is the only 1 in row i
                int rowSum = 0;
                for (int k = 0; k < n; k++) {
                    rowSum += mat[i][k];
                }
                if (rowSum != 1) continue;
                
                // Check if this is the only 1 in column j
                int colSum = 0;
                for (int k = 0; k < m; k++) {
                    colSum += mat[k][j];
                }
                if (colSum == 1) {
                    count++;
                }
            }
        }
    }
    
    return count;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Simple parsing for small matrices
    int mat[50][50];
    int m = 0, n = 0;
    
    // Parse manually - assumes small input
    char* ptr = strchr(line, '[');
    ptr++; // Skip first [
    
    while (*ptr && *ptr != ']') {
        if (*ptr == '[') {
            ptr++;
            n = 0;
            while (*ptr && *ptr != ']') {
                if (*ptr >= '0' && *ptr <= '9') {
                    mat[m][n++] = *ptr - '0';
                }
                ptr++;
            }
            m++;
        }
        ptr++;
    }
    
    int result = solution((int**)mat, m, n);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(m²×n²)

For each cell we check entire row (n elements) and column (m elements)

⚠ Quadratic Growth

Space Complexity

O(1)

Only using constant extra variables

✓ Linear Space

28.4K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Check — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler