You are given a 0-indexed 2D integer array grid of size m x n that represents a map of the items in a shop. The integers in the grid represent the following:
0 represents a wall that you cannot pass through.1 represents an empty cell that you can freely move to and from.It takes 1 step to travel between adjacent grid cells.
You are also given integer arrays pricing and start where pricing = [low, high] and start = [row, col] indicates that you start at the position (row, col) and are interested only in items with a price in the range of [low, high] (inclusive). You are further given an integer k.
You are interested in the positions of the k highest-ranked items whose prices are within the given price range. The rank is determined by the first of these criteria that is different:
start (shorter distance has a higher rank).Return the k highest-ranked items within the price range sorted by their rank (highest to lowest). If there are fewer than k reachable items within the price range, return all of them.
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]] Explanation: 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]] Explanation: 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]] Explanation: 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.lengthn == grid[i].length1 <= m, n <= 1051 <= m * n <= 1050 <= grid[i][j] <= 105pricing.length == 22 <= low <= high <= 105start.length == 20 <= row <= m - 10 <= col <= n - 1grid[row][col] > 01 <= k <= m * nThe key idea for #2146 K Highest Ranked Items Within a Price Range is to explore the grid using Breadth-First Search (BFS) starting from the given starting cell. BFS guarantees that cells are visited in increasing order of distance, which is the first ranking criterion. While traversing, we check whether a cell’s price lies within the given pricing range and collect such items.
Each valid item must be ranked based on four priorities: distance from start, price, row, and column. After gathering candidates during BFS traversal, we can either store them and sort using the ranking rules or maintain a priority queue (heap) to efficiently track the best k items.
The grid is processed once using BFS, ensuring efficient traversal of reachable cells. Sorting or heap operations help extract the top-ranked items. The overall time complexity typically reaches O(m*n log(m*n)) in the worst case, with space usage proportional to the grid and candidate storage.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| BFS + Sorting | O(m*n log(m*n)) | O(m*n) |
| BFS + Priority Queue (Heap) | O(m*n log k) | O(m*n) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
Could you determine the rank of every item efficiently?
We can perform a breadth-first search from the starting position and know the length of the shortest path from start to every item.
Sort all the items according to the conditions listed in the problem, and return the first k (or all if less than k exist) items as the answer.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
BFS is used because it explores grid cells level by level, naturally ensuring the shortest distance from the starting point. Since distance is the primary ranking factor, BFS guarantees items are discovered in increasing order of distance.
A priority queue (heap) is often used to efficiently maintain the best k ranked items while traversing the grid. Alternatively, you can collect all valid candidates and sort them based on the ranking rules before selecting the top k.
Yes, this problem reflects common interview patterns involving BFS on grids, ranking rules, and heap-based selection. Variants of grid traversal combined with sorting or priority queues frequently appear in technical interviews.
The optimal approach uses Breadth-First Search (BFS) to traverse the grid from the starting position while maintaining ranking criteria. Valid items within the price range are collected and ranked by distance, price, row, and column. A priority queue or sorting step helps return the top k items efficiently.