Special Positions in a Binary Matrix

To solve this problem, you need to count how many times each row and each column in the matrix has a 1, then iterate over the matrix again and for every cell that is 1, you check if its row and column counts are both 1. If they are, increment a special positions counter.

Here is the Python solution:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def numSpecial(self, mat: List[List[int]]) -> int:
        # Initialize a count for rows and columns
        rows = [0]*len(mat)
        cols = [0]*len(mat[0])

        # Count the number of 1's in each row and column
        for i in range(len(mat)):
            for j in range(len(mat[0])):
                if mat[i][j] == 1:
                    rows[i] += 1
                    cols[j] += 1

        # Initialize a counter for special positions
        special = 0

        # Iterate over the matrix again, checking for special positions
        for i in range(len(mat)):
            for j in range(len(mat[0])):
                if mat[i][j] == 1 and rows[i] == 1 and cols[j] == 1:
                    special += 1

        return special

This solution works in O(m*n) time and O(m + n) space, where m is the number of rows in the matrix and n is the number of columns.

Q&A

Why expected 3 in [[0,0,0,0,0],[1,0,0,0,0],[0,1,0,0,0],[0,0,1,0,0],[0,0,0,1,1]], if right answer is 4?

The matrix you’ve provided is:

In this case, the special positions (where the cell value is 1 and all other elements in its row and column are 0) are:

(1, 0) with value 1
(2, 1) with value 1
(3, 2) with value 1
(4, 3) with value 1

The position (4, 4) is not special because even though it has value 1, there is another 1 in its column at position (4, 3).

So, there are indeed 4 special positions, not 3. If the expected answer is 3, there might be a mistake in the problem statement or the test case.