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 * nProblem Overview: You start at a position in a grid representing a store. Each cell contains a price or a wall. The task is to find the k highest ranked items whose prices fall within a given range. Ranking follows strict rules: shortest distance from the start first, then lower price, then smaller row index, then smaller column index.
Approach 1: Breadth-First Search (BFS) with Sorting (Time: O(mn log(mn)), Space: O(mn))
The grid behaves like an unweighted graph, so Breadth-First Search naturally finds cells in order of increasing distance from the start. Traverse the grid using BFS while tracking visited cells. Whenever you encounter a cell whose value falls within the price range, store it along with its ranking attributes: distance, price, row, and column. After the traversal finishes, sort the collected candidates using the ranking rules and return the first k positions. Sorting ensures the correct ordering across all valid items.
This approach is straightforward and easy to reason about. BFS guarantees correct distance ordering, while a final sorting step resolves ties using price and coordinates. The downside is that you may collect many candidates and then sort them, which increases the overall cost.
Approach 2: BFS with Priority Queue (Time: O(mn log k), Space: O(mn))
This method still uses BFS to explore the matrix in increasing distance order, but instead of storing every candidate, it maintains a bounded priority queue. During traversal, each valid item is pushed into the heap with its ranking tuple (distance, price, row, col). If the heap grows larger than k, remove the lowest priority element according to the ranking rules. This keeps only the best k candidates while scanning the grid.
Because the heap never stores more than k elements, insertion and removal cost O(log k). The BFS still touches each reachable cell once, but the ranking maintenance becomes more efficient than sorting all candidates at the end.
Recommended for interviews: Start by explaining the BFS traversal since the grid is an unweighted graph and distance is the primary ranking factor. The BFS + sorting approach clearly demonstrates the ranking logic and is easy to implement. The BFS with a priority queue is the more optimized solution and shows stronger algorithmic thinking, especially when the grid contains many candidate items but only a small k is required.
This approach involves using BFS to navigate through the grid starting from the given 'start' position. During the BFS, calculate the distance of each item from the start and filter based on the price range. Once the valid items are identified, sort them according to the criteria specified (distance, price, row, column) and pick the top k items.
The Python solution uses a deque for the BFS queue to ensure efficient popping from the left. We use a priority queue (min-heap) to keep track of items based on the ranking criteria, storing tuples of the form (distance, price, x-coordinate, y-coordinate). The result list is constructed by popping the top k items from the heap.
Python
JavaScript
Time Complexity: O(m * n * log(m * n)), as we potentially explore each cell and sort up to m * n items.
Space Complexity: O(m * n), due to additional space for queues and visited tracking.
This approach combines BFS with a priority queue to dynamically maintain the top k items. As we perform BFS, items are immediately added to the priority queue with the necessary criteria for comparison, maintaining only the top k items efficiently without needing to sort all possible items at the end.
The C++ solution uses a BFS that incorporates a priority queue to maintain the top k items by criteria. The BFS is similar to a standard traversal but continuously updates the priority queue using a custom comparator to ensure the items are ranked according to distance, price, and then position. Once BFS is complete, the selected items are ordered by their criteria and returned.
Time Complexity: O(m * n * log(k)), where k is much smaller than m*n, optimizing storage in the priority queue.
Space Complexity: O(k + m * n), using additional space for the visit tracking and priority queue.
We can start from (row, col) and use breadth-first search to find all items with prices in the range [low, high]. Store the distance, price, row coordinate, and column coordinate of these items in the array pq.
Finally, sort pq by distance, price, row coordinate, and column coordinate, and return the coordinates of the first k items.
The time complexity is O(m times n times log (m times n)), and the space complexity is O(m times n). Here, m and n are the number of rows and columns of the 2D array grid, respectively.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Breadth-First Search (BFS) with Sorting | Time Complexity: O(m * n * log(m * n)), as we potentially explore each cell and sort up to m * n items. |
| Breadth-First Search with Priority Queue | Time Complexity: O(m * n * log(k)), where k is much smaller than m*n, optimizing storage in the priority queue. |
| BFS + Sorting | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| BFS with Sorting | O(mn log(mn)) | O(mn) | Simple implementation when the number of valid items is small or clarity is preferred |
| BFS with Priority Queue | O(mn log k) | O(mn) | Better when the grid is large but only the top k ranked items are required |
2146 K Highest Ranked Items Within a Price Range | LeetCode 2146 || BiWeekly- 70 || Graph || BFS || • Bro Coders • 1,413 views views
Watch 5 more video solutions →Practice K Highest Ranked Items Within a Price Range with our built-in code editor and test cases.
Practice on FleetCode