We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Special Positions in a Binary Matrix

Number: 1704

Difficulty: Easy

Paid? No

Companies: Yahoo, Google

Problem Description

Given an m x n binary matrix mat, determine the number of special positions in mat. A position (i, j) is special if mat[i][j] == 1 and every other element in row i and column j is 0.

Key Insights

  • Pre-compute the sum of 1s in each row and each column.
  • A position with a 1 is special only if its corresponding row and column each have exactly one 1.
  • This method avoids nested loops checking full rows and columns repeatedly.

Space and Time Complexity

Time Complexity: O(m * n) where m is the number of rows and n is the number of columns. Space Complexity: O(m + n) for storing the row and column counts.

Solution

The solution involves two main passes over the matrix. First, iterate over the matrix to calculate the number of 1s for each row and each column using arrays (or lists). In the second pass, check every position; if it contains a 1 and its corresponding row and column counts are both 1, then it is a special position. The use of precomputed counts eliminates the need for redundant traversal of rows and columns, significantly improving efficiency. The key trick here is leveraging auxiliary arrays to store the frequency of 1s, thereby reducing the time complexity of checking each special position.

Code Solutions

# Python solution using precomputed row and column sums

def numSpecial(mat):
    m = len(mat)
    n = len(mat[0])
    
    # Precompute row sums and column sums
    row_sum = [0] * m
    col_sum = [0] * n
    
    # Count the number of 1s in each row and column
    for i in range(m):
        for j in range(n):
            row_sum[i] += mat[i][j]
            col_sum[j] += mat[i][j]
    
    special_count = 0
    # Identify special positions where the element is 1
    # and the corresponding row and column have exactly one 1
    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:
                special_count += 1
                
    return special_count

# Example usage:
matrix = [[1,0,0],[0,0,1],[1,0,0]]
print(numSpecial(matrix))  # Expected output: 1
← Back to All Questions