Count Artifacts That Can Be Extracted

Medium
1792.

Count Artifacts That Can Be Extracted

Count Artifacts That Can Be Extracted is a medium coding problem on arrays, hash table and simulation, asked in Google interviews.

An n x n grid of earth hides some artifacts. Artifact i is the axis-aligned rectangle artifacts[i] = [r1, c1, r2, c2]: it covers every cell (r, c) with r1 <= r <= r2 and c1 <= c <= c2. No two artifacts overlap, and each covers at most 4 cells.

You excavate the cells listed in dig, where dig[j] = [r, c]. An artifact can be extracted once every cell it covers has been excavated.

Return the number of artifacts you can extract.

Example 1

Input
n = 3, artifacts = [[0,0,1,0],[2,1,2,2],[0,2,0,2]], dig = [[0,0],[1,0],[2,2],[0,2]]
Output
2
Explanation
The first artifact covers (0,0) and (1,0), both dug. The third covers only (0,2), dug. The second still has (2,1) buried.

Example 2

Input
n = 2, artifacts = [[0,0,0,0],[0,1,1,1]], dig = [[0,0],[0,1]]
Output
1
Explanation
The second artifact also covers (1,1), which was not dug.

Example 3

Input
n = 1, artifacts = [[0,0,0,0]], dig = [[0,0]]
Output
1

Constraints

  • 1 <= n <= 1000
  • 1 <= artifacts.length, dig.length <= min(n^2, 10^5)
  • artifacts[i].length == 4
  • dig[j].length == 2
  • 0 <= r1 <= r2 < n, 0 <= c1 <= c2 < n
  • no two artifacts overlap; each covers at most 4 cells
  • the entries of dig are unique
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @param {number[][]} artifacts
 * @param {number[][]} dig
 * @return {number}
 */
var digArtifacts = function(n, artifacts, dig) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Count Artifacts That Can Be Extracted — Problem & Solution

Count Artifacts That Can Be Extracted solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Count Artifacts That Can Be Extracted is a medium coding problem on arrays, hash table and simulation, asked in Google interviews.

  • Difficulty: Medium
  • Topics: Arrays, Hash Table, Simulation
  • Asked at: Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

An n x n grid of earth hides some artifacts. Artifact i is the axis-aligned rectangle artifacts[i] = [r1, c1, r2, c2]: it covers every cell (r, c) with r1 <= r <= r2 and c1 <= c <= c2. No two artifacts overlap, and each covers at most 4 cells.

You excavate the cells listed in dig, where dig[j] = [r, c]. An artifact can be extracted once every cell it covers has been excavated.

Return the number of artifacts you can extract.

Example 1

Input: n = 3, artifacts = [[0,0,1,0],[2,1,2,2],[0,2,0,2]], dig = [[0,0],[1,0],[2,2],[0,2]]
Output: 2
Explanation: The first artifact covers (0,0) and (1,0), both dug. The third covers only (0,2), dug. The second still has (2,1) buried.

Example 2

Input: n = 2, artifacts = [[0,0,0,0],[0,1,1,1]], dig = [[0,0],[0,1]]
Output: 1
Explanation: The second artifact also covers (1,1), which was not dug.

Example 3

Input: n = 1, artifacts = [[0,0,0,0]], dig = [[0,0]]
Output: 1

Constraints

  • 1 <= n <= 1000
  • 1 <= artifacts.length, dig.length <= min(n^2, 10^5)
  • artifacts[i].length == 4
  • dig[j].length == 2
  • 0 <= r1 <= r2 < n, 0 <= c1 <= c2 < n
  • no two artifacts overlap; each covers at most 4 cells
  • the entries of dig are unique

Hints for Count Artifacts That Can Be Extracted

  1. Hint 1

    Checking a cell should be O(1): store the excavated cells first.

  2. Hint 2

    Put every dug cell in a hash set (encode (r, c) as r * n + c) or a boolean grid.

  3. Hint 3

    Each artifact covers at most 4 cells, so checking all of its cells is cheap.

How to solve Count Artifacts That Can Be Extracted

Mark the excavated cells, then test each artifact's (at most four) cells against the marks.

Approach

  1. Insert r * n + c for every [r, c] in dig into a hash set.
  2. For each artifact, loop over its rows r1..r2 and columns c1..c2; it counts if every cell is in the set.
  3. Return the count.

Why it works

An artifact is extractable exactly when all its cells are excavated, which is what the loop checks with constant-time lookups. Because artifacts do not overlap, each is judged independently.

Complexity

  • Time — O(D + A)
  • Space — O(D)

Pitfalls

  • Encoding a cell as r + c or r * c collides; use r * n + c (or a pair).
  • Both corners are inclusive — the loops run to r2 and c2.

Reference solution

Python

from typing import List

def digArtifacts(n: int, artifacts: List[List[int]], dig: List[List[int]]) -> int:
    dug = {r * n + c for r, c in dig}
    total = 0
    for r1, c1, r2, c2 in artifacts:
        if all(r * n + c in dug for r in range(r1, r2 + 1) for c in range(c1, c2 + 1)):
            total += 1
    return total

Java

public static int digArtifacts(int n, int[][] artifacts, int[][] dig) {
    Set<Long> dug = new HashSet<>();
    for (int[] d : dig) dug.add((long) d[0] * n + d[1]);
    int total = 0;
    for (int[] a : artifacts) {
        boolean all = true;
        for (int r = a[0]; r <= a[2] && all; r++)
            for (int c = a[1]; c <= a[3]; c++)
                if (!dug.contains((long) r * n + c)) { all = false; break; }
        if (all) total++;
    }
    return total;
}

C++

int digArtifacts(int n, vector<vector<int>>& artifacts, vector<vector<int>>& dig) {
    unordered_set<long long> dug;
    for (auto& d : dig) dug.insert((long long)d[0] * n + d[1]);
    int total = 0;
    for (auto& a : artifacts) {
        bool all = true;
        for (int r = a[0]; r <= a[2] && all; r++)
            for (int c = a[1]; c <= a[3]; c++)
                if (!dug.count((long long)r * n + c)) { all = false; break; }
        if (all) total++;
    }
    return total;
}

JavaScript

var digArtifacts = function(n, artifacts, dig) {
    var dug = new Set();
    for (var i = 0; i < dig.length; i++) dug.add(dig[i][0] * n + dig[i][1]);
    var total = 0;
    for (var a = 0; a < artifacts.length; a++) {
        var art = artifacts[a], all = true;
        for (var r = art[0]; r <= art[2] && all; r++)
            for (var c = art[1]; c <= art[3]; c++)
                if (!dug.has(r * n + c)) { all = false; break; }
        if (all) total++;
    }
    return total;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets