algoadvance

You are given an m x n binary matrix mat of 1’s (representing soldiers) and 0’s (representing civilians). A position (i, j) is called a “special position” if mat[i][j] == 1 and all other elements in row i and column j are 0.

Return the number of special positions in mat.

Clarifying Questions

1. Input Size Limits: What are the constraints on the dimensions of the matrix?
   • Typical constraints are 1 <= m, n <= 100.
2. Matrix Elements: Can we assume all elements of the input matrix are either 0 or 1?
   • Yes, it is given in the problem that it is a binary matrix.

Strategy

To find the number of special positions, we need to:

1. Traverse the matrix to find all the ‘1’s.
2. For each ‘1’, check if all other elements in its row and column are ‘0’s.
3. If the above condition is satisfied, count it as a special position.

The plan is:

1. Iterate through each element in the matrix.
2. If the element is ‘1’, check its row and column for any other ‘1’s.
3. If neither the row nor the column contains another ‘1’, increment the special positions counter.

Code

def numSpecial(mat):
    m, n = len(mat), len(mat[0])
    special_positions = 0
    
    for i in range(m):
        for j in range(n):
            if mat[i][j] == 1:
                row_special = all(mat[i][k] == 0 for k in range(n) if k != j)
                col_special = all(mat[k][j] == 0 for k in range(m) if k != i)
                if row_special and col_special:
                    special_positions += 1
    
    return special_positions

# Example usage:
mat = [
    [1, 0, 0],
    [0, 0, 1],
    [1, 0, 0]
]
print(numSpecial(mat))  # Output should be 1

Time Complexity

• Initial Check for ‘1’s: We traverse the matrix once to find all the ‘1’s.
  • Complexity: O(m * n) where m is the number of rows and n is the number of columns.
• Checking Row and Column:
  • For each ‘1’ found, we check its corresponding row and column.
  • Complexity for each ‘1’: O(m + n)
  • In the worst case (when the matrix is filled with ‘1’s), this results in O((m * n) * (m + n)).

In summary:

• The worst-case time complexity is O((m * n) * (m + n)).

Space Complexity

• Auxiliary Space: We are not using any extra space except for counters and variables, which are O(1) in terms of space.
• Overall Space Complexity: O(1)

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?