Problem Description

You are given an n x n grid representing an archaeological site. There are several artifacts buried on the grid, each defined by a rectangular region: [r1, c1, r2, c2], where (r1, c1) is the top-left cell and (r2, c2) is the bottom-right cell of the artifact.

Some cells in the grid have already been dug (i.e., excavated), given as a list of coordinates dig. An artifact can be extracted only if all the cells it occupies have been dug.

Your task is to count how many artifacts can be extracted, given the grid size n, the list of artifacts, and the list of dug cells dig.

• Each artifact covers a rectangle (may be 1x1, 1x2, 2x1, or 2x2).
• No two artifacts overlap.
• Cells in dig may appear in any order.

Return the number of artifacts that can be extracted.

Thought Process

First, let's understand the problem by focusing on what needs to be checked for each artifact: whether all the cells it covers have been dug. The brute-force approach would be to, for each artifact, check every cell it covers and see if that cell is present in the dig list.

But checking if a cell is in dig by scanning the whole list is inefficient. To optimize, we can use a set to store dug cells for O(1) lookup, making the check for each artifact much faster.

The key realization is that, since artifacts do not overlap and the grid is small, we can process each artifact independently. Our focus is on efficiently checking if all the cells of an artifact are dug.

Solution Approach

• Step 1: Convert the dig list into a set of tuples (or strings) representing dug cells. This allows for quick lookup to check if a cell is dug.
• Step 2: For each artifact, enumerate all the cells it covers by looping from r1 to r2, and c1 to c2.
• Step 3: For each cell of the artifact, check if it is present in the dug set.
• Step 4: If all cells of an artifact are dug, increment the counter for extractable artifacts.
• Step 5: Return the counter after processing all artifacts.

We use a set for constant-time lookup, and iterate only over the cells covered by each artifact. This ensures efficiency even if the number of artifacts or dug cells is large.

Example Walkthrough

Sample Input:
n = 3
artifacts = [[0,0,0,0], [0,1,1,1]]
dig = [[0,0], [0,1], [1,1]]

1. Convert dig to a set: {(0,0), (0,1), (1,1)}
2. For artifact [0,0,0,0] (covers only cell (0,0)):
   • Is (0,0) dug? Yes. Artifact can be extracted.
3. For artifact [0,1,1,1] (covers cells (0,1) and (1,1)):
   • Is (0,1) dug? Yes.
   • Is (1,1) dug? Yes.
   • All cells are dug. Artifact can be extracted.
4. Both artifacts can be extracted, so the answer is 2.

Time and Space Complexity

• Brute-force approach: For each artifact, for each cell it covers, scan the entire dig list. If there are k artifacts, each covering up to 4 cells, and m dug cells, this is O(k * 4 * m) = O(km).
• Optimized approach:
  • Building the set of dug cells: O(m)
  • For each artifact (k artifacts, each up to 4 cells): O(k * 4) = O(k)
  • For each cell, lookup in the set is O(1)
  • Total time complexity: O(m + k)
  • Space complexity: O(m) for the dug set

This is efficient and works well within the problem's constraints.

Summary

The problem requires checking if all cells of each artifact have been dug in order to count extractable artifacts. By using a set for the dug cells, we achieve constant-time checks for each cell, making the solution efficient. The approach is straightforward: process each artifact, check its cells, and count those that are fully dug. This leverages basic data structures and avoids unnecessary nested loops, resulting in an elegant and optimal solution.

Code Implementation

class Solution:
    def countArtifacts(self, n, artifacts, dig):
        dug = set((r, c) for r, c in dig)
        count = 0
        for r1, c1, r2, c2 in artifacts:
            extracted = True
            for r in range(r1, r2+1):
                for c in range(c1, c2+1):
                    if (r, c) not in dug:
                        extracted = False
                        break
                if not extracted:
                    break
            if extracted:
                count += 1
        return count
      

class Solution {
public:
    int countArtifacts(int n, vector<vector<int>>& artifacts, vector<vector<int>>& dig) {
        unordered_set<int> dug;
        for (auto& d : dig) {
            dug.insert(d[0] * n + d[1]);
        }
        int count = 0;
        for (auto& art : artifacts) {
            bool extracted = true;
            for (int r = art[0]; r <= art[2]; ++r) {
                for (int c = art[1]; c <= art[3]; ++c) {
                    if (!dug.count(r * n + c)) {
                        extracted = false;
                        break;
                    }
                }
                if (!extracted) break;
            }
            if (extracted) ++count;
        }
        return count;
    }
};
      

import java.util.*;
class Solution {
    public int countArtifacts(int n, int[][] artifacts, int[][] dig) {
        Set<Integer> dug = new HashSet<>();
        for (int[] d : dig) {
            dug.add(d[0] * n + d[1]);
        }
        int count = 0;
        for (int[] art : artifacts) {
            boolean extracted = true;
            for (int r = art[0]; r <= art[2]; r++) {
                for (int c = art[1]; c <= art[3]; c++) {
                    if (!dug.contains(r * n + c)) {
                        extracted = false;
                        break;
                    }
                }
                if (!extracted) break;
            }
            if (extracted) count++;
        }
        return count;
    }
}
      

var countArtifacts = function(n, artifacts, dig) {
    const dug = new Set();
    for (const [r, c] of dig) {
        dug.add(r * n + c);
    }
    let count = 0;
    for (const [r1, c1, r2, c2] of artifacts) {
        let extracted = true;
        for (let r = r1; r <= r2; r++) {
            for (let c = c1; c <= c2; c++) {
                if (!dug.has(r * n + c)) {
                    extracted = false;
                    break;
                }
            }
            if (!extracted) break;
        }
        if (extracted) count++;
    }
    return count;
};