Scale Engineer

K Highest Ranked Items Within a Price Range

Med
#1955Time: O(V + P_k * log L_max), where `V` is the number of cells visited, `P_k` is the number of valid items found, and `L_max` is the max items at a single level. The worst case is `O(M*N * log(M*N))`, but the average case is often much better.Space: O(M*N). Required for the BFS queue and the `visited` matrix. The `itemsOnLevel` list can also grow up to `O(M*N)` in the worst case.1 company
Algorithms
SortingBreadth-First Search
Data structures
ArrayHeap (Priority Queue)Matrix
Companies
Booking.com

Prompt

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.
  • All other positive integers represent the price of an item in that cell. You may also freely move to and from these item cells.

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:

  1. Distance, defined as the length of the shortest path from the start (shorter distance has a higher rank).
  2. Price (lower price has a higher rank, but it must be in the price range).
  3. The row number (smaller row number has a higher rank).
  4. The column number (smaller column number 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.length
  • n == grid[i].length
  • 1 <= m, n <= 105
  • 1 <= m * n <= 105
  • 0 <= grid[i][j] <= 105
  • pricing.length == 2
  • 2 <= low <= high <= 105
  • start.length == 2
  • 0 <= row <= m - 1
  • 0 <= col <= n - 1
  • grid[row][col] > 0
  • 1 <= k <= m * n

Approaches

3 approaches with complexity analysis and trade-offs.

This approach leverages the properties of Breadth-First Search more effectively. BFS naturally explores the grid in layers of increasing distance. By processing items level by level, we can find the highest-ranked items in the correct order of the primary ranking criterion (distance). This allows us to stop the search as soon as we have found k items, avoiding unnecessary exploration of the grid.

Algorithm

  • Initialize an empty list result to store the answers.
  • Initialize a BFS queue with the start coordinates and a visited matrix.
  • Start a while loop that runs as long as the queue is not empty. This loop represents processing levels.
    • Inside the loop, get the current levelSize of the queue.
    • Create a temporary list itemsOnLevel to store valid items found at the current distance.
    • Loop levelSize times to process all nodes at the current level:
      • Dequeue a cell (r, c).
      • If grid[r][c] is a valid item within the price range, add [price, r, c] to itemsOnLevel.
      • Enqueue all valid, unvisited neighbors.
    • After the inner loop, sort itemsOnLevel based on price, then row, then column.
    • Iterate through the sorted itemsOnLevel and add each item's coordinates [r, c] to the result list.
    • If result.size() becomes equal to k, return result immediately.
  • If the while loop finishes (queue becomes empty) and we have fewer than k items, return the result list as is.

Walkthrough

The algorithm works by performing a level-order (or layer-by-layer) BFS.

  1. Initialization: We start a BFS from the start cell. We use a queue for the BFS, a visited set or array to avoid cycles, and a list to store the final results.
  2. Level-Order Traversal: The BFS proceeds in levels, where each level corresponds to a specific distance from the start. In each iteration of the main loop, we process all nodes at the current distance.
    • We find all items at the current level that are within the price range and add them to a temporary list for this level.
    • Since all items found in the same level have the same distance, we only need to sort this temporary list based on the remaining criteria: price, row, and column.
    • After sorting, we add these items to our final result list.
  3. Early Exit: We continuously check the size of our result list. As soon as it contains k items, we have found the k highest-ranked items because any item found in subsequent BFS levels will have a greater distance and thus a lower rank. We can then terminate the BFS and return the result. If the BFS completes before we find k items, we return all the valid items found.
import java.util.*; class Solution {    public List<List<Integer>> highestRankedKItems(int[][] grid, int[] pricing, int[] start, int k) {        int m = grid.length;        int n = grid[0].length;        int low = pricing[0];        int high = pricing[1];         List<List<Integer>> result = new ArrayList<>();        Queue<int[]> queue = new LinkedList<>();        boolean[][] visited = new boolean[m][n];         queue.offer(new int[]{start[0], start[1]});        visited[start[0]][start[1]] = true;         int[] dr = {-1, 1, 0, 0};        int[] dc = {0, 0, -1, 1};         while (!queue.isEmpty()) {            int levelSize = queue.size();            List<int[]> itemsOnLevel = new ArrayList<>();             for (int i = 0; i < levelSize; i++) {                int[] curr = queue.poll();                int r = curr[0];                int c = curr[1];                int price = grid[r][c];                 if (price > 1 && price >= low && price <= high) {                    itemsOnLevel.add(new int[]{price, r, c});                }                 for (int j = 0; j < 4; j++) {                    int nr = r + dr[j];                    int nc = c + dc[j];                     if (nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] != 0 && !visited[nr][nc]) {                        visited[nr][nc] = true;                        queue.offer(new int[]{nr, nc});                    }                }            }             // Sort items found on the current level            Collections.sort(itemsOnLevel, (a, b) -> {                if (a[0] != b[0]) return a[0] - b[0]; // price                if (a[1] != b[1]) return a[1] - b[1]; // row                return a[2] - b[2]; // col            });             // Add sorted items to result until we have k items            for (int[] item : itemsOnLevel) {                if (result.size() < k) {                    result.add(Arrays.asList(item[1], item[2]));                }            }            if (result.size() == k) {                return result;            }        }         return result;    }}

Complexity

Time

O(V + P_k * log L_max), where `V` is the number of cells visited, `P_k` is the number of valid items found, and `L_max` is the max items at a single level. The worst case is `O(M*N * log(M*N))`, but the average case is often much better.

Space

O(M*N). Required for the BFS queue and the `visited` matrix. The `itemsOnLevel` list can also grow up to `O(M*N)` in the worst case.

Trade-offs

Pros

  • More efficient on average than the brute-force approach, especially if k is small and the highest-ranked items are close to the start.

  • Logically clean as it processes items in the order of the most important ranking criterion (distance).

  • Avoids traversing the entire grid if not necessary due to the early exit condition.

Cons

  • The worst-case time complexity is similar to the brute-force approach if k is large and items are distributed unfavorably across levels.

  • Can be less efficient than the heap-based approach in specific worst-case scenarios where a single level contains a very large number of items.

Solutions

class Solution {public  List<List<Integer>> highestRankedKItems(int[][] grid, int[] pricing,                                          int[] start, int k) {    int m = grid.length, n = grid[0].length;    int row = start[0], col = start[1];    int low = pricing[0], high = pricing[1];    List<int[]> items = new ArrayList<>();    if (low <= grid[row][col] && grid[row][col] <= high) {      items.add(new int[]{0, grid[row][col], row, col});    }    grid[row][col] = 0;    Deque<int[]> q = new ArrayDeque<>();    q.offer(new int[]{row, col, 0});    int[] dirs = {-1, 0, 1, 0, -1};    while (!q.isEmpty()) {      int[] p = q.poll();      int i = p[0], j = p[1], d = p[2];      for (int l = 0; l < 4; ++l) {        int x = i + dirs[l], y = j + dirs[l + 1];        if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] > 0) {          if (low <= grid[x][y] && grid[x][y] <= high) {            items.add(new int[]{d + 1, grid[x][y], x, y});          }          grid[x][y] = 0;          q.offer(new int[]{x, y, d + 1});        }      }    }    items.sort((a, b)->{      if (a[0] != b[0]) {        return a[0] - b[0];      }      if (a[1] != b[1]) {        return a[1] - b[1];      }      if (a[2] != b[2]) {        return a[2] - b[2];      }      return a[3] - b[3];    });    List<List<Integer>> ans = new ArrayList<>();    for (int i = 0; i < items.size() && i < k; ++i) {      int[] p = items.get(i);      ans.add(Arrays.asList(p[2], p[3]));    }    return ans;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem