#2201

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Count Artifacts That Can Be Extracted

Count the number of artifacts that can be extracted after excavating specified grid cells.

Problem Statement

You are given an n x n grid, and some artifacts are buried in it. Each artifact is represented by a rectangle within the grid, defined by the coordinates of its top-left and bottom-right corners. A dig operation is provided in the form of an array of coordinates indicating which cells of the grid are excavated. An artifact is considered fully extracted if all parts of it are excavated.

Your task is to determine how many artifacts can be fully extracted by checking if every cell of each artifact has been excavated. The challenge is to solve this efficiently, given the constraints on grid size and number of excavation operations.

Examples

Example 1

Input: n = 2, artifacts = [[0,0,0,0],[0,1,1,1]], dig = [[0,0],[0,1]]

Output: 1

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

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.

Solution Approach

Track Excavation with Hash Table

Use a hash table to quickly store and check which cells have been excavated. This eliminates the need to iterate through the entire dig array for every artifact, reducing complexity.

Artifact Coverage Check

For each artifact, check if all four corners (or less, depending on its size) are excavated by referring to the hash table. If any part is missing, the artifact cannot be extracted.

Efficient Grid Scanning

Instead of repeatedly scanning the grid, process the excavation coordinates once and mark cells as excavated in the hash table, then check each artifact's coordinates in constant time.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity primarily depends on the number of artifacts and excavation operations. Storing excavation cells in a hash table allows constant time checks per artifact, leading to an overall complexity of O(m + k), where m is the number of excavations and k is the number of artifacts.

What Interviewers Usually Probe

Can the candidate implement a solution that handles large grids efficiently?
Is the candidate able to use a hash table for constant time lookups?
Does the candidate handle edge cases, such as no artifacts or all artifacts being extractable?

Common Pitfalls or Variants

Common pitfalls

Using inefficient search methods for checking excavations, such as iterating over the entire dig array multiple times.
Failing to account for the scenario where artifacts are partially uncovered and cannot be extracted.
Not optimizing the solution to handle large grids and a high number of excavation operations.

Follow-up variants

What if the grid size increases significantly?
How would the problem change if artifacts can overlap?
Can this approach be adapted for a 3D grid?

FAQ

What is the primary pattern in the 'Count Artifacts That Can Be Extracted' problem?

The primary pattern is array scanning combined with hash table lookups, which allows for efficient checks of excavation status for each artifact.

How do you efficiently track excavation in the 'Count Artifacts That Can Be Extracted' problem?

By storing excavation coordinates in a hash table, you can quickly verify if all parts of an artifact are uncovered.

What is the time complexity of the solution for this problem?

The time complexity is O(m + k), where m is the number of dig operations and k is the number of artifacts.

How can I ensure my solution handles large grids?

Use a hash table to track excavated cells, ensuring constant time lookup and avoiding the need to scan the grid repeatedly.

Can artifacts overlap in this problem?

No, the problem specifies that no two artifacts will overlap.

terminal

Solution

Solution 1: 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.

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def digArtifacts(
        self, n: int, artifacts: List[List[int]], dig: List[List[int]]
    ) -> int:
        def check(a: List[int]) -> bool:
            x1, y1, x2, y2 = a
            return all(
                (x, y) in s for x in range(x1, x2 + 1) for y in range(y1, y2 + 1)
            )

        s = {(i, j) for i, j in dig}
        return sum(check(a) for a in artifacts)

Continue Practicing

#2154 keep multiplying found values by two #2295 replace elements in an array #2352 equal row and column pairs