LeetCode 2201 - Count Artifacts That Can Be Extracted

This problem models an excavation process on a square n x n grid. Several rectangular artifacts are buried in the grid, and each artifact occupies one or more cells.

leetcodemediumarrayhash-tablesimulation

LeetCode Problem 2201

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Simulation

Solution

Problem Understanding

This problem models an excavation process on a square n x n grid. Several rectangular artifacts are buried in the grid, and each artifact occupies one or more cells. Every artifact is described by four integers:

  • (r1, c1) represents the top-left corner
  • (r2, c2) represents the bottom-right corner

This means the artifact occupies every cell inside that rectangular region.

You are also given a list of excavated cells in the array dig. Each entry [r, c] means that the cell (r, c) has been dug up and uncovered.

An artifact can only be extracted if every cell it occupies has been excavated. Your task is to count how many artifacts satisfy this condition.

The important detail is that artifacts never overlap. This guarantees that a cell belongs to at most one artifact, which simplifies the logic significantly.

The constraints tell us several important things:

  • n can be as large as 1000, so the grid may contain up to 1,000,000 cells.
  • artifacts.length and dig.length can each be as large as 100,000.
  • Each artifact covers at most 4 cells.

That last constraint is extremely important. Even though the grid can be very large, each artifact is tiny. This allows us to directly inspect all cells of an artifact without worrying about excessive work.

The input guarantees:

  • No overlapping artifacts
  • Unique dig positions
  • Valid coordinates
  • Rectangles are properly formed

Several edge cases are worth thinking about upfront.

An artifact may occupy a single cell. In that case, extracting it only requires that one cell to appear in dig.

Some artifacts may have only part of their area excavated. These must not be counted.

The grid itself may be large, but very sparsely excavated. A naive solution that scans the entire grid would waste enormous amounts of time and memory.

Another subtle case is when no artifact can be extracted at all. The algorithm should still correctly return 0.

Approaches

Brute Force Approach

A straightforward solution is to simulate the entire grid.

We could create a full n x n matrix representing excavated cells. Then, for every artifact, iterate through every cell inside its rectangle and verify whether all cells were excavated.

This approach is correct because it directly checks the condition required for extraction: every occupied cell must appear in dig.

However, this solution becomes inefficient when n is large. Constructing and scanning a massive grid wastes memory because most cells are irrelevant.

For example, when n = 1000, the grid contains one million cells. Even though this is manageable in some languages, it is unnecessary because artifacts only cover a tiny number of cells.

Optimal Approach

The key observation is that we never need to process the entire grid.

Instead, we only care about the excavated positions and the cells occupied by artifacts.

We can store every excavated cell in a hash set for constant time lookup. Then, for each artifact, we check whether every cell it occupies exists in the set.

Because each artifact covers at most 4 cells, this verification is extremely cheap.

This transforms the problem into efficient membership testing:

  • Convert dig into a hash set

  • For every artifact:

  • Enumerate its cells

  • Check whether all of them exist in the set

This approach avoids building the full grid and scales efficiently to the problem constraints.

Approach Time Complexity Space Complexity Notes
Brute Force O(n² + A × S) O(n²) Builds and scans a full grid
Optimal O(D + A × S) O(D) Uses a hash set for constant time lookup

Where:

  • A = number of artifacts
  • D = number of dug cells
  • S = maximum cells per artifact, at most 4

Since S is bounded by a constant, the optimal complexity effectively becomes linear.

Algorithm Walkthrough

Step 1: Store all excavated cells in a hash set

We first convert every coordinate in dig into a tuple and insert it into a hash set.

This allows constant time membership checks.

For example:

dig = [[0,0], [0,1]]

becomes:

dug_cells = {(0,0), (0,1)}

Using a hash set is important because we repeatedly need to answer:

"Has this cell been excavated?"

A set gives average O(1) lookup time.

Step 2: Process each artifact independently

Each artifact is defined by:

[r1, c1, r2, c2]

This means the artifact occupies every cell:

r1 <= r <= r2
c1 <= c <= c2

We iterate through all cells in this rectangle.

Step 3: Verify whether all cells were excavated

For every cell occupied by the artifact, we check whether it exists in the hash set.

If even one cell is missing, the artifact cannot be extracted.

