#2146

Medium

auto_awesomeArray plus Breadth-First Search

LeetCode Problem Workspace

K Highest Ranked Items Within a Price Range

Use BFS to rank reachable shop items by distance, price, row, and column, then return the best k coordinates.

array breadth first search sorting heap priority queue matrix

Problem Statement

You are given a shop grid where 0 means blocked, 1 means empty walkable space, and values greater than 1 are walkable cells containing items priced by that value. Starting from the given position, you can move one step at a time in the four cardinal directions, but only through nonzero cells.

Your goal is to return the coordinates of the top k reachable items whose prices are within the inclusive range [low, high]. Ranking is not based on price alone. Items are ordered first by shortest distance from start, then by lower price, then by smaller row, and finally by smaller column, so the solution must combine BFS traversal with careful tie handling.

Examples

Example 1

Input: grid = [[1,2,0,1],[1,3,0,1],[0,2,5,1]], pricing = [2,5], start = [0,0], k = 3

Output: [[0,1],[1,1],[2,1]]

You start at (0,0). With a price range of [2,5], we can take items from (0,1), (1,1), (2,1) and (2,2). The ranks of these items are:

(0,1) with distance 1
(1,1) with distance 2
(2,1) with distance 3
(2,2) with distance 4 Thus, the 3 highest ranked items in the price range are (0,1), (1,1), and (2,1).

Example 2

Input: grid = [[1,2,0,1],[1,3,3,1],[0,2,5,1]], pricing = [2,3], start = [2,3], k = 2

Output: [[2,1],[1,2]]

You start at (2,3). With a price range of [2,3], we can take items from (0,1), (1,1), (1,2) and (2,1). The ranks of these items are:

(2,1) with distance 2, price 2
(1,2) with distance 2, price 3
(1,1) with distance 3
(0,1) with distance 4 Thus, the 2 highest ranked items in the price range are (2,1) and (1,2).

Example 3

Input: grid = [[1,1,1],[0,0,1],[2,3,4]], pricing = [2,3], start = [0,0], k = 3

Output: [[2,1],[2,0]]

You start at (0,0). With a price range of [2,3], we can take items from (2,0) and (2,1). The ranks of these items are:

(2,1) with distance 5
(2,0) with distance 6 Thus, the 2 highest ranked items in the price range are (2,1) and (2,0). Note that k = 3 but there are only 2 reachable items within the price range.

Constraints

m == grid.length
n == grid[i].length
1 <= m, n <= 105
1 <= m * n <= 105
0 <= grid[i][j] <= 105
pricing.length == 2
2 <= low <= high <= 105
start.length == 2
0 <= row <= m - 1
0 <= col <= n - 1
grid[row][col] > 0
1 <= k <= m * n

Solution Approach

Run BFS because distance is the first rank key

Start from the given cell and perform breadth-first search over walkable cells only. BFS guarantees the first time you reach a cell is its minimum distance, which matches the most important ranking rule in this problem. Mark visited cells immediately when pushing them into the queue so you do not revisit the same location and distort the traversal cost.

Collect only valid items during traversal

While expanding BFS, check whether the current cell contains an item whose value is between low and high. If it does, store a record containing distance, price, row, and column. This keeps the candidate list tied to the exact ranking fields instead of forcing a second pass over the whole grid or mixing blocked and unreachable cells into the result.

Sort candidates by the full ranking tuple and take k

After BFS finishes, sort the collected records by distance, then price, then row, then column, and return the first k coordinates. This approach is simple and reliable because BFS already handled reachability and minimum distance, while sorting resolves ties exactly as the problem requires. A heap variant can reduce stored results, but full collection plus sort is usually the clearest implementation.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Let N be the number of cells in the grid. BFS visits each reachable cell at most once, so traversal costs O(N). If R reachable items fall inside the price range, sorting them costs O(R log R), making the total time O(N + R log R). The space cost is O(N) for the visited structure and BFS queue, plus O(R) for collected ranked items.

What Interviewers Usually Probe

They expect you to notice that shortest path on an unweighted grid means BFS, not Dijkstra or DFS.
They are checking whether you can preserve the exact rank order: distance, price, row, then column.
They want a solution that filters unreachable items naturally instead of scanning and ranking the whole matrix blindly.

Common Pitfalls or Variants

Common pitfalls

Sorting by price before distance gives the wrong answer because this problem ranks by BFS depth first.
Marking visited after popping instead of after pushing can enqueue the same cell multiple times and bloat the search.
Treating every positive cell as a valid answer is wrong because value 1 is walkable space, not a priced item in range unless the range includes 1, which it never does here since low is at least 2.

Follow-up variants

Keep only the best k items in a max-heap while running BFS instead of sorting every candidate at the end.
Return the ranked item values as well as coordinates, which adds output formatting but keeps the same BFS ranking logic.
Change movement rules to eight directions or weighted steps, which would break plain BFS and require a different shortest-path method.

FAQ

What is the key pattern in K Highest Ranked Items Within a Price Range?

The key pattern is array plus breadth-first search. BFS computes the shortest distance from the start in an unweighted grid, and that distance is the first ranking field, so traversal order matters before sorting the final candidates.

Why is BFS better than DFS for LeetCode 2146?

DFS can reach an item through a longer path before a shorter one, so it does not naturally produce minimum distance. Since this problem ranks items by shortest distance first, BFS is the correct fit.

Do I need to sort the whole grid?

No. Only reachable cells discovered by BFS can matter, and only cells with prices inside the range become candidates. Sorting the entire grid wastes work and can mix in blocked or unreachable positions.

Can I stop BFS as soon as I collect k items?

Not safely in the general case. You may find k items at one distance, but more items at that same distance could still appear later in the BFS layer and beat some of your current picks by lower price, row, or column.

What tie breakers matter after distance?

After smaller distance, prefer lower price, then smaller row, then smaller column. Missing even one of these tie breakers will fail hidden cases where multiple reachable items appear in the same BFS layer.

terminal

Solution

Solution 1: BFS + Sorting

We can start from $(\textit{row}, \textit{col})$ and use breadth-first search to find all items with prices in the range $[\textit{low}, \textit{high}]$. Store the distance, price, row coordinate, and column coordinate of these items in the array $\textit{pq}$.

class Solution:
    def highestRankedKItems(
        self, grid: List[List[int]], pricing: List[int], start: List[int], k: int
    ) -> List[List[int]]:
        m, n = len(grid), len(grid[0])
        row, col = start
        low, high = pricing
        q = deque([(row, col)])
        pq = []
        if low <= grid[row][col] <= high:
            pq.append((0, grid[row][col], row, col))
        grid[row][col] = 0
        dirs = (-1, 0, 1, 0, -1)
        step = 0
        while q:
            step += 1
            for _ in range(len(q)):
                x, y = q.popleft()
                for a, b in pairwise(dirs):
                    nx, ny = x + a, y + b
                    if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] > 0:
                        if low <= grid[nx][ny] <= high:
                            pq.append((step, grid[nx][ny], nx, ny))
                        grid[nx][ny] = 0
                        q.append((nx, ny))
        pq.sort()
        return [list(x[2:]) for x in pq[:k]]

Continue Practicing

#2503 maximum number of points from grid queries #2290 minimum obstacle removal to reach corner #1878 get biggest three rhombus sums in a grid