Problem Description

You have an n x n grid (0-indexed) that contains buried artifacts. Each artifact is a rectangular region within the grid.

Input:

• n: The size of the grid (n × n)
• artifacts: A 2D array where each element [r1, c1, r2, c2] represents one artifact
  • (r1, c1) is the top-left corner of the artifact
  • (r2, c2) is the bottom-right corner of the artifact
• dig: A 2D array where each element [r, c] represents a cell you will excavate

Task: You need to excavate cells according to the dig array. When you excavate a cell, you remove the mud from it. If an artifact has all of its cells excavated (all mud removed), you can extract that artifact. Your goal is to count how many artifacts can be fully extracted.

Key Points:

• An artifact can only be extracted if ALL cells it occupies have been excavated
• No two artifacts overlap with each other
• Each artifact covers at most 4 cells
• All coordinates in dig are unique (no duplicate excavations)

Example: If an artifact occupies cells [1,1] to [2,2] (a 2×2 square), you must excavate all four cells (1,1), (1,2), (2,1), and (2,2) to extract this artifact.

The solution uses a hash set to store all excavated positions from the dig array. Then for each artifact, it checks if all cells within the artifact's rectangular region have been excavated. The function returns the count of artifacts that can be fully extracted.

Intuition

The core challenge is determining whether we've excavated all cells that belong to each artifact. Since we need to check if specific cells have been excavated, we need a fast way to look up whether a cell (r, c) has been dug or not.

A hash set is perfect for this - we can store all excavated positions in O(1) lookup time. We convert the dig list into a set of tuples {(i, j) for i, j in dig} for instant membership checking.

For each artifact defined by corners (r1, c1) and (r2, c2), we need to verify that every single cell within this rectangular region has been excavated. This means checking all cells where r ranges from r1 to r2 (inclusive) and c ranges from c1 to c2 (inclusive).

The key insight is that an artifact can only be extracted if 100% of its cells are excavated - even one missing cell means we cannot extract it. So for each artifact, we iterate through all its cells and check if they're all in our excavated set. If they are, we increment our count.

Since artifacts don't overlap and each covers at most 4 cells, we can independently check each artifact without worrying about complex interactions between them. The solution becomes straightforward: convert excavations to a set for fast lookup, then for each artifact, check if all its cells have been excavated.

Solution Approach

The solution uses a hash table approach to efficiently track excavated cells and check artifact extraction eligibility.

Step 1: Create a Hash Set of Excavated Cells

First, we convert the dig list into a set for O(1) lookup operations:

s = {(i, j) for i, j in dig}

This creates a set containing all excavated cell coordinates as tuples.

Step 2: Define a Helper Function to Check Individual Artifacts

The check function determines if a single artifact can be extracted:

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)
    )

This function:

• Unpacks the artifact boundaries [x1, y1, x2, y2]
• Iterates through all cells in the rectangular region from (x1, y1) to (x2, y2) inclusive
• Uses the all() function to verify every cell (x, y) in this region exists in our excavated set s
• Returns True only if all cells have been excavated

Step 3: Count Extractable Artifacts

Finally, we count how many artifacts can be extracted:

return sum(check(a) for a in artifacts)

This uses a generator expression with sum() to:

• Iterate through each artifact in the artifacts list
• Apply the check function to each artifact
• Sum up the boolean results (True = 1, False = 0) to get the total count

Time Complexity: O(m + k) where m is the number of excavated cells and k is the total number of cells covered by all artifacts (at most 4 cells per artifact).

Space Complexity: O(m) for storing the hash set of excavated positions.

Example Walkthrough

Let's walk through a concrete example to illustrate the solution approach.

Given:

• n = 3 (3×3 grid)
• artifacts = [[0,0,0,1], [1,1,2,2]]
  • Artifact 1: occupies cells (0,0) and (0,1)
  • Artifact 2: occupies cells (1,1), (1,2), (2,1), (2,2)
• dig = [[0,0], [0,1], [1,1], [2,1]]

Step 1: Create Hash Set of Excavated Cells

Convert dig into a set:

s = {(0,0), (0,1), (1,1), (2,1)}

Step 2: Check Each Artifact

For Artifact 1 [0,0,0,1]:

