Count Artifacts That Can Be Extracted

This problem can be solved by creating a mapping of cells to artifacts and then updating the uncovered parts of each artifact whenever a cell is excavated. If all parts of an artifact are uncovered, increment the count of extractable artifacts.

Python solution:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution:
    def digArtifacts(self, n: int, artifacts: List[List[int]], dig: List[List[int]]) -> int:
        cell_to_artifact = {}
        artifact_parts = {}
        for i, (r1, c1, r2, c2) in enumerate(artifacts):
            artifact_parts[i] = 0
            for r in range(r1, r2+1):
                for c in range(c1, c2+1):
                    cell_to_artifact[(r,c)] = i
                    artifact_parts[i] += 1
        excavated_artifacts = {i: 0 for i in range(len(artifacts))}
        count = 0
        for r, c in dig:
            if (r, c) in cell_to_artifact:
                artifact = cell_to_artifact[(r, c)]
                excavated_artifacts[artifact] += 1
                if excavated_artifacts[artifact] == artifact_parts[artifact]:
                    count += 1
        return count

In this solution, the cell_to_artifact dictionary maps each cell to the artifact it belongs to, and artifact_parts dictionary stores the number of parts of each artifact. The excavated_artifacts dictionary keeps track of the number of parts of each artifact that have been excavated. If all parts of an artifact are excavated, the count of extractable artifacts is incremented.

The time complexity of this solution is O(n^2) due to the nested loop over the grid cells for each artifact, and O(d) for the loop over the dig list, where d is the length of the dig list. Therefore, the total time complexity is O(n^2 + d). The space complexity is also O(n^2 + d) for storing the cell to artifact mapping and the lists of artifacts and digs.