Skip to main content
Talentd

Count Artifacts That Can Be Extracted - Solution & Explanation

MediumArrayHash TableSimulation12 min read
Practice this problem

Problem Statement

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.

 

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 <= 1000
  • 1 <= artifacts.length, dig.length <= min(n2, 105)
  • artifacts[i].length == 4
  • dig[i].length == 2
  • 0 <= r1i, c1i, r2i, c2i, ri, ci <= n - 1
  • r1i <= r2i
  • c1i <= c2i
  • No two artifacts will overlap.
  • The number of cells covered by an artifact is at most 4.
  • The entries of dig are 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.

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.

Code

PythonC++

Python

C++

Complexity

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.

Try this approach in the editor →

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.

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.

Code

JavaC#

Java

C#

Complexity

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.

Try this approach in the editor →

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.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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.
Space Complexity: O(dig.length) for storing dig positions in a set.

Boolean Grid Solution

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.

Hash Table—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Set-Based SimulationO(a * k + d)O(d)General case when dig operations are sparse and you want memory proportional to digs
Boolean Grid SimulationO(n^2 + a * k)O(n^2)When grid size is manageable and fast array indexing is preferred

Video Solution

2201. Count Artifacts That Can Be Extracted || Leetcode Weekly Contest 284 || Leetcode 2201 • Bro Coders • 1,154 views views

Watch 5 more video solutions →

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.

Ready to solve this problem?

Practice Count Artifacts That Can Be Extracted with our built-in code editor and test cases.

Practice on FleetCode
Previous

Maximal Square