# Count Artifacts That Can Be Extracted
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/count-artifacts-that-can-be-extracted)
Canonical: https://scaleengineer.com/dsa/problems/count-artifacts-that-can-be-extracted
**Data structures:** Array, Hash Table
---
## Problem
There is an `n x n` **0-indexed** grid with some artifacts buried in it. You are given the integer `n` and a **0-indexed** 2D integer array `artifacts` describing the positions of the rectangular artifacts where `artifacts[i] = [r1i, c1i, r2i, c2i]` denotes that the `ith` artifact is buried in the subgrid where:

* `(r1i, c1i)` is the coordinate of the **top-left** cell of the `ith` artifact and
* `(r2i, c2i)` is the coordinate of the **bottom-right** cell of the `ith` artifact.

You will excavate some cells of the grid and remove all the mud from them. If the cell has a part of an artifact buried underneath, it will be uncovered. If all the parts of an artifact are uncovered, you can extract it.

Given a **0-indexed** 2D integer array `dig` where `dig[i] = [ri, ci]` indicates that you will excavate the cell `(ri, ci)`, return _the number of artifacts that you can extract_.

The test cases are generated such that:

* No two artifacts overlap.
* Each artifact only covers at most `4` cells.
* The entries of `dig` are unique.

**Example 1:**

