Abstract / Summary

Count how many artifacts can be removed by always taking the one with the least dependencies first.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 57% (40k+ submissions).

Typical patterns to solve this problem:

• Array
• Hash Table
• Simulation

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The implementation defines a class with a single method that determines how many artifacts are completely uncovered after a series of dig operations on an n × n grid. Each artifact occupies a rectangular region whose corners are given, and each dig reveals a single cell. The method builds a fast lookup structure to map every cell that belongs to an artifact to the artifact’s identifier, then processes each dig, decrementing a counter that tracks how many cells of each artifact remain hidden. Finally it counts how many artifacts have a remaining counter of zero, meaning all of their cells have been dug up.

Key Steps

Building the identifier and cell-to-artifact map

fast = lambda x, y: 10000 * x + y
need = []
look = {}
for x1, y1, x2, y2 in artifacts:
    id = len(need)
    area = (x2 - x1 + 1) * (y2 - y1 + 1)
    need.append(area)
    for x in range(x1, x2 + 1):
        for y in range(y1, y2 + 1):
            look[fast(x, y)] = id

A lambda named fast converts a coordinate pair into a single integer key. The list need stores, for each artifact, the total number of cells it occupies. The dictionary look records every cell that belongs to any artifact, mapping the integer key to the artifact’s index. The nested loops enumerate all cells inside each artifact’s rectangle, guaranteeing that every covered cell is represented in look.

Processing dig operations

for x, y in dig:
    pos = fast(x, y)
    id = look.get(pos, -1)
    if id != -1:
        need[id] -= 1

Each dig coordinate is transformed with the same fast function, then looked up in look. If the cell is part of an artifact (id not equal to -1), the corresponding entry in need is decremented, reflecting that one more piece of that artifact has been uncovered.

Counting fully uncovered artifacts

return need.count(0)

After all digs have been processed, the method returns the number of entries in need that have reached zero, indicating that every cell of those artifacts has been dug.

Edge Cases Handled

When a dig occurs on a cell that does not belong to any artifact, the lookup returns -1 and the conditional guard prevents any modification of need. This safely ignores irrelevant digs without raising errors.

If multiple artifacts share no overlapping cells, the mapping in look remains one-to-one, and each dig affects at most a single artifact.

Artifacts of size one, two, or four cells are all correctly accounted for because the area calculation uses the inclusive range (x2 - x1 + 1) * (y2 - y1 + 1).

When the dig list contains duplicate coordinates, each occurrence will decrement the same artifact’s counter repeatedly. The code does not guard against over-decrementing, but because the problem definition typically guarantees that each cell is dug at most once, the implementation behaves correctly under the expected input constraints.

If the artifacts list is empty, need stays empty, and the final count(0) returns zero, which matches the logical expectation that no artifacts can be uncovered.

If the dig list is empty, no counters are changed, and the result reflects that only artifacts with an initial area of zero (which cannot occur) would be counted, so the method correctly returns zero.

Performance Optimizations

The lambda fast collapses a two-dimensional coordinate into a single integer, allowing the dictionary look to use integer keys instead of tuple keys. Integer hashing in Python is faster than tuple hashing, which reduces the overhead of lookups during the dig phase.

Storing the total cell count for each artifact in the list need enables constant-time updates when a cell is uncovered. The method avoids scanning the entire artifact region on each dig; it directly accesses the artifact’s counter via the identifier retrieved from look.

The use of dict.get with a default value eliminates the need for an explicit existence check before accessing the dictionary, streamlining the dig loop.

By pre-computing the full set of covered cells before processing digs, the algorithm ensures that each dig operation performs only a single dictionary lookup and a simple integer decrement, which is optimal for the given problem size.

The final need.count(0) leverages the built-in list method that is implemented in C, providing a fast way to tally fully uncovered artifacts without writing an explicit loop in Python.

Imagine a big square grid laid out on the floor, like a giant game board. Hidden underneath this board are several special treasures, each occupying a specific rectangular space. Some treasures are small and cover only one square, while others are larger and cover two or four squares.

The first part of the operation sets up a helpful index. It walks through every single treasure from start to finish. It notes exactly how many squares each treasure covers and keeps a memory list of which treasure belongs under which square coordinate. A special trick turns the two-part coordinate of a square into a single number, making it much easier to remember where everything is hidden.

After the setup is complete, the process begins to play the role of a treasure hunter. It looks at every spot where a shovel has dug into the ground. For each dig, it checks the memory list to see if a piece of a treasure is hiding there. If a treasure part is found, the count for that specific treasure is reduced by one.

Once all the digging is finished, the code counts how many treasures have had their entire area uncovered. If a treasure has a count of zero, it means every single one of its hidden squares was successfully found by the digger.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

not analyzed yet

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Python		Java				TS
	WalkCCC	C++	Python		Java
	leetcode.ca	C++	Python		Java		Go	Rust	TS
	Progiez	C++	Python		Java
github	black-shadows	C++
	charles-wangkai				Java
	fsq	C++
	JoshCrozier			JS
	lkwq007		Python
	suxrobGM					C#
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, Rust, TypeScript
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
fsq	C++
JoshCrozier	JavaScript
lkwq007	Python
suxrobGM	C#

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality