Count artifacts that can be extracted

Array Hash Table Simulation

57.1% acceptance

Feb 25, 2026

225

204

There is an n x n 0-indexed grid with some artifacts buried in it. You are given the integer n and a 0-indexed 2D integer array artifacts describing the positions of the rectangular artifacts where artifacts[i] = [r1i, c1i, r2i, c2i] denotes that the ith artifact is buried in the subgrid where: (r1i, c1i) is the coordinate of the top-left cell of the ith artifact and (r2i, c2i) is the coordinate of the bottom-right cell of the ith artifact. You will excavate some cells of the grid and remove all the mud from them. If the cell has a part of an artifact buried underneath, it will be uncovered. If all the parts of an artifact are uncovered, you can extract it. Given a 0-indexed 2D integer array dig where dig[i] = [ri, ci] indicates that you will excavate the cell (ri, ci), return the number of artifacts that you can extract. The test cases are generated such that: No two artifacts overlap. Each artifact only covers at most 4 cells. The entries of dig are unique.

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

use std::collections::HashSet;


impl Solution {
  pub fn dig_artifacts(_n: i32, artifacts: Vec<Vec<i32>>, dig: Vec<Vec<i32>>) -> i32 {
    let dug: HashSet<(i32, i32)> = dig.iter().map(|d| (d[0], d[1])).collect();
    let mut count = 0;
    for a in &artifacts {
      let (r1, c1, r2, c2) = (a[0], a[1], a[2], a[3]);
      let mut all_dug = true;
      'outer: for r in r1..=r2 {
        for c in c1..=c2 {
          if !dug.contains(&(r, c)) {
            all_dug = false;
            break 'outer;
          }
        }
      }
      if all_dug { count += 1; }
    }
    count
  }
}