If all cells are present, we increment the answer.

Step 4: Return the final count

After processing every artifact, the accumulated count represents the number of extractable artifacts.

Why it works

The algorithm directly checks the exact condition required for extraction.

An artifact is extractable if and only if every cell belonging to it has been excavated. The hash set accurately records all excavated cells, and we verify every occupied cell for every artifact.

Since artifacts do not overlap, each artifact can be evaluated independently. Therefore, counting all fully excavated artifacts produces the correct answer.

Python Solution

from typing import List

class Solution:
    def digArtifacts(self, n: int, artifacts: List[List[int]], dig: List[List[int]]) -> int:
        dug_cells = set()

        for row, col in dig:
            dug_cells.add((row, col))

        extracted_count = 0

        for r1, c1, r2, c2 in artifacts:
            can_extract = True

            for row in range(r1, r2 + 1):
                for col in range(c1, c2 + 1):
                    if (row, col) not in dug_cells:
                        can_extract = False
                        break

                if not can_extract:
                    break

            if can_extract:
                extracted_count += 1

        return extracted_count

The implementation begins by converting the dig array into a hash set named dug_cells. This gives constant time lookup when checking whether a cell has already been excavated.

Next, we iterate through every artifact. For each artifact, we enumerate all cells inside its rectangular boundaries.

The nested loops:

for row in range(r1, r2 + 1):
    for col in range(c1, c2 + 1):

visit every occupied cell.

If any cell is not present in dug_cells, the artifact cannot be extracted, so we immediately stop checking that artifact.

If all cells pass the membership test, we increment extracted_count.

Finally, we return the total number of fully excavated artifacts.

Go Solution

func digArtifacts(n int, artifacts [][]int, dig [][]int) int {
	dugCells := make(map[[2]int]bool)

	for _, cell := range dig {
		row, col := cell[0], cell[1]
		dugCells[[2]int{row, col}] = true
	}

	extractedCount := 0

	for _, artifact := range artifacts {
		r1, c1 := artifact[0], artifact[1]
		r2, c2 := artifact[2], artifact[3]

		canExtract := true

		for row := r1; row <= r2 && canExtract; row++ {
			for col := c1; col <= c2; col++ {
				if !dugCells[[2]int{row, col}] {
					canExtract = false
					break
				}
			}
		}

		if canExtract {
			extractedCount++
		}
	}

	return extractedCount
}

The Go implementation follows the same logic as the Python solution.

Instead of Python tuples, Go uses fixed-size arrays of length 2 as map keys:

map[[2]int]bool

This works because arrays are comparable in Go and can therefore be used as hash map keys.

The nested loops iterate through each artifact's rectangle exactly as in the Python version.

Go does not require any special handling for integer overflow because all values are well within the range of standard integers.

Worked Examples

Example 1

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

Step 1: Build the dug set

Dig Operation Set Contents
[0,0] {(0,0)}
[0,1] {(0,0), (0,1)}

Step 2: Check first artifact

Artifact:

[0,0,0,0]

Occupied cells:

Cell Excavated?
(0,0) Yes

All cells are excavated, so this artifact is extractable.

Current answer:

1

Step 3: Check second artifact

Artifact:

[0,1,1,1]

Occupied cells:

Cell Excavated?
(0,1) Yes
(1,1) No

Since (1,1) is missing, this artifact cannot be extracted.

Final answer:

1

Example 2

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

Step 1: Build the dug set

{(0,0), (0,1), (1,1)}

Step 2: Check first artifact

Cell Excavated?
(0,0) Yes

The first artifact is extractable.

Current answer:

1

Step 3: Check second artifact

Cell Excavated?
(0,1) Yes
(1,1) Yes

All cells are excavated.

Current answer:

2

Final result:

2

Complexity Analysis

Measure Complexity Explanation
Time O(D + A × S) Building the set takes O(D), checking artifacts takes O(A × S)
Space O(D) The hash set stores all dug cells

Here:

  • D is the number of excavated cells
  • A is the number of artifacts
  • S is the maximum number of cells per artifact

Because the problem guarantees that each artifact covers at most 4 cells, S is effectively constant. Therefore, the overall runtime behaves like linear time relative to the input size.

Test Cases

