2661. First Completely Painted Row or Column

Problem Description

Given a 0-indexed integer array arr and an m x n integer matrix mat, the task is to process arr and paint the cells in mat based on the sequence provided in arr. Both arr and mat contain all integers in the range [1, m * n]. The process involves iterating over arr and painting the cell in mat that corresponds to each integer arr[i]. The goal is to determine the smallest index i at which either a whole row or a whole column in the matrix mat is completely painted. In other words, find the earliest point at which there's either a full row or a full column with all cells painted in the matrix.

Intuition

The solution revolves around tracking the painting progress in mat as we process each element in arr. The core thought is that we don't need to modify the matrix mat itself but can instead track the number of painted cells in each row and column with auxiliary data structures. This leads us to the idea of using two arrays row and col to maintain the count of painted cells for each respective row and column.

Since we need to find the positions in the matrix mat that correspond to the integers in arr, we can set up a hash table idx to map each number in the matrix to its coordinate (i, j). This allows us to quickly access the correct row and column to increment our counts.

With this setup, we iterate through arr, using the hashed mapping to find where arr[k] should be painted in mat. Each time we increment the counts in row and col, we check if either of them has reached the size of their respective dimension (n for rows, m for columns). If they have, it means that a complete row or column has been painted, and we can return the current index k as the result. This approach leads to an efficient solution since it avoids the need to modify the matrix directly and leverages fast lookups and updates in the auxiliary arrays.

Solution Approach

The implementation consists of several key steps that use algorithms and data structures to efficiently solve the problem.

Firstly, we create a hash table named idx to store the position of each element in the matrix mat. For each element in mat, we make an entry in idx where the key is the element mat[i][j] and the value is a tuple (i, j) representing its row and column indices.

1idx = {}
2for i in range(m):
3    for j in range(n):
4        idx[mat[i][j]] = (i, j)

This hash table allows us to have constant-time lookups for the position of any element later when we traverse arr.

Next, we define two arrays, row and col, with lengths corresponding to the number of rows m and the number of columns n in the matrix mat. These arrays are used to count how many cells have been painted in each row and column, respectively.

1row = [0] * m
2col = [0] * n

The main part of the solution involves iterating through the array arr. For each element arr[k], we get its corresponding position (i, j) in the matrix mat using the hash table idx.

1for k in range(len(arr)):
2    i, j = idx[arr[k]]

We increment the counts in row[i] and col[j] since arr[k] marks the cell at (i, j) as painted.

1row[i] += 1
2col[j] += 1

Then, we check if we have completed painting a row or a column. In other words, if either row[i] equals the number of columns n or col[j] equals the number of rows m, we have found our solution. At that point, we can return the current index k as this is the first index where a row or column is completely painted.

1if row[i] == n or col[j] == m:
2    return k

This approach efficiently determines the solution by using a hash table for fast lookups and simple arrays for counting, thus avoiding the need to make any modifications to the matrix mat itself.

Example Walkthrough

Let's illustrate the solution with a small example. Assume we are given the following matrix mat and array arr:

1mat = [
2    [1, 2],
3    [3, 4]
4]
5arr = [3, 1, 4, 2]

The matrix mat is of size 2 x 2, so m = 2 and n = 2. Our goal is to paint the cells in mat in the order specified by arr and find the smallest index i at which either a whole row or a whole column is completely painted.

Step 1: Create a hash table idx mapping matrix values to coordinates:

1idx = {1: (0, 0), 2: (0, 1), 3: (1, 0), 4: (1, 1)}

Step 2: Initialize counts for rows and columns:

1row = [0, 0]
2col = [0, 0]

Step 3: Start iterating through arr:

• For arr[0] = 3, the position in mat is idx[3] = (1, 0). Increment row[1] and col[0]. Now row = [0, 1], col = [1, 0].
• For arr[1] = 1, the position in mat is idx[1] = (0, 0). Increment row[0] and col[0]. Now row = [1, 1], col = [2, 0].

Since col[0] is now equal to the number of rows m, we've painted an entire column. The smallest index at this point is i = 1.

So, the earliest index in arr at which a whole row or column is painted is 1.

Solution Implementation

Time and Space Complexity

The time complexity of the given code can be broken down into two main parts. Firstly, populating the idx dictionary requires iterating through each element of the m x n matrix, which takes O(m * n) time. Secondly, iterating over the arr array with k elements and updating the row and col counts takes O(k) time. However, each element's index is accessed in constant time due to the dictionary. Therefore, the overall time complexity is the sum of both parts, O(m * n + k).

The space complexity involves the storage used by the idx dictionary, which holds one entry for each element in the m x n matrix, hence O(m * n) space. Additionally, the row and col arrays utilize O(m) and O(n) space, respectively. Consequently, the total space complexity is O(m * n) since O(m + n) is subsumed under O(m * n) when m and n are of the same order.

Learn more about how to find time and space complexity quickly using problem constraints.