Count Artifacts That Can Be Extracted solution and explanation
5 more videos on this problem
2201. Count Artifacts That Can Be Extracted || Leetcode Weekly Contest 284 || Leetcode 2201Bro Coders · 9:25 · 1K views
Count Artifacts That Can Be Extracted | Leetcode 2201 | Easy Matrix | Contest 284 | 🔥🔥Coding Decoded · 6:10 · 761 views
Leetcode Weekly 284 || 2nd Problem || Count Artifacts That Can Be Extracted || LeetCode: 2201codingMohan · 24:02 · 600 views
2201. Count Artifacts That Can Be Extracted (Leetcode Medium)Programming Live with Larry · 12:05 · 276 views
LeetCode 2201. Count Artifacts That Can Be Extracted | Medium | Algorithm Explained | C++Cherry Coding [IIT-G] · 18:44 · 141 views
LeetCode 2201: Count Artifacts That Can Be ExtractedAlitaCode · 29:28 · 2 views
The problem
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 theithartifact and(r2i, c2i)is the coordinate of the bottom-right cell of theithartifact.
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
4cells. - The entries of
digare unique.
Example 1:
Input: n = 2, artifacts = [[0,0,0,0],[0,1,1,1]], dig = [[0,0],[0,1]] Output: 1 Explanation: The different colors represent different artifacts. Excavated cells are labeled with a 'D' in the grid. There is 1 artifact that can be extracted, namely the red artifact. The blue artifact has one part in cell (1,1) which remains uncovered, so we cannot extract it. Thus, we return 1.
Example 2:
Input: n = 2, artifacts = [[0,0,0,0],[0,1,1,1]], dig = [[0,0],[0,1],[1,1]] Output: 2 Explanation: Both the red and blue artifacts have all parts uncovered (labeled with a 'D') and can be extracted, so we return 2.
Constraints:
1 <= n <= 10001 <= artifacts.length, dig.length <= min(n2, 105)artifacts[i].length == 4dig[i].length == 20 <= r1i, c1i, r2i, c2i, ri, ci <= n - 1r1i <= r2ic1i <= c2i- No two artifacts will overlap.
- The number of cells covered by an artifact is at most
4. - The entries of
digare unique.
Approach overview
Problem Overview: You are given an n x n grid with several rectangular artifacts. Each artifact occupies a group of cells defined by its top-left and bottom-right coordinates. You also receive a list of dig operations. An artifact can be extracted only if every cell it occupies has been dug. The task is to count how many artifacts are fully uncovered.
Approach 1: Set-Based Simulation (O(a * k + d) time, O(d) space)
Store every dug coordinate in a set for constant-time membership checks. For each artifact, iterate through all grid cells within its rectangle and verify that every cell exists in the dug set. If any cell is missing, the artifact cannot be extracted. Otherwise, increment the result. The key idea is that hash lookups make each cell check O(1), which keeps the overall simulation efficient. This approach works well because artifact sizes are usually small, so scanning their cells is cheap. It relies on fast membership checks using a hash table and straightforward iteration across coordinates.
Approach 2: Boolean Grid Simulation (O(n^2 + a * k) time, O(n^2) space)
Create a boolean grid dug[n][n] and mark every dig operation as true. Then iterate through each artifact and check all cells inside its rectangle. If every cell in the region is marked true, the artifact is fully uncovered and can be extracted. This approach avoids hash lookups and uses direct array indexing instead, which is extremely fast in languages like Java or C#. The tradeoff is higher memory usage since the entire grid is allocated. The technique is essentially a direct array-based simulation of the digging process.
Recommended for interviews: The set-based solution is typically the most flexible and language-agnostic approach. It demonstrates good use of hashing and keeps memory proportional to the number of digs instead of the full grid. The boolean grid approach is also acceptable and often simpler to implement in strongly typed languages. Showing the straightforward simulation first and then optimizing the membership checks with a hash set demonstrates strong problem-solving progression.
Approach 1: Set-Based Solution
This approach uses sets for efficient lookup. We first store all dig positions in a set. Then, for each artifact, we check all positions it covers to see if they are all present in the dig set. If so, we increment the counter for extractable artifacts.
def countArtifacts(n, artifacts, dig):
dig_set = set(map(tuple, dig))
count = 0
for r1, c1, r2, c2 in artifacts:
if all((r, c) in dig_set for r in range(r1, r2 + 1) for c in range(c1, c2 + 1)):
count += 1
return count#include <vector>
#include <unordered_set>
int countArtifacts(int n, std::vector<std::vector<int>>& artifacts, std::vector<std::vector<int>>& dig) {
std::unordered_set<int> digSet;
for (const auto& d : dig) {
digSet.insert(d[0] * n + d[1]);
}
int count = 0;
for (const auto& art : artifacts) {
bool canExtract = true;
for (int r = art[0]; r <= art[2] && canExtract; ++r) {
for (int c = art[1]; c <= art[3] && canExtract; ++c) {
if (digSet.find(r * n + c) == digSet.end()) {
canExtract = false;
}
}
}
if (canExtract) ++count;
}
return count;
}The code creates a set of excavated cells for quick lookup. It iterates through each artifact and checks if all its covered cells are in the dig set. If yes, the artifact can be extracted, and the counter is incremented.
Time Complexity: O(artifacts.length * 4), where 4 is the maximum number of cells an artifact can cover. This is efficient for large n, up to 1000.
Space Complexity: O(dig.length) for storing dig positions in a set.
Approach 2: Boolean Grid Solution
This approach uses a boolean grid to track excavated cells. It marks all dug positions on the grid and then checks each artifact to see if all its cells are marked. If so, the artifact can be extracted.
public int countArtifacts(int n, int[][] artifacts, int[][] dig) {
boolean[][] excavated = new boolean[n][n];
for (int[] d : dig) {
excavated[d[0]][d[1]] = true;
}
int count = 0;
for (int[] art : artifacts) {
boolean canExtract = true;
for (int r = art[0]; r <= art[2] && canExtract; r++) {
for (int c = art[1]; c <= art[3] && canExtract; c++) {
if (!excavated[r][c]) {
canExtract = false;
}
}
}
if (canExtract) {
count++;
}
}
return count;
}public int CountArtifacts(int n, int[][] artifacts, int[][] dig) {
bool[,] excavated = new bool[n, n];
foreach (var d in dig) {
excavated[d[0], d[1]] = true;
}
int count = 0;
foreach (var art in artifacts) {
bool canExtract = true;
for (int r = art[0]; r <= art[2] && canExtract; r++) {
for (int c = art[1]; c <= art[3] && canExtract; c++) {
if (!excavated[r, c]) {
canExtract = false;
}
}
}
if (canExtract) {
count++;
}
}
return count;
}We use a boolean 2D array to mark cells that have been excavated. For each artifact, we check if all its cells are excavated by iterating through its covered range.
Time Complexity: O(n^2 + artifacts.length * 4), where n^2 is for initializing the grid.
Space Complexity: O(n^2), for the excavated grid.
Approach 3: Hash Table
We can use a hash table s to record all the excavated cells, then traverse all the workpieces, and check whether all parts of the workpiece are in the hash table. If so, we can extract the workpiece, and the answer is increased by one.
The time complexity is O(m + k), and the space complexity is O(k). Here, m is the number of workpieces, and k is the number of excavated cells.
function digArtifacts(n: number, artifacts: number[][], dig: number[][]): number {
const s: Set<number> = new Set();
for (const [x, y] of dig) {
s.add(x * n + y);
}
let ans = 0;
const check = (a: number[]): number => {
const [x1, y1, x2, y2] = a;
for (let x = x1; x <= x2; ++x) {
for (let y = y1; y <= y2; ++y) {
if (!s.has(x * n + y)) {
return 0;
}
}
}
return 1;
};
for (const a of artifacts) {
ans += check(a);
}
return ans;
}func digArtifacts(n int, artifacts [][]int, dig [][]int) (ans int) {
s := map[int]bool{}
for _, p := range dig {
s[p[0]*n+p[1]] = true
}
check := func(a []int) int {
x1, y1, x2, y2 := a[0], a[1], a[2], a[3]
for x := x1; x <= x2; x++ {
for y := y1; y <= y2; y++ {
if !s[x*n+y] {
return 0
}
}
}
return 1
}
for _, a := range artifacts {
ans += check(a)
}
return
}use std::collections::HashSet;
impl Solution {
pub fn dig_artifacts(n: i32, artifacts: Vec<Vec<i32>>, dig: Vec<Vec<i32>>) -> i32 {
let mut s: HashSet<i32> = HashSet::new();
for p in dig {
s.insert(p[0] * n + p[1]);
}
let check = |a: &[i32]| -> i32 {
let x1 = a[0];
let y1 = a[1];
let x2 = a[2];
let y2 = a[3];
for x in x1..=x2 {
for y in y1..=y2 {
if !s.contains(&(x * n + y)) {
return 0;
}
}
}
1
};
let mut ans = 0;
for a in artifacts {
ans += check(&a);
}
ans
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Set-Based Solution | Time Complexity: O(artifacts.length * 4), where 4 is the maximum number of cells an artifact can cover. This is efficient for large n, up to 1000. |
| Boolean Grid Solution | Time Complexity: O(n^2 + artifacts.length * 4), where n^2 is for initializing the grid. |
| Hash Table | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Set-Based Simulation | O(a * k + d) | O(d) | General case when dig operations are sparse and you want memory proportional to digs |
| Boolean Grid Simulation | O(n^2 + a * k) | O(n^2) | When grid size is manageable and fast array indexing is preferred |
Frequently asked questions
Is Count Artifacts That Can Be Extracted easy or hard?
The problem is rated Medium because the logic is straightforward but requires careful handling of grid coordinates and artifact boundaries. Recognizing that the task is a simulation with constant-time membership checks makes the solution much simpler.
Count Artifacts That Can Be Extracted Python/Java solution
Python and C++ implementations often use a set of coordinate pairs to track dug cells. Java and C# solutions frequently use a boolean grid for faster indexing. Both implementations simulate checking each artifact and run in roughly O(a * k + d) time.
How to solve Count Artifacts That Can Be Extracted in O(n)?
Use a hash set to store every dug cell as a coordinate pair. For each artifact, iterate through its rectangle and verify that every cell exists in the set. Because each lookup is O(1), the algorithm scales linearly with the number of digs plus the total artifact cells inspected.
What is the best approach for Count Artifacts That Can Be Extracted?
The most practical approach uses a hash set to store all dug coordinates and then checks whether every cell of each artifact exists in the set. Each lookup is O(1), making the overall complexity roughly O(a * k + d), where a is the number of artifacts, k is the average cells per artifact, and d is the number of dig operations.
Is Count Artifacts That Can Be Extracted asked at Google/Amazon/Meta?
Problems involving grid simulation and hash-based lookups appear frequently in interviews at companies like Amazon and Google. Variations of grid coverage or excavation-style problems test understanding of arrays, hash sets, and simulation patterns.
What data structure is used in Count Artifacts That Can Be Extracted?
The most common data structure is a hash set that stores dug cell coordinates for constant-time membership checks. Another approach uses a boolean 2D array to mark dug positions and directly verify artifact cells.
What is the time complexity of Count Artifacts That Can Be Extracted?
The optimal simulation runs in O(a * k + d) time. Building the set of dig operations takes O(d), and checking all cells of each artifact requires O(a * k). Space complexity is O(d) when using a hash set to store dug cells.