First completely painted row or column

Array Hash Table Matrix

63.9% acceptance

Feb 25, 2026

1104

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 arr[i]. Return the smallest index i at which either a row or a column will be completely painted in mat.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn first_complete_index(arr: Vec<i32>, mat: Vec<Vec<i32>>) -> i32 {
    let m = mat.len();
    let n = mat[0].len();

    // Map value to (row, col)
    let mut pos = vec![(0usize, 0usize); m * n + 1];
    for r in 0..m {
      for c in 0..n {
        pos[mat[r][c] as usize] = (r, c);
      }
    }

    let mut row_count = vec![0usize; m];
    let mut col_count = vec![0usize; n];

    for (i, &v) in arr.iter().enumerate() {
      let (r, c) = pos[v as usize];
      row_count[r] += 1;
      col_count[c] += 1;
      if row_count[r] == n || col_count[c] == m {
        return i as i32;
      }
    }
    -1
  }
}