Abstract / Summary

Find the top k items with the highest rank that fall within a given price range from a list of items.

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 47% (40k+ submissions).

Typical patterns to solve this problem:

• Array
• Breadth First Search
• Heap (Priority Queue)
• Matrix
• Sorting

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 provided implementation solves a grid-based search problem by performing a breadth-first traversal from a given start cell, collecting items whose price falls within a specified range, and then emitting the coordinates of the top k items according to a three-level ranking: distance from the start, price, and row/column order. The algorithm is encapsulated in a single method of the Solution class and returns a generator that yields the selected coordinates.

Algorithm Overview

The core of the solution is a breadth-first search (BFS) that explores the grid in expanding rings of steps. Each visited cell is examined for eligibility as an item, and eligible items are stored together with their distance and price. After the BFS completes, the collected items are sorted according to the required ranking criteria, and the first k entries are yielded.

Initialization

The method begins by preparing several variables that define the search space and the constraints.

result = []
height = len(grid)
width  = len(grid[0])

low, high = pricing

result will accumulate candidate items. height and width capture the grid dimensions for bounds checking. The price interval is unpacked into low and high.

A compact representation of the four cardinal directions is created with a single tuple, and a double-ended queue (deque) is seeded with the start position and an initial step count of zero.

deltas = ( 0, +1, 0, -1, 0 )
todo   = deque([ ( 0, start[0], start[1] ) ]) # steps, y, x

The deltas tuple enables iteration over neighbor offsets without constructing separate lists for each direction.

Breadth-First Search Loop

The BFS proceeds while there are pending positions in todo. Each iteration extracts the next cell together with the number of steps taken to reach it.

while todo:
    steps, y, x = todo.popleft()

Bounds and Wall Handling

Immediately after extraction, the code checks whether the coordinates lie outside the grid. If they do, the iteration is aborted early.

if x < 0 or x == width or y < 0 or y == height:
    continue

A second guard discards cells that are either walls (represented by a zero price) or have already been visited. The same condition also serves to prevent re-processing of previously explored cells.

price = grid[y][x]
if price == 0: # wall or already visited
    continue

In-Place Visited Marking

When a cell passes the above checks, it is marked as visited by overwriting its value with zero. This in-place mutation eliminates the need for an auxiliary visited matrix, reducing memory pressure and improving cache locality.

grid[y][x] = 0 # mark as visited

Item Collection

If the cell’s price lies within the inclusive range [low, high], a tuple containing the distance, price, and coordinates is appended to result. The tuple ordering directly reflects the ranking criteria: distance first, then price, then row and column.

if low <= price <= high:
    result.append( ( steps, price, y, x ))

Neighbor Expansion

The algorithm expands to the four orthogonal neighbors using the pre-computed deltas. By zipping the tuple with a one-element offset slice, each pair (dx, dy) is produced without allocating separate direction vectors.

for dx, dy in zip(deltas, deltas[1 :]):
    todo.append(( steps + 1, y + dy, x + dx ))

Each neighbor is enqueued with an incremented step count, ensuring that the BFS explores cells in order of increasing distance from the start.

Item Ranking and Result Generation

After the BFS exhausts all reachable cells, the accumulated candidate items are sorted using Python’s built-in sorted. Because the tuples were stored in the exact ranking order, a simple lexical sort yields the correct priority.

for steps, price, y, x in sorted(result)[ : k]:
    yield y, x

The slice [:k] selects the first k entries, and the generator yields each coordinate pair as a tuple. This lazy emission allows the caller to consume results without constructing an intermediate list of all sorted items.

Edge Cases Handled

The code gracefully deals with several boundary conditions. Out-of-bounds coordinates are filtered before any array access, preventing index errors. Cells containing a zero value are treated as impassable walls, and the same check also serves to skip cells that have already been visited, ensuring that each grid location is processed at most once. The price filter respects the inclusive nature of the interval, correctly handling items whose price equals either endpoint. Finally, if fewer than k eligible items are discovered, the slice operation simply yields all available entries without raising an exception.

Performance Optimizations

In-place mutation of the input grid to mark visited cells eliminates the overhead of a separate visited structure, saving memory and improving locality. The use of deque provides constant-time insertion and removal from both ends, which is essential for an efficient BFS. The compact deltas tuple and the zip construct avoid repeated allocation of direction lists, reducing per-iteration overhead. Leveraging Python’s highly optimized sorted function for the final ranking step benefits from C-level performance, making the ordering phase fast even for a large number of candidate items. The generator pattern for result emission avoids building a full list of output coordinates, allowing the caller to process results incrementally.

Imagine a magical treasure map where every square has a special number representing how much it costs. Some squares are gold, some are walls that cannot be passed, and some are just empty paths. The goal is to find the best treasures while walking through this grid.

To start, imagine standing on a magic starting square. From there, it is possible to step to the North, South, East, or West. Every step takes a little bit of time, so we keep track of how many steps have been taken to get to each place.

As the journey continues, we look at the cost of the ground under our feet. If the cost is a fair price that falls between the lowest and highest price allowed, we put that spot on a list of treasures to remember. Because walls might be in the way or we might accidentally walk in a circle, we mark every spot we visit with a zero so that we never visit the same place twice.

Once we have explored everywhere we can walk, we look at the list of all the treasures found. We organize them by how many steps it took to reach them, then by how much they cost, and finally by their position on the map. This helps decide which items are the most special. After everything is nicely organized, we pick out the best ones up to the number asked for and share where those treasures are hidden.

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

Time: loglinear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

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	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, 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