2201. Count Artifacts That Can Be Extracted LeetCode Solution
In this guide, you will get 2201. Count Artifacts That Can Be Extracted LeetCode Solution with the best time and space complexity. The solution to Count Artifacts That Can Be Extracted problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Count Artifacts That Can Be Extracted
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.
Complexity Analysis
Time Complexity: O(|\texttt{dig}| + n^2)
Space Complexity: O(|\texttt{dig}|)
2201. Count Artifacts That Can Be Extracted LeetCode Solution in C++
class Solution {
public:
int digArtifacts(int n, vector<vector<int>>& artifacts,
vector<vector<int>>& dig) {
unordered_set<int> digged;
for (const vector<int>& d : dig)
digged.insert(hash(d[0], d[1]));
return ranges::count_if(
artifacts, [&](const auto& a) { return canExtract(a, digged); });
}
private:
int hash(int i, int j) {
return i << 16 | j;
}
bool canExtract(const vector<int>& a, const unordered_set<int>& digged) {
for (int i = a[0]; i <= a[2]; ++i)
for (int j = a[1]; j <= a[3]; ++j)
if (!digged.contains(hash(i, j)))
return false;
return true;
}
}; /* code provided by PROGIEZ */
2201. Count Artifacts That Can Be Extracted LeetCode Solution in Java
class Solution {
public int digArtifacts(int n, int[][] artifacts, int[][] dig) {
Set<Integer> digged = new HashSet<>();
for (int[] d : dig)
digged.add(hash(d[0], d[1]));
return (int) Arrays.stream(artifacts).filter(a -> canExtract(a, digged)).count();
}
private int hash(int i, int j) {
return i << 16 | j;
}
private boolean canExtract(int[] a, Set<Integer> digged) {
for (int i = a[0]; i <= a[2]; ++i)
for (int j = a[1]; j <= a[3]; ++j)
if (!digged.contains(hash(i, j)))
return false;
return true;
}
} // code provided by PROGIEZ
2201. Count Artifacts That Can Be Extracted LeetCode Solution in Python
class Solution:
def digArtifacts(
self,
n: int,
artifacts: list[list[int]],
dig: list[list[int]],
) -> int:
digged = set((r, c) for r, c in dig)
def canExtract(a: list[int]) -> bool:
for i in range(a[0], a[2] + 1):
for j in range(a[1], a[3] + 1):
if (i, j) not in digged:
return False
return True
return sum(canExtract(a) for a in artifacts) # code by PROGIEZ
