Count Artifacts That Can Be Extracted

MEDIUM

Description

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] = [r1_i, c1_i, r2_i, c2_i] denotes that the i^th artifact is buried in the subgrid where:

(r1_i, c1_i) is the coordinate of the top-left cell of the i^th artifact and
(r2_i, c2_i) is the coordinate of the bottom-right cell of the i^th 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] = [r_i, c_i] indicates that you will excavate the cell (r_i, c_i), 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:

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:

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(n², 10⁵)
artifacts[i].length == 4
dig[i].length == 2
0 <= r1_i, c1_i, r2_i, c2_i, r_i, c_i <= n - 1
r1_i <= r2_i
c1_i <= c2_i
No two artifacts will overlap.
The number of cells covered by an artifact is at most 4.
The entries of dig are unique.

Approaches

Checkout 4 different approaches to solve Count Artifacts That Can Be Extracted. Click on different approaches to view the approach and algorithm in detail.

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.

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.

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.

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;
    }
}

Complexity Analysis

Time Complexity: 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 Complexity: O(n^2) to store the `dugGrid`.

Pros and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Count Artifacts That Can Be Extracted. Click on different languages to view the code.

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;
  }
}

Video Solution

Watch the video walkthrough for Count Artifacts That Can Be Extracted

Data Structures:

ArrayHash Table