🎯 Beginner-Friendly Guide 'Special Positions in a Binary Matrix' - Problem 1582 (C++, Python, JavaScript)

#programming #cpp #javascript #python

Scanning a grid for specific patterns is a fundamental skill in both competitive programming and real-world image processing. This problem challenges you to identify unique elements that stand out as the sole occupants of their respective rows and columns.

Problem Summary

You're given:
A 2D grid called a matrix, consisting of $m$ rows and $n$ columns, filled only with 0s and 1s.

Your goal:
Return the number of "special positions" in the matrix. A position $(i, j)$ is considered special if the value at that coordinate is 1, and all other elements in row $i$ and column $j$ are 0.

Intuition

To determine if a 1 is "special," we need to know how many other 1s exist in its specific row and its specific column. If the count of 1s in row $i$ is exactly 1, and the count of 1s in column $j$ is also exactly 1, then the 1 located at $(i, j)$ must be the only one there.

Instead of re-scanning the entire row and column for every single 1 we encounter, which would be inefficient, we can perform a "pre-computation" step. We use two auxiliary arrays to store the frequency of 1s for every row and every column. Once we have these counts, a second pass through the matrix allows us to verify each 1 in $O(1)$ constant time.

Walkthrough: Understanding the Examples

Consider a matrix like this:
[[1, 0, 0], [0, 0, 1], [1, 0, 0]]

Counting Phase:
Row counts: Row 0 has one 1. Row 1 has one 1. Row 2 has one 1. Result: rowOnes = [1, 1, 1].
Column counts: Column 0 has two 1s. Column 1 has zero 1s. Column 2 has one 1. Result: colOnes = [2, 0, 1].
Verification Phase:
Check mat[0][0]: It is a 1. Its row count is 1, but its column count is 2. Not special.
Check mat[1][2]: It is a 1. Its row count is 1 and its column count is 1. Special!
Check mat[2][0]: It is a 1. Its row count is 1, but its column count is 2. Not special.

The total count of special positions is 1.

Code Blocks

C++

class Solution {
public:
    int numSpecial(vector<vector<int>>& mat) {
        const int m = mat.size();
        const int n = mat[0].size();
        int ans = 0;
        vector<int> rowOnes(m, 0);
        vector<int> colOnes(n, 0);

        // Step 1: Pre-compute the number of 1s in each row and column
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (mat[i][j] == 1) {
                    ++rowOnes[i];
                    ++colOnes[j];
                }
            }
        }

        // Step 2: Identify positions that meet the special criteria
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (mat[i][j] == 1 && rowOnes[i] == 1 && colOnes[j] == 1) {
                    ++ans;
                }
            }
        }

        return ans;
    }
};

Python

class Solution:
    def numSpecial(self, mat: list[list[int]]) -> int:
        m, n = len(mat), len(mat[0])
        row_ones = [0] * m
        col_ones = [0] * n
        ans = 0

        # Step 1: Count 1s in rows and columns
        for r in range(m):
            for c in range(n):
                if mat[r][c] == 1:
                    row_ones[r] += 1
                    col_ones[c] += 1

        # Step 2: Check for special 1s
        for r in range(m):
            for c in range(n):
                if mat[r][c] == 1 and row_ones[r] == 1 and col_ones[c] == 1:
                    ans += 1

        return ans

JavaScript

/**
 * @param {number[][]} mat
 * @return {number}
 */
var numSpecial = function(mat) {
    const m = mat.length;
    const n = mat[0].length;
    const rowOnes = new Array(m).fill(0);
    const colOnes = new Array(n).fill(0);
    let ans = 0;

    // Step 1: Accumulate counts
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (mat[i][j] === 1) {
                rowOnes[i]++;
                colOnes[j]++;
            }
        }
    }

    // Step 2: Evaluate special conditions
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (mat[i][j] === 1 && rowOnes[i] === 1 && colOnes[j] === 1) {
                ans++;
            }
        }
    }

    return ans;
};

Key Takeaways

Space-Time Tradeoff: By using $O(m + n)$ extra space for our count arrays, we avoid a nested scan that would result in a much higher time complexity.
Frequency Arrays: Using arrays to "remember" counts is a powerful pattern that simplifies complex conditional logic.
Matrix Traversal: This problem reinforces how to navigate 2D data structures using nested loops efficiently.

Final Thoughts

This problem is an excellent introduction to optimization. In real-world software engineering, this logic is mirrored in database indexing or spreadsheet software, where we need to quickly identify unique records across different dimensions. In a search engine, you might use similar techniques to find unique keywords that only appear once in a specific document and nowhere else in a cluster. Mastering the ability to pre-calculate metadata about your data will make your algorithms significantly faster.

DEV Community