algoadvance

Leetcode 1582. Special Positions in a Binary Matrix

Problem Statement

You are given an m x n binary matrix mat of 1’s (representing soldiers) and 0’s (representing civilians). A position (i, j) in the matrix is called special if:

1. mat[i][j] == 1, and
2. All other elements in row i and column j are 0.

Return the number of special positions in the matrix.

Example:

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

Output: 1

Explanation: 
(1, 2) is a special position because it is '1' and all other elements in the row and column are 0.

Clarifying Questions

1. Is the matrix guaranteed to be non-empty?
   • Yes, the matrix mat is guaranteed to have at least one element (m >= 1 and n >= 1).
2. Can the matrix have multiple special positions?
   • Yes, there can be multiple special positions.
3. Can a row or column have more than one soldier (1)?
   • Yes, but if a row or column has more than one soldier, they cannot be considered special positions.

Strategy

1. Iterate through the matrix: We’ll iterate through each element of the matrix.
2. Check conditions: For each element, if it is 1, we’ll check all other elements in its row and column.
3. Count special positions: Maintain a counter to keep track of elements that fulfill the special position criteria.

Code

public 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;
                        }
                    }
                    // Check column j
                    if (isSpecial) {
                        for (int k = 0; k < m; k++) {
                            if (k != i && mat[k][j] == 1) {
                                isSpecial = false;
                                break;
                            }
                        }
                    }
                    if (isSpecial) {
                        specialCount++;
                    }
                }
            }
        }
        return specialCount;
    }
}

Time Complexity

• Best Case: O(m * n) where m is the number of rows and n is the number of columns.
• We iterate through each element once and conduct row and column checks which can take O(n) and O(m) respectively. Therefore, it becomes O(m * n * (m + n)) in the worst case, but improvements can be made.

A possible optimization could involve precomputing the sum of rows and columns to quickly check if they contain another ‘1’.

Would you like to proceed with the optimized version?

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• 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?