algoadvance

Leetcode 1582. Special Positions in a Binary Matrix

Problem Statement

Given a m x n binary matrix mat, return the number of special positions in the matrix.

A position (i,j) is called special if mat[i][j] == 1 and all the other elements in row i and column j are 0.

Example 1:

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

Example 2:

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

Clarifying Questions

  1. What are the values in mat?
    • The values in mat are binary, i.e., either 0 or 1.
  2. What should be returned if there are no special positions?
    • If there are no special positions, return 0.
  3. Can mat be an empty matrix?
    • No, the problem guarantees that mat will have at least one row and one column.
  4. What are the constraints on m and n?
    • Constraints typically range between 1 <= m, n <= 100. This makes an O(m * n) solution feasible as it would result in a maximum of 10,000 operations.

Strategy

To solve this problem, we will:

  1. Iterate through the matrix to identify positions where mat[i][j] == 1.
  2. For each such position, verify that all other elements in row i and column j are 0.
  3. Count such special positions.

Matrices with values strictly within a limited range allow us to use nested loops to check rows and columns for verification.

Time Complexity

The time complexity for this solution is O(m * n) because:

  1. We iterate through each element in the matrix once.
  2. For every 1 found, we verify its row and column, making another pass of at most m + n elements.

This results in an overall complexity of O(m * n) + k * O(m + n), where k is the number of 1s, but given constraints, it simplifies to O(m * n).

Code

#include <vector>

class Solution {
public:
    int numSpecial(std::vector<std::vector<int>>& mat) {
        int m = mat.size();
        int n = mat[0].size();
        int count = 0;
        
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (mat[i][j] == 1) {
                    bool isSpecial = true;
                    
                    // Check the entire row
                    for (int k = 0; k < n; ++k) {
                        if (k != j && mat[i][k] == 1) {
                            isSpecial = false;
                            break;
                        }
                    }
                    
                    // Check the entire column
                    if (isSpecial) {
                        for (int k = 0; k < m; ++k) {
                            if (k != i && mat[k][j] == 1) {
                                isSpecial = false;
                                break;
                            }
                        }
                    }
                    
                    if (isSpecial) ++count;
                }
            }
        }
        
        return count;
    }
};

This approach iterates through each element and checks its row and column conditions to determine if it’s a special position or not.

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