Count Artifacts That Can Be Extracted Solution In C++/Java/Python/Javascript
Problem Description
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:
(r1 i,c1 i) 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.
The test cases are generated such that:
No two artifacts overlap.
Each artifact only covers at most 4 cells.
The entries of dig are unique.
Examples:
Input: n = 2, artifacts = [[0,0,0,0],[0,1,1,1]], dig = [[0,0],[0,1]]
Output: 1
Explanation:
The different colors represent different artifacts. Excavated cells are labeled with a 'D' in the grid.
There is 1 artifact that can be extracted, namely the red artifact.
The blue artifact has one part in cell (1,1) which remains uncovered, so we cannot extract it.
Thus, we return 1.
Input: n = 2, artifacts = [[0,0,0,0],[0,1,1,1]], dig = [[0,0],[0,1],[1,1]]
Output: 2
Explanation: Both the red and blue artifacts have all parts uncovered (labeled with a 'D') and can be extracted, so we return 2.
Constraints
- 1 <= n <= 1000
- 1 <= artifacts.length, dig.length <= min(n^2, 10^5)
- artifacts[i].length == 4
- dig[i].length == 2
- 0 <= r1 i, c1 i, r2 i, c2 i, r i, c i <= n - 1
- r1 i <= r2 i
- c1 i <= c2 i
- No two artifacts will overlap.
- The number of cells covered by an artifact is at most 4.
- The entries of dig are unique.
This problem involves determining how many artifacts in a grid can be fully uncovered using given excavation coordinates. The challenge is to efficiently check if all cells of an artifact have been excavated. A smart approach is to track excavated positions using a set and verify completeness for each artifact, ensuring quick lookups and minimal redundant checks.
Brute Force Approach
Intuition
The approach to solving the Count Artifacts That Can Be Extracted problem involves systematically checking every artifact in the grid to determine if it can be fully extracted based on the cells that have been dug. The goal is to identify all artifacts where every cell within their rectangular area has been excavated.
To achieve this, we use a simulation-based approach. First, we initialize a 2D boolean grid called visited to represent the excavation status of each cell. We then iterate through the dig array and mark the corresponding cells in the visited grid as true. This step simulates the digging process and helps us keep track of which cells have been excavated.
Next, for each artifact, we check if all the cells within its rectangular area have been dug. This involves iterating through every cell in the artifact's area and verifying if it has been marked as true in the visited grid. If all cells in the artifact's area are marked as true, the artifact can be fully extracted, and we increment our count.
To ensure the solution is efficient and avoids redundant checks, we rely on the grid representation and the simulation of the digging process. By breaking the problem into smaller, manageable steps—such as marking dug cells, iterating through artifacts, and verifying their extraction status—we can systematically evaluate every artifact and determine if it can be fully extracted.
This approach ensures that every possible artifact is evaluated, and the use of the visited grid provides a clear and efficient way to track the excavation status of cells. By focusing on these smaller steps, we gain a clear understanding of the problem and ensure that the solution is both intuitive and effective.
Approach
Step 1: Initialize a 2D Boolean Grid
Create a 2D boolean grid called visited of size n x n and initialize all its values to false. This grid will help us keep track of which cells in the grid have been excavated.
Step 2: Mark the Excavated Cells
Iterate through the dig array and mark the corresponding cells in the visited grid as true. This step simulates the digging process and ensures that we know which cells have been excavated.
Step 3: Initialize a Counter for Extracted Artifacts
Create a variable called count and set it to 0. This variable will keep track of the number of artifacts that can be fully extracted.
Step 4: Iterate Through Each Artifact
Loop through the artifacts array. For each artifact, extract its coordinates, which define the rectangular area it occupies. The coordinates are given as r1, c1 (top-left corner) and r2, c2 (bottom-right corner).
Step 5: Check if All Cells in the Artifact Are Excavated
For each artifact, use nested loops to iterate through every cell within its rectangular area. Check if the corresponding cell in the visited grid is marked as true. If any cell in the artifact's area is not excavated (i.e., false), mark the artifact as not extractable.
Step 6: Increment the Counter if the Artifact Is Fully Excavated
If all cells within the artifact's area are marked as true in the visited grid, increment the count variable. This indicates that the artifact can be fully extracted.
Step 7: Return the Final Count
After processing all artifacts, return the value of count, which represents the total number of artifacts that can be fully extracted based on the excavated cells.
Count Artifacts That Can Be Extracted Dry run - Brute Force
Input Values:
- Grid size (n): 2×2
- Artifacts:
Artifact 1 → Covers cell (0,0)
Artifact 2 → Covers cells (0,1) and (1,1) - Dig locations: (0,0) and (0,1)
Step 1: Initialize visited Grid
A visited matrix is initialized to track which cells have been dug.
Initially, visited is:
0 0
0 0
Step 2: Mark Dig Locations in visited
After processing dig locations (0,0) and (0,1), the visited grid updates to:
1 1
0 0
(1 represents dug cells, 0 represents undug cells)
Step 3: Process ArtifactsArtifact 1: (0,0 to 0,0)
- It covers only one cell: (0,0).
- Since (0,0) is dug (visited[0][0] = 1), it is fully excavated.
- Increase count to 1.
Artifact 2: (0,1 to 1,1)
- It covers cells (0,1) and (1,1).
- (0,1) is dug (visited[0][1] = 1), but (1,1) is not (visited[1][1] = 0).
- Since not all cells are dug, it is not fully excavated.
Final Output
Only one artifact is fully excavated, so the function returns 1.
Count Artifacts That Can Be Extracted Code for All Languages - Brute Force
C++
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
// Function to count the number of fully dug-up artifacts
int digArtifacts(int n, vector<vector<int>>& artifacts, vector<vector<int>>& dig) {
vector<vector<bool>> visited(n, vector<bool>(n, false));
// Mark the positions that have been dug
for (auto& vec : dig) {
visited[vec[0]][vec[1]] = true;
}
int count = 0;
// Check if each artifact is completely uncovered
for (auto& artifact : artifacts) {
int r1 = artifact[0], c1 = artifact[1], r2 = artifact[2], c2 = artifact[3];
bool flag = true;
// Iterate through the artifact's area
for (int i = r1; i <= r2; i++) {
for (int j = c1; j <= c2; j++) {
if (!visited[i][j]) {
flag = false;
}
}
}
// If the artifact is fully uncovered, increment count
if (flag) count++;
}
return count;
}
};
int main() {
int n, m, d;
// Read grid size and number of artifacts
cin >> n >> m;
vector<vector<int>> artifacts(m, vector<int>(4));
// Read artifact positions
for (int i = 0; i < m; i++) {
for (int j = 0; j < 4; j++) {
cin >> artifacts[i][j];
}
}
// Read number of dig locations
cin >> d;
vector<vector<int>> dig(d, vector<int>(2));
// Read dig positions
for (int i = 0; i < d; i++) {
cin >> dig[i][0] >> dig[i][1];
}
Solution sol;
// Output the number of completely uncovered artifacts
cout << sol.digArtifacts(n, artifacts, dig) << endl;
return 0;
}Count Artifacts That Can Be Extracted code in Java - Brute Force
import java.util.*;
class Solution {
// Function to count the number of fully dug-up artifacts
public int digArtifacts(int n, int[][] artifacts, int[][] dig) {
boolean[][] visited = new boolean[n][n];
// Mark the positions that have been dug
for (int[] d : dig) {
visited[d[0]][d[1]] = true;
}
int count = 0;
// Check if each artifact is completely uncovered
for (int[] artifact : artifacts) {
int r1 = artifact[0], c1 = artifact[1], r2 = artifact[2], c2 = artifact[3];
boolean flag = true;
// Iterate through the artifact's area
for (int i = r1; i <= r2; i++) {
for (int j = c1; j <= c2; j++) {
if (!visited[i][j]) {
flag = false;
}
}
}
// If the artifact is fully uncovered, increment count
if (flag) count++;
}
return count;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();
int[][] artifacts = new int[m][4];
for (int i = 0; i < m; i++) {
for (int j = 0; j < 4; j++) {
artifacts[i][j] = scanner.nextInt();
}
}
int d = scanner.nextInt();
int[][] dig = new int[d][2];
for (int i = 0; i < d; i++) {
dig[i][0] = scanner.nextInt();
dig[i][1] = scanner.nextInt();
}
Solution sol = new Solution();
System.out.println(sol.digArtifacts(n, artifacts, dig));
scanner.close();
}
}Count Artifacts That Can Be Extracted code in Python - Brute Force
# Function to count the number of fully dug-up artifacts
def digArtifacts(n, artifacts, dig):
visited = [[False] * n for _ in range(n)]
# Mark the positions that have been dug
for x, y in dig:
visited[x][y] = True
count = 0
# Check if each artifact is completely uncovered
for r1, c1, r2, c2 in artifacts:
if all(visited[i][j] for i in range(r1, r2+1) for j in range(c1, c2+1)):
count += 1
return count
# Read input values
n = int(input())
m = int(input())
artifacts = [list(map(int, input().split())) for _ in range(m)]
d = int(input())
dig = [list(map(int, input().split())) for _ in range(d)]
# Print the number of fully uncovered artifacts
print(digArtifacts(n, artifacts, dig))Count Artifacts That Can Be Extracted code in JavaScript - Brute Force
function digArtifacts(n, artifacts, dig) {
let visited = Array.from({ length: n }, () => Array(n).fill(false));
// Mark the positions that have been dug
for (let [x, y] of dig) {
visited[x][y] = true;
}
let count = 0;
// Check if each artifact is completely uncovered
for (let [r1, c1, r2, c2] of artifacts) {
let flag = true;
for (let i = r1; i <= r2; i++) {
for (let j = c1; j <= c2; j++) {
if (!visited[i][j]) {
flag = false;
}
}
}
if (flag) count++;
}
return count;
}
// Example usage
const n = parseInt(prompt());
const m = parseInt(prompt());
let artifacts = Array.from({ length: m }, () => prompt().split(' ').map(Number));
const d = parseInt(prompt());
let dig = Array.from({ length: d }, () => prompt().split(' ').map(Number));
console.log(digArtifacts(n, artifacts, dig));Time Complexity : O(N)
Marking dug positions:
- We iterate through the dig array of size d, marking the visited matrix.
- This takes O(d) time.
Checking artifacts:
- For each artifact in artifacts, we iterate through all its covered grid positions.
- Since each artifact has a bounded area (at most n² in the worst case), iterating over all m artifacts results in O(m * k) time, where k is the number of cells in each artifact.
- The worst case occurs when all artifacts cover separate cells, so k can be at most O(n²/m), leading to an upper bound of O(m * n²/m) = O(n²).
Overall Complexity:
- The worst-case scenario is O(d + n²), but since d ≤ n² and m ≤ n², the effective upper bound remains O(n²).
Space Complexity : O(1)
Auxiliary Space Complexity (Extra Space Used)
- visited matrix of size n × n → O(n²).
- No additional significant data structures beyond input storage.
Total Space Complexity
Input Storage:
- artifacts: O(m) (each artifact has 4 integers).
- dig: O(d) (each dig position has 2 integers).
- Auxiliary Space: O(n²) for the visited matrix.
Overall: Worst-case scenario: O(n²) (auxiliary) + O(m + d) (input) = O(n²).
Learning Tip
Now we have successfully tackled this problem, let's try these similar problems.
Given an m x n binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area.
You are given the two integers, n and m and two integer arrays, hBars and vBars. The grid has n + 2 horizontal and m + 2 vertical bars, creating 1 x 1 unit cells. The bars are indexed starting from 1.
You can remove some of the bars in h Bars from horizontal bars and some of the bars in v Bars from vertical bars. Note that other bars are fixed and cannot be removed.
Return an integer denoting the maximum area of a square-shaped hole in the grid, after removing some bars (possibly none).