# 20.01.2025 [2661. First Completely Painted Row or Column]
Index of first filled row/column in 2D matrix #medium #counting
20.01.2025
2661. First Completely Painted Row or Column medium blog post substack youtube
Join me on Telegram
Problem TLDR
Index of the first filled row / column in 2D matrix #medium #counting
Intuition
Two ways of mapping:
remember positions (y, x) of nums in matrx, the scan the
arr
and count visited rows/columnsanother way is to remember indices of
arr
, then scan matrix horizontally and vertically to find a minimum of maximum row/column index
Approach
do
size + 1
to simplify indexingfor the first approach, we can store
y * width + x
instead of pairs
Complexity
Time complexity: $$O(nm)$$
Space complexity: $$O(nm)$$
Code
fun firstCompleteIndex(arr: IntArray, mat: Array<IntArray>): Int {
val ix = IntArray(arr.size + 1); for (i in arr.indices) ix[arr[i]] = i
return min(mat[0].indices.minOf { mat.maxOf { r -> ix[r[it]] }},
mat.minOf { r -> mat[0].indices.maxOf { ix[r[it]] }})
}
pub fn first_complete_index(arr: Vec<i32>, mat: Vec<Vec<i32>>) -> i32 {
let (mut ix, m, n) = (vec![0; arr.len() + 1], mat.len(), mat[0].len());
for i in 0..arr.len() { ix[arr[i] as usize] = i }
(0..n).map(|x| (0..m).map(|y| ix[mat[y][x] as usize]).max().unwrap()).min().unwrap().min(
(0..m).map(|y| (0..n).map(|x| ix[mat[y][x] as usize]).max().unwrap()).min().unwrap()) as _
}
int firstCompleteIndex(vector<int>& arr, vector<vector<int>>& mat) {
int m = size(mat), n = size(mat[0]); vector<int> ix(size(arr) + 1), r(m, 0), c(n, 0);
for (int y = 0; y < m; ++y) for (int x = 0; x < n; ++x) ix[mat[y][x]] = y * n + x;
for (int i = 0; i < size(arr); ++i)
if (++r[ix[arr[i]] / n] == n || ++c[ix[arr[i]] % n] == m) return i;
return size(arr);
}