2201. Count Artifacts That Can Be Extracted

Problem Description

In the given LeetCode problem, we have a grid of n x n size where some artifacts are buried. The grid is such that each cell can be represented by coordinates (r, c), where r is the row number and c is the column number, with both being 0-indexed. Artifacts are buried in rectangular areas within this grid. Each artifact is defined by two coordinates - the top-left cell (r1, c1) and the bottom-right cell (r2, c2). This forms a rectangle in the grid, including the cells on the border of these coordinates.

As part of the excavation process, we dig certain cells in the grid, specified by array dig. Each element in dig is a pair of coordinates (r, c) indicating a cell we have dug up. An artifact is considered to be extracted if all the cells covering it are excavated. The goal is to find out how many artifacts can be completely extracted given the cells we have dug.

Intuition

To solve this problem, the first step is to keep track of all the dug cells in an efficient manner. Since we need to check whether a cell is dug or not, we can use a set data structure (s). This set will allow us to quickly determine the presence or absence of each dug cell by using the coordinates as a unique key for each cell.

Once we have this set of dug cells, the next step is to go through each artifact described in the artifacts array. For each artifact, we iterate over every cell that it covers, which are the cells bounded by (r1, c1) and (r2, c2) inclusive. We check if all these cells are present in our set of dug cells.

The check function accomplishes this iteration and checking. If at least one cell belonging to an artifact is not present in the dug cells set, it means that the artifact cannot be fully extracted, and thus, we return False. If all of the cells are present, we return True indicating the artifact can be extracted.

Finally, we use a generator expression to sum up the number of True values returned by the check function for each artifact, which translates to the number of artifacts that can be extracted.

Solution Approach

The solution follows a simple approach mainly utilizing set data structures and iteration.

1. First, we convert the dig list into a set s which includes tuples of coordinates (i, j) for each cell we dig. The set data structure is chosen for its efficient O(1) average time complexity for lookup operations, which is crucial since we need to check if each cell of an artifact has been dug.

2. A helper function check is defined which takes an artifact as an argument, represented by a list [r1, c1, r2, c2]. The function checks if all cells that belong to the artifact have been dug. It does this by iterating over all cells in the rectangular area that the artifact covers—from r1 to r2 and c1 to c2—and checking if each cell (x, y) is in the set s. If any cell is not present, check returns False because this means the artifact is incomplete and cannot be extracted.

3. If all cells of the artifact are found in the set, check returns True.

4. The main function digArtifacts applies the check function to each artifact in the artifacts array and sums up the True values (logically equivalent to 1) to obtain the total number of complete artifacts that can be extracted. This uses Python's sum function with a generator expression, which is a compact and efficient way to sum a sequence of boolean values.

Here is the relevant section of the code demonstrating the process:

1s = {(i, j) for i, j in dig}  # Convert the dig list to a set for efficient lookups
2def check(artifact):
3    r1, c1, r2, c2 = artifact  # Unpack the coordinates of the artifact
4    for x in range(r1, r2 + 1):  # Iterate over the rows
5        for y in range(c1, c2 + 1):  # Iterate over the columns
6            if (x, y) not in s:  # Check if the cell is not dug
7                return False
8    return True  # All cells are dug and artifact can be extracted
9
10# Sum up the instances where the artifact can be extracted
11return sum(check(v) for v in artifacts)

Each step of the approach is designed to cut down on unnecessary computations, which is why we use a set for digs and the check function only iterates over cells belonging to the artifacts and not the entire grid. This solution has a time complexity that scales with the number of digs and the size of the artifacts, as opposed to the entire grid size, making it efficient even for larger grid sizes.

Example Walkthrough

Let's consider the following example to illustrate the solution approach:

Suppose we have a grid of size 3 x 3 and there are two artifacts buried:

• Artifact A with coordinates [0, 0, 1, 1], which spans from the top-left corner to the cell in the second row and second column.
• Artifact B with coordinates [1, 1, 2, 2], which spans from the cell in the second row and second column to the bottom-right corner.

The dig array contains the cells that have been dug: [(0, 0), (0, 1), (1, 1), (2, 2)].

To determine how many artifacts can be completely extracted, we will follow the solution approach:

1. Convert the dig array into a set for efficient lookups.

   s = {(0, 0), (0, 1), (1, 1), (2, 2)}

2. Use the check function to verify whether all the cells of an artifact have been dug.

3. For Artifact A, the check function will look at coordinates:

   • (0, 0), which is in the set s
   • (0, 1), which is in the set s
   • (1, 0), which is not in the set s
   • (1, 1), which is in the set s

   Since the cell (1, 0) hasn't been dug, Artifact A cannot be fully extracted; hence, check returns False.

4. For Artifact B, the check function will verify the following cells:

   • (1, 1), which is in the set s
   • (1, 2), which is not in the set s
   • (2, 1), which is not in the set s
   • (2, 2), which is in the set s

   Since the cells (1, 2) and (2, 1) haven't been dug, Artifact B cannot be fully extracted; thus, check returns False.

5. Now, we sum up the True values returned by the check function for each artifact. Since both artifacts returned False, the sum is 0, meaning no artifacts can be completely extracted based on the cells dug.

By using this solution approach, we are focusing the computation only on the cells that need to be checked, avoiding unnecessary work on other grid cells that do not contain artifacts. This example illustrates how combining set data structures with a focused checking function works efficiently to solve the problem.

Solution Implementation

Time and Space Complexity

Time Complexity

The time complexity of the given code can be analyzed in the following steps:

1. Conversion of dig list into a set s: This operation iterates over each element in the dig list once. Therefore, the time complexity for this part is O(D), where D is the length of the dig list.

2. The check function: This function is called for each artifact. Inside the function, there's a nested loop that iterates over the artifact's area which is at most (r2 - r1 + 1) * (c2 - c1 + 1) for each artifact. In the worst case, this could be equal to the size of the grid (n * n), if the artifact covers the entire grid.

3. The last line sums up the results of the check function for each artifact. Since check is invoked once per artifact, the time complexity for calling check overall is O(A * n^2), where A is the number of artifacts, since we consider the worst case where an artifact spans the entire grid.

Combining these complexities, we have an overall time complexity of O(D + A * n^2).

Space Complexity

The space complexity can be analyzed by looking at the additional space used by the program components:

1. The set s that stores the dug positions: In the worst case, it will store all D positions where digs happened, yielding a space complexity of O(D).

2. The space used for the check function's call stack is negligible as it does not involve recursive calls or additional data structures with size depending on the inputs. However, due to the iterating for each cell in the range of an artifact, at worst case the space required to store the temporary variables x and y in the stack is constant, O(1).

Overall, since there are no other significant data structures being used, the space complexity is O(D).

Learn more about how to find time and space complexity quickly using problem constraints.