Count Artifacts That Can Be Extracted

Problem Description

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.

Key Insights

• Each artifact occupies at most 4 cells in the grid.
• No two artifacts overlap, which simplifies the extraction process.
• The cells to be excavated are unique, ensuring no duplication in dig operations.
• A straightforward approach involves checking if all parts of an artifact are dug out.

Space and Time Complexity

Time Complexity: O(m + k), where m is the number of artifacts and k is the number of digs.
Space Complexity: O(m), for storing the state of each artifact.

Solution

To solve the problem, we can utilize a hash set to keep track of the excavated cells. For each artifact, we will check if all its constituent cells have been excavated. The steps involved in the solution are as follows:

1. Create a set to store excavated cells.
2. Iterate through the list of digs and add each excavated cell to the set.
3. For each artifact, check if all the cells it occupies are in the excavated set.
4. Count how many artifacts can be fully extracted based on the above checks.

Code Solutions