Watch 7 video solutions for Count Artifacts That Can Be Extracted, a medium level problem involving Array, Hash Table, Simulation. This walkthrough by Bro Coders has 1,143 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |