LeetCode 2201: Count Artifacts That Can Be Extracted Solution

Master LeetCode problem 2201 (Count Artifacts That Can Be Extracted), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

2201. Count Artifacts That Can Be Extracted

Medium

Array Hash Table Simulation

Problem Explanation

Explanation

To solve this problem, we can simulate the excavation process and keep track of the uncovered parts of each artifact. We can use a set to store the coordinates of the excavated cells and iterate through the artifacts to check if all their parts are uncovered. If all parts of an artifact are uncovered, we increment the count of extractable artifacts.

We initialize a set excavated to store excavated cell coordinates.
We iterate through the dig array and add the excavated cells to the excavated set.
We iterate through the artifacts and check if all parts are uncovered by comparing the cell coordinates with the excavated set.
If all parts are uncovered, we increment the count of extractable artifacts.

Time complexity: O(n) where n is the number of artifacts
Space complexity: O(n) for the set and storing artifact details

Solution Code

class Solution {
    public int countArtifacts(int n, int[][] artifacts, int[][] dig) {
        Set<String> excavated = new HashSet<>();
        int count = 0;
        
        for (int[] d : dig) {
            excavated.add(d[0] + "," + d[1]);
        }
        
        for (int[] artifact : artifacts) {
            int r1 = artifact[0], c1 = artifact[1];
            int r2 = artifact[2], c2 = artifact[3];
            boolean uncovered = true;
            
            for (int i = r1; i <= r2; i++) {
                for (int j = c1; j <= c2; j++) {
                    if (!excavated.contains(i + "," + j)) {
                        uncovered = false;
                        break;
                    }
                }
                if (!uncovered) break;
            }
            
            if (uncovered) count++;
        }
        
        return count;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 2201 (Count Artifacts That Can Be Extracted)?

This page provides optimized solutions for LeetCode problem 2201 (Count Artifacts That Can Be Extracted) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 2201 (Count Artifacts That Can Be Extracted)?

The time complexity for LeetCode 2201 (Count Artifacts That Can Be Extracted) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 2201 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 2201 in Java, C++, or Python.

Back to LeetCode Solutions