Count Artifacts That Can Be Extracted - Practice Coding Problems

Count Artifacts That Can Be Extracted - Problem

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.

Note: No two artifacts overlap. Each artifact only covers at most 4 cells. The entries of dig are unique.

Input & Output

Example 1 — Basic Case

$ Input: n = 2, artifacts = [[0,0,0,0],[0,1,1,1]], dig = [[0,0],[0,1]]

› Output: 1

💡 Note: First artifact [0,0,0,0] covers only cell (0,0) which is excavated, so it can be extracted. Second artifact [0,1,1,1] covers cells (0,1), (1,1) but only (0,1) is excavated, so it cannot be extracted. Total: 1 artifact.

Example 2 — No Artifacts Extractable

$ Input: n = 2, artifacts = [[0,0,0,0],[0,1,1,1]], dig = [[0,1]]

› Output: 0

💡 Note: First artifact needs cell (0,0) but it's not excavated. Second artifact needs cells (0,1), (1,1) but only (0,1) is excavated. Neither artifact is fully excavated, so 0 can be extracted.

Example 3 — All Artifacts Extractable

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

› Output: 2

💡 Note: First artifact [0,0,0,1] covers cells (0,0), (0,1) - both are excavated. Second artifact [1,0,1,0] covers cell (1,0) - it is excavated. Both artifacts can be extracted.

Constraints

1 ≤ n ≤ 1000
1 ≤ artifacts.length, dig.length ≤ 10⁵
artifacts[i].length == 4
dig[i].length == 2
0 ≤ r1i, c1i, r2i, c2i, ri, ci ≤ n - 1
r1i ≤ r2i and 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

Visualization

Tap to expand

Understanding the Visualization

Input Grid

2×2 grid with artifacts at [0,0,0,0] and [0,1,1,1], excavated positions (0,0) and (0,1)

Check Coverage

First artifact covers (0,0) ✓ - fully excavated. Second covers (0,1) ✓, (1,1) ✗ - partially excavated

Count Result

Only 1 artifact can be extracted

Key Takeaway

🎯 Key Insight: Use hash set for O(1) lookups when checking if artifact cells are excavated

Asked in

M Meta 12 G Google 8 A Amazon 6

The key insight is that an artifact can only be extracted if ALL its cells have been excavated. The optimal approach uses a hash set to store excavated positions for O(1) lookup time, then checks each artifact's cells against this set. Time: O(d + a × c), Space: O(d).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Check Each Cell Multiple Times	O(a × c × d)	O(1)	For each artifact, scan through all dig positions to check if each artifact cell is excavated
Hash Set Optimization	O(d + a × c)	O(d)	First store all dig positions in a hash set, then check each artifact in O(1) per cell

Brute Force - Check Each Cell Multiple Times — Algorithm Steps

For each artifact, get its rectangular boundaries
For each cell in the artifact, check if it appears in the dig array
Count artifacts where all cells are found in dig array

Visualization

Tap to expand

Step-by-Step Walkthrough

Select Artifact

Take first artifact [0,0,0,1] covering cells (0,0) and (0,1)

Check Each Cell

For cell (0,0), scan through dig array [0,0],[0,1],[1,0] until match found

Repeat Process

For cell (0,1), scan dig array again - very inefficient!

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int n, int artifacts[][4], int artifactsSize, int dig[][2], int digSize) {
    int count = 0;
    
    for (int i = 0; i < artifactsSize; i++) {
        int r1 = artifacts[i][0], c1 = artifacts[i][1];
        int r2 = artifacts[i][2], c2 = artifacts[i][3];
        int fullyExcavated = 1;
        
        // Check each cell in the artifact
        for (int r = r1; r <= r2 && fullyExcavated; r++) {
            for (int c = c1; c <= c2; c++) {
                // Check if this cell is in dig array
                int found = 0;
                for (int j = 0; j < digSize; j++) {
                    if (dig[j][0] == r && dig[j][1] == c) {
                        found = 1;
                        break;
                    }
                }
                if (!found) {
                    fullyExcavated = 0;
                    break;
                }
            }
        }
        
        if (fullyExcavated) count++;
    }
    
    return count;
}

int main() {
    int n;
    scanf("%d", &n);
    
    // Simplified parsing for demo
    int artifacts[100][4];
    int artifactsSize = 0;
    int dig[1000][2];
    int digSize = 0;
    
    int result = solution(n, artifacts, artifactsSize, dig, digSize);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(a × c × d)

For each artifact (a), check each cell (c) against all dig positions (d)

✓ Linear Growth

Space Complexity

O(1)

Only using variables, no extra data structures

✓ Linear Space

12.4K Views

Medium Frequency

~15 min Avg. Time

287 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Check Each Cell Multiple Times — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler