2661. First Completely Painted Row or Column

• categories: Code, Interview Question, leetcode, Medium
• source: https://leetcode.com/problems/first-completely-painted-row-or-column
• topics: 2D Array, Hash Table

Description

You are given a 0-indexed integer array arr, and an m x n integer matrix mat. arr and mat both contain all the integers in the range [1, m * n].

Go through each index i in arr starting from index 0 and paint the cell in mat containing the integer arr[i].

Return the smallest index i at which either a row or a column will be completely painted in mat.

Idea

Inverse mapping

Code

class Solution:
    def firstCompleteIndex(self, arr: List[int], mat: List[List[int]]) -> int:
        N = len(mat)
        M = len(mat[0])
        row_counters = [M] * N
        col_counters = [N] * M
        indices = {}
        
        for i in range(N):
            for j in range(M):
                indices[mat[i][j]] = (i, j)
        
        for t, v in enumerate(arr):
            i, j = indices[v]
            row_counters[i] -= 1
            col_counters[j] -= 1
            if not row_counters[i] or not col_counters[j]:
                return t