Watch 10 video solutions for First Completely Painted Row or Column, a medium level problem involving Array, Hash Table, Matrix. This walkthrough by NeetCodeIO has 7,504 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
Example 1:
Input: arr = [1,3,4,2], mat = [[1,4],[2,3]] Output: 2 Explanation: 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 Explanation: The second column becomes fully painted at arr[3].
Constraints:
m == mat.lengthn = mat[i].lengtharr.length == m * n1 <= m, n <= 1051 <= m * n <= 1051 <= arr[i], mat[r][c] <= m * narr are unique.mat are unique.Problem Overview: You are given an array arr describing the order in which numbers are painted and a matrix mat containing those numbers. Each value in arr corresponds to a cell in the matrix. After every paint operation, you need to check whether an entire row or column has become fully painted. The task is to return the earliest index in arr where this happens.
Approach 1: Direct Mapping of Integers (O(m*n) time, O(m*n) space)
The key idea is to avoid repeatedly scanning the matrix. First build a mapping from matrix value to its coordinates using a hash map: value → (row, col). Then iterate through arr and locate the corresponding cell in constant time. Maintain two counters: rowCount[m] and colCount[n]. Each time you paint a cell, increment the corresponding row and column counters. If rowCount[r] == n or colCount[c] == m, the row or column is fully painted and you return the current index. This avoids matrix scans and keeps each operation O(1) after preprocessing. The approach works well because all matrix values are unique, making the mapping straightforward. This technique heavily relies on hash table lookups and efficient counting.
Approach 2: Tracking Painted Cells with Set Operations (O(m*n) time, O(m*n) space)
Another way is to explicitly track painted cells using sets. Maintain structures that store which cells in each row and column are painted, such as rowSets[r] and colSets[c]. As you iterate through arr, determine the cell location and insert the painted position into both sets. If the size of a row set reaches n or the size of a column set reaches m, that row or column is complete. This solution is straightforward to reason about and easy to implement in languages like JavaScript or C++ using Set containers. The tradeoff is higher constant overhead compared to simple counters.
Both approaches rely on quickly locating matrix coordinates for a value and updating row/column progress. Problems like this often appear in array and matrix categories where tracking incremental state is more efficient than recomputing results.
Recommended for interviews: The direct mapping approach with row and column counters is the expected solution. It demonstrates the ability to convert a matrix lookup into O(1) using a hash map and track progress with simple counters. Interviewers typically want to see you move from the naive idea of scanning rows and columns toward this constant‑time update strategy.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Direct Mapping with Row/Column Counters | O(m*n) | O(m*n) | Best general solution; constant-time updates after preprocessing |
| Tracking Painted Cells with Sets | O(m*n) | O(m*n) | Good when using languages with strong set abstractions |
| Naive Scan After Each Paint | O((m*n)*(m+n)) | O(1) | Conceptual starting point but inefficient for large matrices |