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:
4 cells.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 <= 10001 <= artifacts.length, dig.length <= min(n2, 105)artifacts[i].length == 4dig[i].length == 20 <= r1i, c1i, r2i, c2i, ri, ci <= n - 1r1i <= r2ic1i <= c2i4.dig are unique.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.
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.
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.
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.
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.
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.
| 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 | — |
| 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 |
2201. Count Artifacts That Can Be Extracted || Leetcode Weekly Contest 284 || Leetcode 2201 • Bro Coders • 1,143 views views
Watch 6 more video solutions →Practice Count Artifacts That Can Be Extracted with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor