Skip to content

2201. Count Artifacts That Can Be Extracted 👎

  • Time: $O(|\texttt{dig}| + n^2)$
  • Space: $O(|\texttt{dig}|)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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 count_if(begin(artifacts), end(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.count(hash(i, j)))
          return false;
    return true;
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
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;
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
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)