Skip to content
MediumHeapAI interview only

K Highest Ranked Items Within A Price Range

Asked atamazongoogleuber

01 · Problem

A shop floor is described by an m x n integer grid:

  • 0 is a wall that cannot be entered;
  • 1 is an empty walkway cell;
  • any value greater than 1 is 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:

  1. shorter shortest-path distance from start ranks higher;
  2. then lower price;
  3. then smaller row index;
  4. 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

Example 01
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]]

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.

Example 02
Input
grid = [[1,4,1],[4,1,2],[1,1,1]], pricing = [2,4], start = [1,1], k = 2
Output
[[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.

Example 03
Input
grid = [[1,0,3],[1,0,1],[1,0,2]], pricing = [2,3], start = [0,0], k = 2
Output
[]

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)
05 · Two ways to work on it

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.