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 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;
  }
};

 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
13
14
15
16
17
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)