K Highest Ranked Items Within A Price Range
01 · Problem
A shop floor is described by an m x n integer grid:
0is a wall that cannot be entered;1is an empty walkway cell;- any value greater than
1is a cell holding an item with that price (you can also walk through it).
Moving to an adjacent cell (up, down, left, right) takes one step. You start at start = [row, col], which is never a wall. You are interested in items whose price lies in the inclusive range pricing = [low, high].
Rank every reachable item in range using these keys, in order:
- shorter shortest-path distance from
startranks higher; - then lower price;
- then smaller row index;
- then smaller column index.
Return the positions [row, col] of the k highest-ranked items, best first. If fewer than k items qualify, return all of them in rank order (an empty list if none). The start cell itself counts, with distance 0, if it holds an in-range item.
02 · Examples
grid = [[1,2,0,1],[1,3,0,1],[0,2,5,1]], pricing = [2,5], start = [0,0], k = 3
[[0,1],[1,1],[2,1]]
Reachable in-range items: (0,1) at distance 1, (1,1) at distance 2, (2,1) at distance 3, (2,2) at distance 4. The three closest are returned in that order.
grid = [[1,4,1],[4,1,2],[1,1,1]], pricing = [2,4], start = [1,1], k = 2
[[1,2],[0,1]]
Three items sit at distance 1: (0,1) price 4, (1,0) price 4 and (1,2) price 2. Lower price wins first, so (1,2) ranks highest; the two price-4 items tie and the smaller row puts (0,1) next.
grid = [[1,0,3],[1,0,1],[1,0,2]], pricing = [2,3], start = [0,0], k = 2
[]
The wall column separates the start from both items, so nothing is reachable and the answer is empty.
03 · Constraints
- 01m == grid.length, n == grid[i].length
- 021 <= m, n <= 105 and 1 <= m * n <= 105
- 030 <= grid[i][j] <= 105
- 04pricing.length == 2 and 2 <= low <= high <= 105
- 05start.length == 2, grid[start[0]][start[1]] != 0, and 1 <= k <= m * n
04 · Optimal complexity
- Time
- O(mn log k)
- Space
- O(mn)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.