LeetCode 2661: First Completely Painted Row or Column (Earliest Paint Step Mapping)
LeetCode 2661MatrixHash MapToday we solve LeetCode 2661 - First Completely Painted Row or Column.
Source: https://leetcode.com/problems/first-completely-painted-row-or-column/
English
Problem Summary
We have a matrix mat containing values 1..m*n, each appearing once. We paint numbers in the order of arr. Return the first index i such that after painting arr[i], at least one whole row or one whole column is fully painted.
Key Insight
Do not scan the whole matrix for each painted value. Build a direct mapping from value to its cell position (r, c). Then every paint step updates exactly one row counter and one column counter. As soon as rowCount[r] == n or colCount[c] == m, we found the answer.
Algorithm
- Precompute pos[value] = (row, col) from mat.
- Keep rowCount[m] and colCount[n] initialized to 0.
- Iterate arr from left to right. For each value, find its (r, c), then increment rowCount[r] and colCount[c].
- If rowCount[r] == n or colCount[c] == m, return current index.
Complexity Analysis
Let matrix size be m x n.
Time: O(m*n).
Space: O(m*n).
Common Pitfalls
- Mixing up row length n and column length m when checking completion.
- Re-scanning rows/columns each step, which causes unnecessary overhead.
- Forgetting the matrix values are unique, which is what makes direct mapping valid.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public int firstCompleteIndex(int[] arr, int[][] mat) {
int m = mat.length, n = mat[0].length;
int[][] pos = new int[m * n + 1][2];
for (int r = 0; r < m; r++) {
for (int c = 0; c < n; c++) {
pos[mat[r][c]][0] = r;
pos[mat[r][c]][1] = c;
}
}
int[] rowCount = new int[m];
int[] colCount = new int[n];
for (int i = 0; i < arr.length; i++) {
int v = arr[i];
int r = pos[v][0], c = pos[v][1];
rowCount[r]++;
colCount[c]++;
if (rowCount[r] == n || colCount[c] == m) {
return i;
}
}
return -1;
}
}func firstCompleteIndex(arr []int, mat [][]int) int {
m, n := len(mat), len(mat[0])
pos := make([][2]int, m*n+1)
for r := 0; r < m; r++ {
for c := 0; c < n; c++ {
v := mat[r][c]
pos[v] = [2]int{r, c}
}
}
rowCount := make([]int, m)
colCount := make([]int, n)
for i, v := range arr {
r, c := pos[v][0], pos[v][1]
rowCount[r]++
colCount[c]++
if rowCount[r] == n || colCount[c] == m {
return i
}
}
return -1
}class Solution {
public:
int firstCompleteIndex(vector<int>& arr, vector<vector<int>>& mat) {
int m = mat.size(), n = mat[0].size();
vector<pair<int,int>> pos(m * n + 1);
for (int r = 0; r < m; ++r) {
for (int c = 0; c < n; ++c) {
pos[mat[r][c]] = {r, c};
}
}
vector<int> rowCount(m, 0), colCount(n, 0);
for (int i = 0; i < (int)arr.size(); ++i) {
int v = arr[i];
int r = pos[v].first, c = pos[v].second;
rowCount[r]++;
colCount[c]++;
if (rowCount[r] == n || colCount[c] == m) {
return i;
}
}
return -1;
}
};class Solution:
def firstCompleteIndex(self, arr: List[int], mat: List[List[int]]) -> int:
m, n = len(mat), len(mat[0])
pos = [None] * (m * n + 1)
for r in range(m):
for c in range(n):
pos[mat[r][c]] = (r, c)
row_count = [0] * m
col_count = [0] * n
for i, v in enumerate(arr):
r, c = pos[v]
row_count[r] += 1
col_count[c] += 1
if row_count[r] == n or col_count[c] == m:
return i
return -1var firstCompleteIndex = function(arr, mat) {
const m = mat.length, n = mat[0].length;
const pos = Array.from({ length: m * n + 1 }, () => [0, 0]);
for (let r = 0; r < m; r++) {
for (let c = 0; c < n; c++) {
const v = mat[r][c];
pos[v] = [r, c];
}
}
const rowCount = new Array(m).fill(0);
const colCount = new Array(n).fill(0);
for (let i = 0; i < arr.length; i++) {
const v = arr[i];
const [r, c] = pos[v];
rowCount[r]++;
colCount[c]++;
if (rowCount[r] === n || colCount[c] === m) {
return i;
}
}
return -1;
};中文
题目概述
给定一个包含 1..m*n 且互不重复的矩阵 mat，以及按顺序涂色的数组 arr。当涂到某个下标 i 时，如果存在某一整行或某一整列都已被涂色，就返回这个最早的 i。
核心思路
不要每次涂色都去全矩阵查位置。先建立 值 -> 坐标 映射，然后每一步只更新对应的 rowCount[r] 和 colCount[c]。一旦某行计数到 n 或某列计数到 m，该步就是答案。
算法步骤
- 遍历 mat，预处理 pos[value] = (r, c)。
- 维护行计数数组 rowCount 与列计数数组 colCount。
- 从左到右遍历 arr，找到每个值的位置并更新对应行列计数。
- 若 rowCount[r] == n 或 colCount[c] == m，立即返回当前下标。
复杂度分析
矩阵大小为 m x n。
时间复杂度：O(m*n)。
空间复杂度：O(m*n)。
常见陷阱
- 行满条件应比较 n，列满条件应比较 m，不要写反。
- 每一步重复扫描整行整列会拖慢效率。
- 忘记利用“矩阵值唯一”这一关键条件，导致实现复杂化。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public int firstCompleteIndex(int[] arr, int[][] mat) {
int m = mat.length, n = mat[0].length;
int[][] pos = new int[m * n + 1][2];
for (int r = 0; r < m; r++) {
for (int c = 0; c < n; c++) {
pos[mat[r][c]][0] = r;
pos[mat[r][c]][1] = c;
}
}
int[] rowCount = new int[m];
int[] colCount = new int[n];
for (int i = 0; i < arr.length; i++) {
int v = arr[i];
int r = pos[v][0], c = pos[v][1];
rowCount[r]++;
colCount[c]++;
if (rowCount[r] == n || colCount[c] == m) {
return i;
}
}
return -1;
}
}func firstCompleteIndex(arr []int, mat [][]int) int {
m, n := len(mat), len(mat[0])
pos := make([][2]int, m*n+1)
for r := 0; r < m; r++ {
for c := 0; c < n; c++ {
v := mat[r][c]
pos[v] = [2]int{r, c}
}
}
rowCount := make([]int, m)
colCount := make([]int, n)
for i, v := range arr {
r, c := pos[v][0], pos[v][1]
rowCount[r]++
colCount[c]++
if rowCount[r] == n || colCount[c] == m {
return i
}
}
return -1
}class Solution {
public:
int firstCompleteIndex(vector<int>& arr, vector<vector<int>>& mat) {
int m = mat.size(), n = mat[0].size();
vector<pair<int,int>> pos(m * n + 1);
for (int r = 0; r < m; ++r) {
for (int c = 0; c < n; ++c) {
pos[mat[r][c]] = {r, c};
}
}
vector<int> rowCount(m, 0), colCount(n, 0);
for (int i = 0; i < (int)arr.size(); ++i) {
int v = arr[i];
int r = pos[v].first, c = pos[v].second;
rowCount[r]++;
colCount[c]++;
if (rowCount[r] == n || colCount[c] == m) {
return i;
}
}
return -1;
}
};class Solution:
def firstCompleteIndex(self, arr: List[int], mat: List[List[int]]) -> int:
m, n = len(mat), len(mat[0])
pos = [None] * (m * n + 1)
for r in range(m):
for c in range(n):
pos[mat[r][c]] = (r, c)
row_count = [0] * m
col_count = [0] * n
for i, v in enumerate(arr):
r, c = pos[v]
row_count[r] += 1
col_count[c] += 1
if row_count[r] == n or col_count[c] == m:
return i
return -1var firstCompleteIndex = function(arr, mat) {
const m = mat.length, n = mat[0].length;
const pos = Array.from({ length: m * n + 1 }, () => [0, 0]);
for (let r = 0; r < m; r++) {
for (let c = 0; c < n; c++) {
const v = mat[r][c];
pos[v] = [r, c];
}
}
const rowCount = new Array(m).fill(0);
const colCount = new Array(n).fill(0);
for (let i = 0; i < arr.length; i++) {
const v = arr[i];
const [r, c] = pos[v];
rowCount[r]++;
colCount[c]++;
if (rowCount[r] === n || colCount[c] === m) {
return i;
}
}
return -1;
};
Comments