Today’s Problem

https://leetcode.com/problems/first-completely-painted-row-or-column/description

Intuition

Do what the question ask.

Trick

We can store a count array for each row and column, so that we can know how many block painted in any row or column.

Approach

  1. Store the position of each number in the gird.
  2. Add one count in each row and column every print.
  3. If the print lead to a row or column that is all painted, then output i.

Complexity

  • Time complexity: $O(NM)$, N,M are the length and width of the grid.

  • Space complexity: $O(NM)$, we need to store the index of each number.

Code

class Solution:
    def firstCompleteIndex(self, arr: List[int], mat: List[List[int]]) -> int:
        col = [0] * (len(arr) + 1)
        row = [0] * (len(arr) + 1)
        for i in range(len(mat)):
            for j in range(len(mat[0])):
                col[mat[i][j]] = j
                row[mat[i][j]] = i
    
        cntR,cntC = [0] * len(mat), [0] * len(mat[0])

        for i, x in enumerate(arr):
            cntR[row[x]] += 1
            cntC[col[x]] += 1
            if cntR[row[x]] == len(mat[0]) or cntC[col[x]] == len(mat):
                return i
        
        return -1

image.png