1582. Special Positions in a Binary Matrix

Problem concept

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

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

• Input: mat = [[1,0,0],[0,0,1],[1,0,0]]
• Output: 1
• Explanation: (1, 2) is a special position because mat[1][2] == 1 and all other elements in row 1 and column 2 are 0.

First temp

LeetCode - The World’s Leading Online Programming Learning Platform

Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

LeetCode

import numpy
class Solution:
    def numSpecial(self, mat: List[List[int]]) -> int:
        mat = numpy.array(mat)
        n,m = mat.shape
        mask = numpy.zeros_like(mat, dtype=bool)
        for row in range(n):
            for col in range(m):
                if mat[row,col] == 1:
                    mask[row,:] = False
                    mask[:,col] = False
                    if sum(mat[row,:]) == 1 and sum(mat[:,col]) == 1:
                        mask[row,col] = True
                        
        print(mask)
        return numpy.sum(mask)

First I used numpy and masking to check the exact position that is 1. Made numpy matrix for easy sum of mask. And in the double for loop of n,m, make all the row and col 'False' for the position except the position if the position is the only 1 of row and col.

As you can see, the rank of this code is sooooo low because of complexity is not good enough compared to other solutions. It need to be terminated when meet 1, not check all the row and col in the check part. And to lighten the code, it is better to not use numpy library.

Code from bard and chatgpt

class Solution:
  def numSpecial(self, mat: List[List[int]]) -> int:
    count = 0
    for row in range(len(mat)):
      for col in range(len(mat[0])):
        if mat[row][col] == 1:
          # Check if the element is the only 1 in its row and column
          is_special = True
          for i in range(len(mat[row])):
            if mat[row][i] == 1 and i != col:
              is_special = False
              break
          for j in range(len(mat)):
            if mat[j][col] == 1 and j != row:
              is_special = False
              break
          if is_special:
            count += 1
    return count

Bard with gemini gave me this solution. It is not using numpy, and instead of checking all elements in the row and column, the code stops iterating if it finds another 1, improving efficiency. Also the code uses a single loop to iterate through all elements, further improving time complexity. So the Time complexity becomes $O(n*m)$ for the double for loop. And Memory complexity becomes $O(1)$.

The is_special token is used as a flag whether the position is special or not. And not using other matrix like i created for report the possibility of the position to be included in result. And the way of using col and row for check is smooth as shit! love it...