LeetCode Solution: 1582. Special Positions in a Binary Matrix

Decoding LeetCode 1582: Finding the "Special" Ones in a Binary Matrix! ✨

Hey fellow coders and aspiring problem-solvers! 👋 Vansh2710 here, ready to dive into another fun LeetCode challenge. Today, we're tackling Problem 1582: Special Positions in a Binary Matrix. Don't let the name scare you; it's a great problem for beginners to practice matrix traversal and simple logic.

Think of it like finding hidden gems in a grid. Let's unearth them together!

---

What's the "Special" Deal? 🤔

The problem asks us to find "special positions" in a given m x n binary matrix (mat). A binary matrix just means all its elements are either 0 or 1.

So, what makes a position (i, j) special?

1. The element mat[i][j] must be 1. (It's got to be a gem, not an empty spot!)
2. Crucially, it must be the ONLY 1 in its entire row i AND the ONLY 1 in its entire column j.

Basically, a 1 is special if it's the lone wolf in its row and column.

Let's look at the examples to make it crystal clear:

Example 1:

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

Here, (1, 2) is special. mat[1][2] is 1.

• Row 1: [0,0,1] - only one 1. Perfect!
• Column 2: [0,1,0] - only one 1. Perfect! So, (1, 2) is special. No other 1s meet this condition.

Example 2:

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

In this diagonal matrix:

• (0, 0) is special (Row 0: [1,0,0], Col 0: [1,0,0])
• (1, 1) is special (Row 1: [0,1,0], Col 1: [0,1,0])
• (2, 2) is special (Row 2: [0,0,1], Col 2: [0,0,1]) Total 3 special positions!

---

The "Aha!" Moment: How to Spot a Lone Wolf? 💡

Imagine you're trying to find these special 1s. For each 1 you encounter, you'd have to:

1. Scan its entire row to ensure there are no other 1s.
2. Scan its entire column to ensure there are no other 1s.

This works, but it's a bit inefficient. If our matrix is 100x100, checking each 1 would involve scanning up to 100 elements horizontally and 100 elements vertically. If there are many 1s, this could lead to a lot of repeated scanning!

The "aha!" moment is realizing we can pre-calculate some information. What if we already knew how many 1s were in each row and each column?

If we had this information, checking if a 1 at (i, j) is special would be super fast:

• Is mat[i][j] equal to 1? (Of course, we only check 1s anyway!)
• Is the count of 1s in row i exactly 1?
• Is the count of 1s in column j exactly 1?

If all three conditions are true, bingo! We've found a special position.

---

Our Two-Pass Approach 🚶‍♂️🚶‍♀️

This leads us to a clear, two-pass strategy:

Step 1: Count 1s for Each Row and Column

1. Initialize two arrays:
   • rowCounts: An array to store the number of 1s in each row. Its size will be m (number of rows).
   • colCounts: An array to store the number of 1s in each column. Its size will be n (number of columns). Initialize all counts to 0.
2. Iterate through the entire mat matrix once.
   • For each cell mat[i][j]:
     • If mat[i][j] is 1, increment rowCounts[i] (because we found a 1 in row i) AND colCounts[j] (because we found a 1 in column j).

After this first pass, rowCounts[i] will tell us exactly how many 1s are in row i, and colCounts[j] will tell us how many 1s are in column j.

Step 2: Find the Special Positions

1. Initialize a variable specialPositionsCount = 0. This will store our final answer.
2. Iterate through the mat matrix again (this is our second pass).
   • For each cell mat[i][j]:
     • Check if mat[i][j] is 1. (We only care about actual 1s).
     • AND check if rowCounts[i] is 1. (Meaning it's the only 1 in its row).
     • AND check if colCounts[j] is 1. (Meaning it's the only 1 in its column).
     • If all three conditions are true, increment specialPositionsCount.
3. After this second pass, specialPositionsCount will hold the total number of special positions. Return this value!

---

The Code (C++) 🚀

Here's how our strategy translates into C++ code:

#include <vector> // Required for std::vector

class Solution {
public:
    int numSpecial(std::vector<std::vector<int>>& mat) {
        int m = mat.size();         // Number of rows
        int n = mat[0].size();      // Number of columns

        // Arrays to store counts of '1's in each row and column
        // Initialized to 0
        std::vector<int> rowCounts(m, 0);
        std::vector<int> colCounts(n, 0);

        // --- First Pass: Populate rowCounts and colCounts ---
        // Iterate through each cell of the matrix
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (mat[i][j] == 1) {
                    // If we find a '1', increment the count for its row and column
                    rowCounts[i]++;
                    colCounts[j]++;
                }
            }
        }

        // --- Second Pass: Find special positions ---
        int ans = 0; // Initialize count of special positions
        // Iterate through each cell of the matrix again
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                // Check if the current position (i, j) is special
                // 1. It must contain a '1'
                // 2. Its row must have exactly one '1'
                // 3. Its column must have exactly one '1'
                if (mat[i][j] == 1 && rowCounts[i] == 1 && colCounts[j] == 1) {
                    ans++; // If all conditions met, it's a special position!
                }
            }
        }
        return ans; // Return the total count
    }
};

---

Time & Space Complexity Analysis ⏱️📏

Let m be the number of rows and n be the number of columns in the matrix.

• Time Complexity: O(m * n)

  • We perform one full pass over the matrix to populate rowCounts and colCounts. This takes O(m * n) time.
  • We perform a second full pass over the matrix to identify special positions. This also takes O(m * n) time.
  • Total time complexity: O(m * n) + O(m * n) = O(m * n). Since m and n are at most 100, 100 * 100 = 10,000 operations per pass is very efficient!

• Space Complexity: O(m + n)

  • We use rowCounts array of size m.
  • We use colCounts array of size n.
  • Total space complexity: O(m + n). Again, for m, n <= 100, this is 100 + 100 = 200 integers, which is minimal.

---

Key Takeaways 🌟

1. Pre-computation for Efficiency: Sometimes, doing an initial pass to gather information can make subsequent checks much faster. Instead of repeatedly scanning rows/columns, we store the counts once.
2. Breaking Down the Problem: Complex conditions (like "only 1 in its row and column") can be broken into simpler, pre-calculated checks.
3. Matrix Traversal Basics: This problem reinforces how to iterate through 2D arrays and access elements by their (row, col) indices.
4. Auxiliary Data Structures: Using std::vector (or arrays in other languages) to store additional information (rowCounts, colCounts) is a common and powerful technique in algorithm design.

---

That's it for Special Positions in a Binary Matrix! I hope this breakdown helped you understand the problem and its elegant solution. Keep practicing, and you'll be crushing LeetCode problems in no time!

Happy coding! ✨

---

Author Account: Vansh2710
Time Published: 2026-05-13 22:46:26