# Special Positions in a Binary Matrix
**Difficulty:** EASY
[External](https://leetcode.com/problems/special-positions-in-a-binary-matrix)
Canonical: https://scaleengineer.com/dsa/problems/special-positions-in-a-binary-matrix
**Data structures:** Array, Matrix
---
## Problem
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**).

**Example 1:**

![](https://assets.glich.co/dsa/special-positions-in-a-binary-matrix/image0.jpg) 

**Input:** mat = [[1,0,0],[0,0,1],[1,0,0]]
**Output:** 1
**Explanation:** (1, 2) is a special position because mat[1][2] == 1 and all other elements in row 1 and column 2 are 0.

**Example 2:**

![](https://assets.glich.co/dsa/special-positions-in-a-binary-matrix/image1.jpg) 

**Input:** mat = [[1,0,0],[0,1,0],[0,0,1]]
**Output:** 3
**Explanation:** (0, 0), (1, 1) and (2, 2) are special positions.

**Constraints:**

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

# Approaches
## Brute Force Iteration
This approach involves iterating through every single cell of the matrix. For each cell that contains a `1`, we then perform a check to see if it qualifies as a "special" position. This check involves scanning the entire corresponding row and column to ensure all other elements are `0`.
**Time:** O(m * n * (m + n)). For each of the `m * n` cells, if it's a `1`, we scan its row (size `n`) and its column (size `m`). In the worst case, this leads to the specified complexity. · **Space:** O(1). We only use a few variables to keep track of the count and loop indices, which is constant extra space.
**Pros:** Simple to understand and implement.; Requires no extra space beyond the input matrix.
**Cons:** Highly inefficient due to redundant computations. The same row or column is scanned multiple times for different `1`s within them.
### Explanation
The algorithm proceeds as follows:
1.  Initialize a counter `specialCount` to 0.
2.  Iterate through each cell `(i, j)` of the matrix `mat`, where `i` is the row index and `j` is the column index.
3.  If `mat[i][j]` is `1`, we need to verify if it's a special position.
4.  To do this, we check two conditions:
    a.  **Row Check:** Iterate through all elements in row `i`. If we find another `1` (at a column `k` where `k != j`), then this position is not special.
    b.  **Column Check:** Iterate through all elements in column `j`. If we find another `1` (at a row `k` where `k != i`), then this position is not special.
5.  If both the row and column checks pass (meaning no other `1`s were found), it means `(i, j)` is a special position. Increment `specialCount`.
6.  After checking all cells, the value of `specialCount` is the result.

```java
class Solution {
    public int numSpecial(int[][] mat) {
        int m = mat.length;
        int n = mat[0].length;
        int specialCount = 0;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (mat[i][j] == 1) {
                    boolean isSpecial = true;
                    
                    // Check row i
                    for (int k = 0; k < n; k++) {
                        if (k != j && mat[i][k] == 1) {
                            isSpecial = false;
                            break;
                        }
                    }
                    
                    if (!isSpecial) continue;

                    // Check column j
                    for (int k = 0; k < m; k++) {
                        if (k != i && mat[k][j] == 1) {
                            isSpecial = false;
                            break;
                        }
                    }

                    if (isSpecial) {
                        specialCount++;
                    }
                }
            }
        }
        return specialCount;
    }
}
```
### Algorithm
*   Initialize `specialCount = 0`.
*   Get matrix dimensions `m` (rows) and `n` (columns).
*   For `i` from `0` to `m-1`:
    *   For `j` from `0` to `n-1`:
        *   If `mat[i][j] == 1`:
            *   Set a flag `isSpecial = true`.
            *   **Check the row:** For `k` from `0` to `n-1`:
                *   If `k != j` and `mat[i][k] == 1`, set `isSpecial = false` and break the loop.
            *   If `isSpecial` is `false`, continue to the next `j`.
            *   **Check the column:** For `k` from `0` to `m-1`:
                *   If `k != i` and `mat[k][j] == 1`, set `isSpecial = false` and break the loop.
            *   If `isSpecial` is still `true`, increment `specialCount`.
*   Return `specialCount`.

## Pre-computation of Row and Column Sums
This approach optimizes the brute-force method by avoiding redundant calculations. Instead of repeatedly scanning rows and columns, we first pre-calculate the sum of `1`s for every row and every column. A position `(i, j)` is special if and only if `mat[i][j] == 1`, the sum of its row is `1`, and the sum of its column is `1`.
**Time:** O(m * n). We traverse the matrix twice. The first traversal is for pre-computation, and the second is for counting. Both take `O(m * n)` time, which is a significant improvement. · **Space:** O(m + n). We use two additional arrays, `rowSum` and `colSum`, to store the sums, requiring space proportional to the number of rows plus the number of columns.
**Pros:** Much more efficient than the brute-force approach in terms of time.; The logic is clear and directly follows the definition of a special position.
**Cons:** Requires extra space for the sum arrays, proportional to the dimensions of the matrix.
### Explanation
The algorithm is divided into two main phases:
1.  **Pre-computation Phase:**
    *   Create two arrays: `rowSum` of size `m` (number of rows) and `colSum` of size `n` (number of columns), both initialized to zeros.
    *   Iterate through the entire matrix `mat` once. For each element `mat[i][j]`, if it's a `1`, increment `rowSum[i]` and `colSum[j]`. After this pass, `rowSum[i]` will hold the total number of `1`s in row `i`, and `colSum[j]` will hold the total number of `1`s in column `j`.

2.  **Counting Phase:**
    *   Initialize a counter `specialCount` to 0.
    *   Iterate through the matrix `mat` a second time.
    *   For each cell `(i, j)`, check if it meets all three conditions for being a special position:
        a.  `mat[i][j] == 1`
        b.  `rowSum[i] == 1`
        c.  `colSum[j] == 1`
    *   If all three conditions are true, increment `specialCount`.
    *   After iterating through all cells, return `specialCount`.

```java
class Solution {
    public int numSpecial(int[][] mat) {
        int m = mat.length;
        int n = mat[0].length;
        
        int[] rowSum = new int[m];
        int[] colSum = new int[n];
        
        // Pre-compute row and column sums
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (mat[i][j] == 1) {
                    rowSum[i]++;
                    colSum[j]++;
                }
            }
        }
        
        int specialCount = 0;
        // Count special positions
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (mat[i][j] == 1 && rowSum[i] == 1 && colSum[j] == 1) {
                    specialCount++;
                }
            }
        }
        
        return specialCount;
    }
}
```
### Algorithm
*   Get matrix dimensions `m` (rows) and `n` (columns).
*   Initialize `rowSum` array of size `m` with all zeros.
*   Initialize `colSum` array of size `n` with all zeros.
*   **Pre-computation Pass:**
    *   For `i` from `0` to `m-1`:
        *   For `j` from `0` to `n-1`:
            *   If `mat[i][j] == 1`:
                *   Increment `rowSum[i]`.
                *   Increment `colSum[j]`.
*   Initialize `specialCount = 0`.
*   **Counting Pass:**
    *   For `i` from `0` to `m-1`:
        *   For `j` from `0` to `n-1`:
            *   If `mat[i][j] == 1` and `rowSum[i] == 1` and `colSum[j] == 1`:
                *   Increment `specialCount`.
*   Return `specialCount`.

# Solutions
### Java

```java
class Solution {
public
  int numSpecial(int[][] mat) {
    int m = mat.length, n = mat[0].length;
    int[] r = new int[m];
    int[] c = new int[n];
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        r[i] += mat[i][j];
        c[j] += mat[i][j];
      }
    }
    int ans = 0;
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        if (mat[i][j] == 1 && r[i] == 1 && c[j] == 1) {
          ++ans;
        }
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int numSpecial(vector<vector<int>> &mat) {
    int m = mat.size(), n = mat[0].size();
    vector<int> r(m), c(n);
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        r[i] += mat[i][j];
        c[j] += mat[i][j];
      }
    }
    int ans = 0;
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        if (mat[i][j] == 1 && r[i] == 1 && c[j] == 1) {
          ++ans;
        }
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def numSpecial(self, mat: List[List[int]]) -> int: m, n = len(mat), len(mat[0]) r = [0] * m c = [0] * n for i, row in enumerate(mat): for j, v in enumerate(row): r[i] += v c[j] += v ans = 0 for i in range(m): for j in range(n): if mat[i][j] == 1 and r[i] == 1 and c[j] == 1: ans += 1 return ans

```