LeetCode Entry

2661. First Completely Painted Row or Column

20.01.2025 medium 2025 kotlin rust

Index of the first filled row/column in 2D matrix

2661. First Completely Painted Row or Column medium blog post substack youtube 1.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/870

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/columns
  • another 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 indexing
  • for 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);
    }