• Need to check cells from (0,0) to (0,1)
• Check (0,0): ✓ in set
• Check (0,1): ✓ in set
• All cells excavated → Can extract!

For Artifact 2 [1,1,2,2]:

• Need to check cells from (1,1) to (2,2)
• Check (1,1): ✓ in set
• Check (1,2): ✗ NOT in set
• Since (1,2) is missing, cannot extract this artifact

Step 3: Count Extractable Artifacts

• Artifact 1: Extractable (returns True → 1)
• Artifact 2: Not extractable (returns False → 0)
• Total: 1 + 0 = 1

Result: We can extract 1 artifact.

The key insight here is that even though we excavated 3 out of 4 cells for Artifact 2, we still cannot extract it because extraction requires ALL cells to be excavated. Only Artifact 1, with both of its cells excavated, can be successfully extracted.

Solution Implementation

Time and Space Complexity

Time Complexity: O(m + k)

The time complexity consists of two main parts:

• Creating the set s from the dig list takes O(k) time, where k is the number of excavated cells (length of dig)
• For each artifact in artifacts, the check function iterates through all cells within the artifact's rectangular area. In the worst case, an artifact could span the entire n×n grid, making each check O(n²). However, the total number of cells across all artifacts is bounded. Since we're checking membership in a set (which is O(1) per lookup), and the total cells checked across all artifacts is proportional to m (the total area covered by artifacts), the iteration through all artifacts takes O(m) time

Therefore, the total time complexity is O(m + k).

Space Complexity: O(k)

The space complexity is determined by:

• The set s which stores all excavated cells from dig, requiring O(k) space where k is the number of excavated cells
• The generator expression in the return statement doesn't create additional data structures, it evaluates lazily
• The check function uses only a constant amount of additional space for variables

Therefore, the space complexity is O(k).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Boundary Iteration

One of the most common mistakes is forgetting that the artifact boundaries are inclusive. When iterating through the cells of an artifact from (r1, c1) to (r2, c2), you must include the end coordinates.

Wrong approach:

# Missing the +1, which excludes the boundary cells
for row in range(row1, row2):  # ❌ Excludes row2
    for col in range(col1, col2):  # ❌ Excludes col2

Correct approach:

# Include +1 to make the range inclusive of the end coordinates
for row in range(row1, row2 + 1):  # ✓ Includes row2
    for col in range(col1, col2 + 1):  # ✓ Includes col2

2. Using List Instead of Set for Excavated Cells

Checking membership in a list has O(n) time complexity, which can significantly slow down the solution when there are many excavated cells.

Inefficient approach:

excavated_cells = dig  # ❌ Still a list
# or
excavated_cells = [(row, col) for row, col in dig]  # ❌ Still a list

# Checking membership in a list is O(n) for each lookup
if [row, col] in excavated_cells:  # Slow!

Efficient approach:

excavated_cells = {(row, col) for row, col in dig}  # ✓ Set with O(1) lookup

3. Tuple vs List Confusion in Set

When storing coordinates in a set, they must be hashable (immutable). Lists are not hashable, but tuples are.

Wrong approach:

excavated_cells = {[row, col] for row, col in dig}  # ❌ Lists are not hashable
# This will raise: TypeError: unhashable type: 'list'

Correct approach:

excavated_cells = {(row, col) for row, col in dig}  # ✓ Tuples are hashable

4. Early Return Optimization Mistake

When checking if an artifact is fully excavated, returning True as soon as you find one excavated cell is incorrect. You need ALL cells to be excavated.

Wrong logic:

def is_artifact_fully_excavated(artifact):
    row1, col1, row2, col2 = artifact
    for row in range(row1, row2 + 1):
        for col in range(col1, col2 + 1):
            if (row, col) in excavated_cells:
                return True  # ❌ Wrong! Just one cell isn't enough
    return False

Correct logic:

def is_artifact_fully_excavated(artifact):
    row1, col1, row2, col2 = artifact
    for row in range(row1, row2 + 1):
        for col in range(col1, col2 + 1):
            if (row, col) not in excavated_cells:
                return False  # ✓ Return False if ANY cell is not excavated
    return True  # ✓ Return True only if ALL cells are excavated