First Completely Painted Row or Column - Solution & Explanation
Problem Statement
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 * n- All the integers of
arrare unique. - All the integers of
matare unique.
Approach Overview
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 1: Using Direct Mapping of Integers
This approach leverages a dictionary to map each integer to its corresponding position in the matrix. As we iterate over the array `arr`, we update the count of painted cells in the respective row and column. We keep track of the count of painted cells for each row and column, and as soon as any row or column reaches the total count of columns `n` or rows `m`, respectively, we know it is completely painted.
This code initializes a mapping of each integer to its matrix position. It has arrays to track the number of painted cells in each row and column. As it iterates through `arr`, it updates the paint counters. As soon as a counter equals the respective length of a row or column, the function returns the current index.
Complexity
Time Complexity: O(m * n), as we traverse each element of the matrix to create the position map and then process each element of `arr`.
Space Complexity: O(m * n), storing position information for every element in the matrix.
Approach 2: Tracking Painted Cells with Set Operations
This approach leverages sets to efficiently track and update the counts of painted cells in rows and columns. For each element processed from `arr`, we check and update the positions in the matrix. If any row or column set attains the size equal to the number of columns or rows, respectively, we determine that deletion criteria are satisfied.
In this JavaScript solution, a Map is used to store positions of matrix elements. Arrays keep track of painted cell counts for rows and columns. As elements of `arr` are processed, these counts are incremented, and checks are performed for full completion.
Code
JavaScript
C++
Complexity
Time Complexity: O(m * n), accounting for all map operations and checks.
Space Complexity: O(m * n), for storage in the map structure.
Approach 3: 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.
Traverse the array arr. For each element arr[k], we find its position (i, j) in the matrix mat, and then add row[i] and col[j] by one. If row[i] = n or col[j] = m, it means that the i-th row or the j-th column has been colored, so arr[k] is the element we are looking for, and we return k.
The time complexity is O(m times n), and the space complexity is O(m times n). Here m and n are the number of rows and columns of the matrix mat respectively.
Complexity Comparison
| Approach | Complexity |
|---|---|
| Using Direct Mapping of Integers | Time Complexity: O(m * n), as we traverse each element of the matrix to create the position map and then process each element of `arr`. Space Complexity: O(m * n), storing position information for every element in the matrix. |
| Tracking Painted Cells with Set Operations | Time Complexity: O(m * n), accounting for all map operations and checks. Space Complexity: O(m * n), for storage in the map structure. |
| Hash Table + Array Counting | — |
Detailed Complexity Analysis
| 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 |
Video Solution
First Completely Painted Row or Column - Leetcode 2661 - Python • NeetCodeIO • 7,581 views views
Watch 9 more video solutions →Frequently Asked Questions
Is First Completely Painted Row or Column easy or hard?
First Completely Painted Row or Column Python/Java solution
How to solve First Completely Painted Row or Column in O(n)?
What is the best approach for First Completely Painted Row or Column?
Is First Completely Painted Row or Column asked at Google/Amazon/Meta?
What data structure is used in First Completely Painted Row or Column?
What is the time complexity of First Completely Painted Row or Column?
Ready to solve this problem?
Practice First Completely Painted Row or Column with our built-in code editor and test cases.
Practice on FleetCode