Watch 6 video solutions for K Highest Ranked Items Within a Price Range, a medium level problem involving Array, Breadth-First Search, Sorting. This walkthrough by Bro Coders has 1,413 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |