Code Implementation

class Solution:
    def numSpecial(self, mat):
        m, n = len(mat), len(mat[0])
        row_sum = [sum(row) for row in mat]
        col_sum = [sum(mat[i][j] for i in range(m)) for j in range(n)]
        count = 0
        for i in range(m):
            for j in range(n):
                if mat[i][j] == 1 and row_sum[i] == 1 and col_sum[j] == 1:
                    count += 1
        return count
      

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

class Solution {
    public int numSpecial(int[][] mat) {
        int m = mat.length, n = mat[0].length;
        int[] rowSum = new int[m];
        int[] colSum = new int[n];
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++) {
                rowSum[i] += mat[i][j];
                colSum[j] += mat[i][j];
            }
        int count = 0;
        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)
                    count++;
        return count;
    }
}
      

var numSpecial = function(mat) {
    const m = mat.length, n = mat[0].length;
    const rowSum = Array(m).fill(0), colSum = Array(n).fill(0);
    for (let i = 0; i < m; i++)
        for (let j = 0; j < n; j++) {
            rowSum[i] += mat[i][j];
            colSum[j] += mat[i][j];
        }
    let count = 0;
    for (let i = 0; i < m; i++)
        for (let j = 0; j < n; j++)
            if (mat[i][j] === 1 && rowSum[i] === 1 && colSum[j] === 1)
                count++;
    return count;
};
      

Problem Description

Given a binary matrix mat of size m x n, a special position is defined as a cell (i, j) such that mat[i][j] == 1 and all other elements in row i and column j are 0. In other words, a special position contains a 1 that is the only 1 in its entire row and column.

The task is to count the number of such special positions in the matrix and return this count.

• Each cell can only be counted once.
• All elements are either 0 or 1.
• You cannot reuse elements or count the same position more than once.

Thought Process

To solve this problem, the first idea is to check every cell in the matrix. For each 1, check if it's the only 1 in its row and column. This brute-force approach is straightforward but can be inefficient for large matrices.

To optimize, we can precompute the number of 1s in every row and every column. If a cell (i, j) contains a 1, and both the total number of 1s in row i and in column j is exactly 1, then that cell is a special position. This reduces repeated work and makes the solution more efficient.

The key insight is that by storing row and column sums, we can check the condition for a special position in constant time for each cell.

Solution Approach

• Step 1: Compute the sum of 1s in each row and each column. Store these in two arrays: one for row sums and one for column sums.
• Step 2: Iterate through every cell in the matrix. For each cell (i, j):
  • If mat[i][j] == 1 and both row_sum[i] == 1 and col_sum[j] == 1, then this cell is a special position.
• Step 3: Count all such special positions and return the total.

This approach is efficient because:

• Calculating row and column sums is O(mn), where m and n are the matrix dimensions.
• Checking each cell is also O(mn), but the check itself is constant time due to precomputed sums.
• No extra space is needed except two arrays for the sums.

Example Walkthrough

Consider the following matrix:

    mat = [
      [1, 0, 0],
      [0, 0, 1],
      [1, 0, 0]
    ]
  

• Compute row sums: [1, 1, 1]
• Compute column sums: [2, 0, 1]

Now, check each cell:

• (0,0): mat[0][0] == 1, row_sum[0] == 1, col_sum[0] == 2 → Not special (column has more than one 1)
• (0,1): mat[0][1] == 0 → Skip
• (0,2): mat[0][2] == 0 → Skip
• (1,0): mat[1][0] == 0 → Skip
• (1,1): mat[1][1] == 0 → Skip
• (1,2): mat[1][2] == 1, row_sum[1] == 1, col_sum[2] == 1 → Special position!
• (2,0): mat[2][0] == 1, row_sum[2] == 1, col_sum[0] == 2 → Not special
• (2,1): mat[2][1] == 0 → Skip
• (2,2): mat[2][2] == 0 → Skip

Only one special position is found: (1,2).

Time and Space Complexity

Brute-force approach:
For each 1 in the matrix, scan its entire row and column to check if it is the only 1. This results in O(mn(m + n)) time complexity, which is inefficient for large matrices.

Optimized approach:

• Computing row and column sums: O(mn)
• Checking each cell: O(mn)
• Total time complexity: O(mn)
• Space complexity: O(m + n) for the row and column sum arrays

Summary

The problem asks us to find all special positions in a binary matrix, where a special position is a 1 that is the only 1 in its row and column. By precomputing the number of 1s in each row and column, we can efficiently determine special positions in linear time. This approach avoids redundant checks and leverages simple array storage to achieve optimal performance.