![](https://assets.glich.co/dsa/count-artifacts-that-can-be-extracted/image0.jpg) 

**Input:** n = 2, artifacts = [[0,0,0,0],[0,1,1,1]], dig = [[0,0],[0,1]]
**Output:** 1
**Explanation:** 
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:**

![](https://assets.glich.co/dsa/count-artifacts-that-can-be-extracted/image1.jpg) 

**Input:** n = 2, artifacts = [[0,0,0,0],[0,1,1,1]], dig = [[0,0],[0,1],[1,1]]
**Output:** 2
**Explanation:** 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.

# Approaches
## Brute Force Iteration
This approach directly translates the problem statement into code. We iterate through each artifact. For each artifact, we determine all the grid cells it occupies. Then, for each of these cells, we scan the entire `dig` array to see if the cell has been excavated. If all cells of an artifact are found in the `dig` array, we count it as extractable.
**Time:** O(A * S * D), where A is `artifacts.length`, S is the number of cells per artifact (at most 4), and D is `dig.length`. This simplifies to O(A * D). · **Space:** O(1) extra space.
**Pros:** Simple to understand and implement.; Requires no extra space.
**Cons:** Extremely inefficient due to nested loops.; Will result in a 'Time Limit Exceeded' error for large inputs.
### Explanation
The brute-force method checks every artifact one by one. For an artifact defined by `[r1, c1, r2, c2]`, it iterates through all cells `(r, c)` where `r1 <= r <= r2` and `c1 <= c <= c2`. For each such cell, it iterates through the `dig` array to find a match. This nested iteration makes the approach very slow.

```java
class Solution {
    public int countArtifacts(int n, int[][] artifacts, int[][] dig) {
        int extractedCount = 0;
        for (int[] artifact : artifacts) {
            int r1 = artifact[0], c1 = artifact[1], r2 = artifact[2], c2 = artifact[3];
            boolean allDug = true;
            
            // Iterate over all cells of the artifact
            for (int r = r1; r <= r2; r++) {
                for (int c = c1; c <= c2; c++) {
                    boolean found = false;
                    // Search for the cell in the dig array
                    for (int[] digCell : dig) {
                        if (digCell[0] == r && digCell[1] == c) {
                            found = true;
                            break;
                        }
                    }
                    if (!found) {
                        allDug = false;
                        break;
                    }
                }
                if (!allDug) {
                    break;
                }
            }
            
            if (allDug) {
                extractedCount++;
            }
        }
        return extractedCount;
    }
}
```
### Algorithm
- Initialize a counter for extracted artifacts to zero.
- Iterate through each artifact in the `artifacts` list.
- For each artifact, generate a list of all cells it occupies.
- For each cell of the artifact, perform a linear scan through the entire `dig` array to check if it has been excavated.
- If a cell is not found in `dig`, the artifact cannot be extracted; stop checking this artifact and move to the next.
- If all cells of an artifact are found in `dig`, increment the counter.
- Return the final count.

## Grid Marking
A significant improvement over brute force is to avoid repeatedly scanning the `dig` array. We can use a 2D grid, the same size as the excavation area, to mark which cells have been dug. We first iterate through the `dig` array and mark the corresponding cells in our grid. Then, for each artifact, we check this grid to see if all its cells are marked as dug.
**Time:** O(n^2 + D + A), where `n` is the grid dimension, `D` is `dig.length`, and `A` is `artifacts.length`. The `n^2` term comes from initializing the grid. · **Space:** O(n^2) to store the `dugGrid`.
**Pros:** Much faster than the brute-force approach.; Conceptually simple, mapping directly to the grid-based nature of the problem.
**Cons:** High space complexity, O(n^2), which can be large.; Time complexity includes an O(n^2) term for initialization, which can be the bottleneck if n is large.
### Explanation
This method pre-processes the dug locations. By creating an `n x n` boolean grid, we can mark all excavated cells in O(D) time, where D is the number of dug cells. After this one-time setup, checking if a cell is dug becomes an O(1) operation. We then iterate through each artifact and check its constituent cells against this grid. The main drawback is the space and time required to handle the grid itself, which depends on `n^2`.

```java
class Solution {
    public int countArtifacts(int n, int[][] artifacts, int[][] dig) {
        boolean[][] dugGrid = new boolean[n][n];
        for (int[] d : dig) {
            dugGrid[d[0]][d[1]] = true;
        }
        
        int extractedCount = 0;
        for (int[] artifact : artifacts) {
            int r1 = artifact[0], c1 = artifact[1], r2 = artifact[2], c2 = artifact[3];
            boolean isExtractable = true;
            
            for (int r = r1; r <= r2; r++) {
                for (int c = c1; c <= c2; c++) {
                    if (!dugGrid[r][c]) {
                        isExtractable = false;
                        break;
                    }
                }
                if (!isExtractable) {
                    break;
                }
            }
            
            if (isExtractable) {
                extractedCount++;
            }
        }
        return extractedCount;
    }
}
```
### Algorithm
- Create a boolean 2D array `dugGrid` of size `n x n`, initialized to `false`.
- Iterate through each cell `[r, c]` in `dig` and set `dugGrid[r][c] = true`.
- Initialize `extractedCount = 0`.
- For each `artifact` in `artifacts`:
  - Assume the artifact is extractable (`isExtractable = true`).
  - Iterate through all cells of the artifact.
  - For each cell, check if it's marked as true in `dugGrid`.
  - If any cell is not marked, set `isExtractable = false` and break.
- If `isExtractable` is still true after checking all its cells, increment `extractedCount`.
- Return `extractedCount`.

## Optimized Check using Hash Set
This approach improves upon the grid marking method by reducing space complexity when the number of dug cells `D` is much smaller than `n^2`. Instead of a full 2D grid, we use a hash set to store the coordinates of the dug cells. This allows for average O(1) time complexity for checking if a cell has been excavated.
**Time:** O(D + A), where D is `dig.length` and A is `artifacts.length`. This is because populating the set takes O(D) and checking all artifacts takes O(A) as each artifact has at most 4 cells. · **Space:** O(D), where D is the number of dug cells, to store them in the hash set.
**Pros:** Optimal time complexity.; Space-efficient when the number of dug cells is much smaller than n*n.
**Cons:** Uses O(D) space, which could be large if there are many dug cells.; Hashing can have a small constant-time overhead compared to direct array access.
### Explanation
By using a hash set, we only store the locations that have been dug, which is more memory-efficient than an `n x n` grid if `D` is significantly smaller than `n^2`. The process involves two main stages: first, populating the hash set with all dug cells, and second, iterating through each artifact to verify if all its parts are in the set. The check for each part of an artifact is an average O(1) lookup in the hash set.

```java
import java.util.HashSet;
import java.util.Set;

class Solution {
    public int countArtifacts(int n, int[][] artifacts, int[][] dig) {
        Set<Integer> dugCells = new HashSet<>();
        for (int[] d : dig) {
            dugCells.add(d[0] * n + d[1]);
        }
        
        int extractedCount = 0;
        for (int[] artifact : artifacts) {
            int r1 = artifact[0], c1 = artifact[1], r2 = artifact[2], c2 = artifact[3];
            boolean isExtractable = true;
            
            for (int r = r1; r <= r2; r++) {
                for (int c = c1; c <= c2; c++) {
                    if (!dugCells.contains(r * n + c)) {
                        isExtractable = false;
                        break;
                    }
                }
                if (!isExtractable) {
                    break;
                }
            }
            
            if (isExtractable) {
                extractedCount++;
            }
        }
        return extractedCount;
    }
}
```
### Algorithm
- Create a `HashSet` to store the coordinates of dug cells.
- To store a 2D coordinate `(r, c)`, encode it into a single integer, e.g., `r * n + c`.
- Iterate through the `dig` array and add the encoded coordinate of each cell to the hash set.
- Initialize `extractedCount = 0`.
- For each `artifact`:
  - Assume it's extractable (`isExtractable = true`).
  - Iterate through all cells of the artifact.
  - For each cell, check if its encoded coordinate exists in the hash set.
  - If not found, set `isExtractable = false` and break.
- If `isExtractable` remains true, increment `extractedCount`.
- Return `extractedCount`.

## Pre-computation and Counting
This is another highly efficient approach with the same time complexity as the hash set method but potentially different space usage. Instead of checking from artifacts to dug sites, we can go the other way. We first pre-process all artifacts to know which cells belong to which artifact and the total size of each artifact. Then, we iterate through the dug sites, and for each dug cell, we credit the corresponding artifact. Finally, we count how many artifacts have all their cells credited (i.e., dug).
**Time:** O(A + D). O(A) to pre-process artifacts (since each has at most 4 cells), O(D) to process digs, and O(A) for the final count. · **Space:** O(A), as the total number of cells covered by artifacts is at most 4*A. The map and arrays scale with the number of artifacts.
**Pros:** Optimal time complexity.; Space complexity depends on the total number of cells covered by artifacts, which can be more efficient than the HashSet approach if `4*A` is smaller than `D`.
**Cons:** Slightly more complex implementation with multiple data structures.; Requires multiple passes over the data (once for artifacts, once for digs, once for final count).
### Explanation
This method changes the perspective: instead of asking "is this artifact cell dug?", it asks "which artifact does this dug cell uncover?". It requires pre-computation to build a mapping from each cell covered by an artifact to the artifact's identifier (its index). It also tracks the total number of cells for each artifact. After processing all dug sites and updating the counts of uncovered parts for each artifact, a final pass determines which artifacts are complete.

```java
import java.util.HashMap;
import java.util.Map;

class Solution {
    public int countArtifacts(int n, int[][] artifacts, int[][] dig) {
        int numArtifacts = artifacts.length;
        int[] artifactSizes = new int[numArtifacts];
        int[] uncoveredParts = new int[numArtifacts];
        Map<Integer, Integer> cellToArtifact = new HashMap<>();
        
        for (int i = 0; i < numArtifacts; i++) {
            int[] artifact = artifacts[i];
            int r1 = artifact[0], c1 = artifact[1], r2 = artifact[2], c2 = artifact[3];
            int size = 0;
            for (int r = r1; r <= r2; r++) {
                for (int c = c1; c <= c2; c++) {
                    cellToArtifact.put(r * n + c, i);
                    size++;
                }
            }
            artifactSizes[i] = size;
        }
        
        for (int[] d : dig) {
            int cellKey = d[0] * n + d[1];
            Integer artifactIndex = cellToArtifact.get(cellKey);
            if (artifactIndex != null) {
                uncoveredParts[artifactIndex]++;
            }
        }
        
        int extractedCount = 0;
        for (int i = 0; i < numArtifacts; i++) {
            if (artifactSizes[i] > 0 && uncoveredParts[i] == artifactSizes[i]) {
                extractedCount++;
            }
        }
        
        return extractedCount;
    }
}
```
### Algorithm
- Create a map `cellToArtifact` to link cell coordinates to artifact indices and an array `artifactSizes` to store the size of each artifact.
- Pre-process by iterating through all artifacts. For each artifact, calculate its size and populate the map with its cells.
- Create an array `uncoveredParts` initialized to zeros to count uncovered cells for each artifact.
- Iterate through the `dig` array. For each dug cell, look up which artifact it belongs to using the map and increment the `uncoveredParts` count for that artifact.
- Finally, iterate through the artifacts. If `uncoveredParts[i]` equals `artifactSizes[i]`, it means the artifact is fully excavated. Increment a result counter.
- Return the result counter.

# Solutions
### Java

```java
class Solution {
private
  Set<Integer> s = new HashSet<>();
private
  int n;
public
  int digArtifacts(int n, int[][] artifacts, int[][] dig) {
    this.n = n;
    for (var p : dig) {
      s.add(p[0] * n + p[1]);
    }
    int ans = 0;
    for (var a : artifacts) {
      ans += check(a);
    }
    return ans;
  }
private
  int check(int[] a) {
    int x1 = a[0], y1 = a[1], x2 = a[2], y2 = a[3];
    for (int x = x1; x <= x2; ++x) {
      for (int y = y1; y <= y2; ++y) {
        if (!s.contains(x * n + y)) {
          return 0;
        }
      }
    }
    return 1;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int digArtifacts(int n, vector<vector<int>> &artifacts,
                   vector<vector<int>> &dig) {
    unordered_set<int> s;
    for (auto &p : dig) {
      s.insert(p[0] * n + p[1]);
    }
    auto check = [&](vector<int> &a) {
      int x1 = a[0], y1 = a[1], x2 = a[2], y2 = a[3];
      for (int x = x1; x <= x2; ++x) {
        for (int y = y1; y <= y2; ++y) {
          if (!s.count(x * n + y)) {
            return 0;
          }
        }
      }
      return 1;
    };
    int ans = 0;
    for (auto &a : artifacts) {
      ans += check(a);
    }
    return ans;
  }
};

```

### Python

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

```