Scale Engineer

Count Artifacts That Can Be Extracted

Med
#2005Time: 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`.
Data structures
ArrayHash Table

Prompt

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:

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

4 approaches with complexity analysis and trade-offs.

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.

Walkthrough

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

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`.

Trade-offs

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.

Solutions

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 walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem