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 <= 10001 <= artifacts.length, dig.length <= min(n^2, 10^5)artifacts[i].length == 4dig[j].length == 20 <= r1 <= r2 < n, 0 <= c1 <= c2 < nno two artifacts overlap; each covers at most 4 cellsthe entries of dig are unique
Hints for Count Artifacts That Can Be Extracted
Hint 1
Checking a cell should be O(1): store the excavated cells first.
Hint 2
Put every dug cell in a hash set (encode
(r, c)asr * n + c) or a boolean grid.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
- Insert
r * n + cfor every[r, c]indiginto a hash set. - For each artifact, loop over its rows
r1..r2and columnsc1..c2; it counts if every cell is in the set. - 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 + corr * ccollides; user * n + c(or a pair). - Both corners are inclusive — the loops run to
r2andc2.
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 totalJava
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