from typing import List

class Solution:
    def digArtifacts(self, n: int, artifacts: List[List[int]], dig: List[List[int]]) -> int:
        dug_cells = set()

        for row, col in dig:
            dug_cells.add((row, col))

        extracted_count = 0

        for r1, c1, r2, c2 in artifacts:
            can_extract = True

            for row in range(r1, r2 + 1):
                for col in range(c1, c2 + 1):
                    if (row, col) not in dug_cells:
                        can_extract = False
                        break

                if not can_extract:
                    break

            if can_extract:
                extracted_count += 1

        return extracted_count

solution = Solution()

# Example 1, only one artifact fully excavated
assert solution.digArtifacts(
    2,
    [[0, 0, 0, 0], [0, 1, 1, 1]],
    [[0, 0], [0, 1]]
) == 1

# Example 2, both artifacts fully excavated
assert solution.digArtifacts(
    2,
    [[0, 0, 0, 0], [0, 1, 1, 1]],
    [[0, 0], [0, 1], [1, 1]]
) == 2

# Single cell artifact not excavated
assert solution.digArtifacts(
    1,
    [[0, 0, 0, 0]],
    []
) == 0

# Single cell artifact excavated
assert solution.digArtifacts(
    1,
    [[0, 0, 0, 0]],
    [[0, 0]]
) == 1

# Multi-cell artifact partially excavated
assert solution.digArtifacts(
    3,
    [[0, 0, 1, 1]],
    [[0, 0], [0, 1], [1, 0]]
) == 0

# Multi-cell artifact fully excavated
assert solution.digArtifacts(
    3,
    [[0, 0, 1, 1]],
    [[0, 0], [0, 1], [1, 0], [1, 1]]
) == 1

# Multiple artifacts, mixed extraction status
assert solution.digArtifacts(
    4,
    [[0, 0, 0, 0], [1, 1, 2, 2], [3, 3, 3, 3]],
    [[0, 0], [1, 1], [1, 2], [2, 1], [2, 2]]
) == 2

# Large sparse grid
assert solution.digArtifacts(
    1000,
    [[999, 999, 999, 999]],
    [[999, 999]]
) == 1

# No artifacts fully excavated
assert solution.digArtifacts(
    3,
    [[0, 0, 0, 1], [1, 1, 2, 1]],
    [[0, 0], [1, 1]]
) == 0

# All artifacts fully excavated
assert solution.digArtifacts(
    3,
    [[0, 0, 0, 1], [1, 1, 2, 1]],
    [[0, 0], [0, 1], [1, 1], [2, 1]]
) == 2
Test Why
Example 1 Verifies partial excavation
Example 2 Verifies complete excavation
Single cell artifact not excavated Smallest failing case
Single cell artifact excavated Smallest successful case
Multi-cell artifact partially excavated Ensures incomplete artifacts are rejected
Multi-cell artifact fully excavated Ensures rectangular artifacts work correctly
Multiple artifacts, mixed extraction status Verifies independent artifact processing
Large sparse grid Confirms algorithm avoids full-grid dependency
No artifacts fully excavated Verifies zero result handling
All artifacts fully excavated Verifies maximum successful extraction

Edge Cases

One important edge case is a single-cell artifact. Since the artifact occupies exactly one coordinate, extraction depends entirely on whether that one coordinate appears in dig. Some implementations accidentally assume artifacts always span multiple cells, but this solution handles both uniformly because every artifact is processed through the same nested loop logic.

Another important case is a partially excavated multi-cell artifact. For example, a 2 x 2 artifact may have three excavated cells and one missing cell. A buggy implementation might incorrectly count it if it only tracks the number of excavated cells globally rather than checking the exact coordinates. This implementation avoids that issue by verifying every occupied cell individually.

A third edge case is a very large grid with very few excavated cells. Constructing an entire 1000 x 1000 matrix is unnecessary and inefficient in this scenario. The hash set approach only stores actual excavated coordinates, so memory usage depends on the number of digs rather than the total grid size.

Another subtle edge case occurs when no artifact can be extracted. Some implementations may accidentally initialize counters incorrectly or prematurely increment results before fully validating all cells. This implementation only increments the answer after every occupied coordinate has been confirmed present in the hash set.