LeetCode Solutions Blog

Count Artifacts That Can Be Extracted

Number: 1312

Difficulty: Medium

Paid? No

Companies: IMC

Problem Description

Given an n x n grid with artifacts buried in rectangular regions defined by their top-left and bottom-right coordinates, and a list of excavated (dig) positions, determine how many artifacts can be extracted. An artifact can be extracted if and only if every cell it covers has been excavated.

Key Insights

Use a hash set to store all excavated cells for constant-time lookups.
For each artifact, check every cell within its rectangular boundary.
Since each artifact covers at most 4 cells, the per-artifact check is efficient.
No two artifacts overlap, so each artifact can be processed independently.

Space and Time Complexity

Time Complexity: O(A) where A is the number of artifacts, since each artifact inspects at most 4 cells. Space Complexity: O(D) for the set storing excavated cells, where D is the number of dig positions.

Solution

The solution converts the given dig positions into a hash set for quick access. For every artifact defined by its top-left (r1, c1) and bottom-right (r2, c2) coordinates, iterate over the cells in that rectangle. If all cells are found in the excavation set, count the artifact as extractable. This approach leverages the fact that each artifact spans only a few cells (at most 4), making the overall algorithm efficient, even for large grids.

Code Solutions

# Function to count the number of artifacts that can be extracted
def extractable_artifacts(n, artifacts, dig):
    # Create a set of excavated cells for fast lookup, store each cell as (row, col)
    excavated = {(r, c) for r, c in dig}
    
    # Counter for artifacts that can be extracted
    extractable_count = 0
    
    # Process each artifact
    for artifact in artifacts:
        r1, c1, r2, c2 = artifact  # Unpack artifact boundaries
        can_extract = True  # Assume artifact can be extracted
        
        # Check every cell in the artifact's defined rectangle
        for row in range(r1, r2 + 1):
            for col in range(c1, c2 + 1):
                if (row, col) not in excavated:  # If any cell is not excavated
                    can_extract = False  # Artifact cannot be extracted
                    break  # Exit inner loop
            if not can_extract:
                break  # Exit outer loop
        
        # If all cells are excavated, count the artifact as extractable
        if can_extract:
            extractable_count += 1
            
    return extractable_count

# Example usage:
n = 2
artifacts = [[0, 0, 0, 0], [0, 1, 1, 1]]
dig = [[0, 0], [0, 1]]
print(extractable_artifacts(n, artifacts, dig))  # Expected output: 1