#2661

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

First Completely Painted Row or Column

Find the first index where a row or column is completely painted in a matrix based on an array of integers.

Problem Statement

You are given a 0-indexed integer array arr and an m x n matrix mat. Each element in arr corresponds to a unique integer in the matrix mat, and they cover all integers from 1 to m * n. For each element in arr, you must mark the corresponding cell in mat as painted.

Your goal is to return the smallest index i such that after painting mat[arr[i]], either a row or a column in the matrix is fully painted. A row or column is fully painted when all of its cells have been marked from arr.

Examples

Example 1

Input: arr = [1,3,4,2], mat = [[1,4],[2,3]]

Output: 2

The moves are shown in order, and both the first row and second column of the matrix become fully painted at arr[2].

Example 2

Input: arr = [2,8,7,4,1,3,5,6,9], mat = [[3,2,5],[1,4,6],[8,7,9]]

Output: 3

The second column becomes fully painted at arr[3].

Constraints

m == mat.length
n = mat[i].length
arr.length == m * n
1 <= m, n <= 105
1 <= m * n <= 105
1 <= arr[i], mat[r][c] <= m * n
All the integers of arr are unique.
All the integers of mat are unique.

Solution Approach

Array Scanning with Hash Lookup

You can track the painted cells in each row and column using hash maps. For each element in arr, mark the corresponding matrix cell, then check if any row or column is fully painted by checking its corresponding counter. This allows for efficient tracking during each step.

Use of Frequency Arrays

A frequency array or hash table is essential to track the number of painted cells in each row and column. Each time a number from arr is processed, update the corresponding row and column counters. Once a row or column reaches its length, return the current index.

Efficient Matrix Traversal

Rather than repeatedly scanning the matrix, using a hash table for row and column counts lets you track the status of the painting in O(1) time per operation, thus optimizing the traversal and checking process.

Complexity Analysis

Metric	Value
Time	O(m \cdot n)
Space	O(k) \equiv O(m\cdot n)

Time complexity is O(m * n) since we process each element of arr, marking the corresponding matrix cell and updating the row and column counts. Space complexity is O(m * n) to store the frequency of each row and column in hash maps.

What Interviewers Usually Probe

Candidate demonstrates the use of a hash table for row/column tracking.
Candidate quickly identifies the optimization opportunity using a frequency array.
Candidate exhibits awareness of the constraints and chooses a solution that scales linearly with the matrix size.

Common Pitfalls or Variants

Common pitfalls

Not efficiently tracking the painted rows and columns, leading to repeated scanning of the matrix.
Failing to update row and column counters correctly, which might cause incorrect results.
Not considering edge cases where the matrix might already have some painted rows or columns before processing the array.

Follow-up variants

How would the solution change if the goal were to paint the entire matrix before checking for a full row or column?
What if instead of marking the matrix, you were to use a different data structure to track the positions?
How would you optimize this if the matrix is sparsely populated with numbers?

FAQ

How can I solve the First Completely Painted Row or Column problem?

The solution involves scanning the array while marking matrix cells and using frequency arrays to track row and column completion.

What is the optimal time complexity for the First Completely Painted Row or Column problem?

The optimal time complexity is O(m * n), where m is the number of rows and n is the number of columns in the matrix.

What pattern does the First Completely Painted Row or Column problem follow?

The problem follows the array scanning plus hash lookup pattern, where we use hash maps to track the painted rows and columns efficiently.

What happens if I do not efficiently track the rows and columns?

If you do not efficiently track the rows and columns, your solution will involve redundant matrix scans, which is inefficient.

How can GhostInterview assist with the First Completely Painted Row or Column problem?

GhostInterview helps by providing structured guidance on efficiently solving the problem using array scanning, hash lookup, and frequency tracking.

terminal

Solution

Solution 1: Hash Table + Array Counting

We use a hash table $idx$ to record the position of each element in the matrix $mat$, that is $idx[mat[i][j]] = (i, j)$, and define two arrays $row$ and $col$ to record the number of colored elements in each row and each column respectively.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

class Solution:
    def firstCompleteIndex(self, arr: List[int], mat: List[List[int]]) -> int:
        m, n = len(mat), len(mat[0])
        idx = {}
        for i in range(m):
            for j in range(n):
                idx[mat[i][j]] = (i, j)
        row = [0] * m
        col = [0] * n
        for k in range(len(arr)):
            i, j = idx[arr[k]]
            row[i] += 1
            col[j] += 1
            if row[i] == n or col[j] == m:
                return k

Continue Practicing

#2711 difference of number of distinct values on diagonals #2713 maximum strictly increasing cells in a matrix #2732 find a good subset of the matrix