First Completely Painted Row or Column solution and explanation
Google
9 more videos on this problem
First Completely Painted Row or Column - Leetcode 2661 - PythonNeetCodeIO · 12:03 · 7K views
First Completely Painted Row or Column | 3 Approaches | Detailed | Leetcode 2661 | codestorywithMIKcodestorywithMIK · 39:47 · 7K views
2661. First Completely Painted Row or Column | Hash Maps | ArraysAryan Mittal · 8:19 · 1K views
Leetcode | 2661 First Completely Painted Row or Column | Java | Simple ApproachCakot Coding · 13:51 · 678 views
First Completely Painted Row or Column - Leetcode 2661 - PythonAlgorithms Casts · 11:36 · 561 views
Coding Interview Problem - First Completely Painted Row or ColumnKnapsack · 8:39 · 434 views
2661. First Completely Painted Row or Column (Leetcode Medium)Programming Live with Larry · 5:14 · 368 views
LeetCode 2661 First Completely Painted Row or Column | Hash Table | Adobe Interview QuestionCode Harmony · 20:09 · 106 views
LeetCode 2661 - First Completely Painted Row Or Column - PythonAlpha-Code · 7:08 · 61 views
LeetCode 2661 - First Completely painted row or columnPranav Sharma · 13:39 · 48 views
The problem
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.
def firstCompleteIndex(arr, mat):
m, n = len(mat), len(mat[0])
position_map = {mat[i][j]: (i, j) for i in range(m) for j in range(n)}
row_paint_count = [0] * m
col_paint_count = [0] * n
for i, num in enumerate(arr):
r, c = position_map[num]
row_paint_count[r] += 1
col_paint_count[c] += 1
if row_paint_count[r] == n or col_paint_count[c] == m:
return i
return -1import java.util.*;
public class Solution {
public int firstCompleteIndex(int[] arr, int[][] mat) {
int m = mat.length, n = mat[0].length;
Map<Integer, int[]> posMap = new HashMap<>();
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
posMap.put(mat[i][j], new int[]{i, j});
}
}
int[] rowCount = new int[m];
int[] colCount = new int[n];
for (int i = 0; i < arr.length; i++) {
int[] position = posMap.get(arr[i]);
int row = position[0], col = position[1];
rowCount[row]++;
colCount[col]++;
if (rowCount[row] == n || colCount[col] == m) {
return i;
}
}
return -1;
}
}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.
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.
#include <vector>
#include <unordered_map>
using namespace std;
int firstCompleteIndex(vector<int>& arr, vector<vector<int>>& mat) {
int m = mat.size(), n = mat[0].size();
unordered_map<int, pair<int, int>> posMap;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
posMap[mat[i][j]] = {i, j};
}
}
vector<int> rowPaintCount(m, 0), colPaintCount(n, 0);
for (int i = 0; i < arr.size(); ++i) {
auto [row, col] = posMap[arr[i]];
rowPaintCount[row]++;
colPaintCount[col]++;
if (rowPaintCount[row] == n || colPaintCount[col] == m) {
return i;
}
}
return -1;
}function firstCompleteIndex(arr, mat) {
const m = mat.length, n = mat[0].length;
const positionMap = new Map();
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
positionMap.set(mat[i][j], [i, j]);
}
}
const rowPaint = new Array(m).fill(0);
const colPaint = new Array(n).fill(0);
for (let i = 0; i < arr.length; i++) {
const [r, c] = positionMap.get(arr[i]);
rowPaint[r]++;
colPaint[c]++;
if (rowPaint[r] === n || colPaint[c] === m) {
return i;
}
}
return -1;
}This C++ solution uses an unordered_map to track positions of all integers from the matrix. It iterates through `arr`, updating counts for each matrix element. It checks if a row or column is completely updated at each index.
Time Complexity: O(m * n), similar to other implementations, with each map and iteration operation.
Space Complexity: O(m * n), needed to store position details and count storage.
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.
function firstCompleteIndex(arr: number[], mat: number[][]): number {
const m = mat.length;
const n = mat[0].length;
const idx: Map<number, number[]> = new Map();
for (let i = 0; i < m; ++i) {
for (let j = 0; j < n; ++j) {
idx.set(mat[i][j], [i, j]);
}
}
const row: number[] = Array(m).fill(0);
const col: number[] = Array(n).fill(0);
for (let k = 0; ; ++k) {
const [i, j] = idx.get(arr[k])!;
++row[i];
++col[j];
if (row[i] === n || col[j] === m) {
return k;
}
}
}func firstCompleteIndex(arr []int, mat [][]int) int {
m, n := len(mat), len(mat[0])
idx := map[int][2]int{}
for i := range mat {
for j := range mat[i] {
idx[mat[i][j]] = [2]int{i, j}
}
}
row := make([]int, m)
col := make([]int, n)
for k := 0; ; k++ {
x := idx[arr[k]]
i, j := x[0], x[1]
row[i]++
col[j]++
if row[i] == n || col[j] == m {
return k
}
}
}use std::collections::HashMap;
impl Solution {
pub fn first_complete_index(arr: Vec<i32>, mat: Vec<Vec<i32>>) -> i32 {
let m = mat.len();
let n = mat[0].len();
let mut idx = HashMap::new();
for i in 0..m {
for j in 0..n {
idx.insert(mat[i][j], [i, j]);
}
}
let mut row = vec![0; m];
let mut col = vec![0; n];
for k in 0..arr.len() {
let x = idx.get(&arr[k]).unwrap();
let i = x[0];
let j = x[1];
row[i] += 1;
col[j] += 1;
if row[i] == n || col[j] == m {
return k as i32;
}
}
-1
}
}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), similar to other implementations, with each map and iteration operation. Space Complexity: O(m * n), needed to store position details and count storage. |
| Hash Table + Array Counting | – |
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 |
Frequently asked questions
Is First Completely Painted Row or Column easy or hard?
The problem is rated Medium because the logic is simple but requires recognizing the need for a value-to-position mapping. Without that insight, repeatedly scanning rows or columns leads to inefficient solutions.
First Completely Painted Row or Column Python/Java solution
Python and Java implementations usually use a hash map (dictionary or HashMap) to store value-to-position mappings. Two arrays track row and column counts, and the algorithm iterates through arr updating these counters until a row or column becomes fully painted.
How to solve First Completely Painted Row or Column in O(n)?
Treat n as the total number of matrix cells (m*n). Precompute a hash map from matrix value to its coordinates. Iterate through arr once, update row and column counters, and check if any counter reaches the row or column length. Each step is O(1), so the entire algorithm runs in linear time relative to the number of cells.
What is the best approach for First Completely Painted Row or Column?
The best approach is direct mapping of matrix values to their coordinates combined with row and column counters. Build a hash map from value to (row, column), then iterate through arr and update rowCount and colCount. As soon as a row reaches n painted cells or a column reaches m painted cells, return that index. This runs in O(m*n) time with O(m*n) space.
Is First Completely Painted Row or Column asked at Google/Amazon/Meta?
Matrix and hash map tracking problems like this frequently appear in interviews at companies such as Amazon, Google, and Meta. The pattern of mapping values to coordinates and maintaining counters for rows and columns is a common interview technique.
What data structure is used in First Completely Painted Row or Column?
The core data structures are a hash map for mapping matrix values to coordinates and two arrays that track how many cells in each row and column are painted. Some implementations also use sets to track painted positions.
What is the time complexity of First Completely Painted Row or Column?
The optimal solution runs in O(m*n) time where m and n are the matrix dimensions. Building the value-to-position map takes O(m*n), and processing the painting order also takes O(m*n). Each update is constant time using row and column counters.