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

Sorting Breadth-First Search

Data structures

Array Heap (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:

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

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.
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.
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.

1import java.util.*;2 3class Solution {4    public List<List<Integer>> highestRankedKItems(int[][] grid, int[] pricing, int[] start, int k) {5        int m = grid.length;6        int n = grid[0].length;7        int low = pricing[0];8        int high = pricing[1];9 10        List<List<Integer>> result = new ArrayList<>();11        Queue<int[]> queue = new LinkedList<>();12        boolean[][] visited = new boolean[m][n];13 14        queue.offer(new int[]{start[0], start[1]});15        visited[start[0]][start[1]] = true;16 17        int[] dr = {-1, 1, 0, 0};18        int[] dc = {0, 0, -1, 1};19 20        while (!queue.isEmpty()) {21            int levelSize = queue.size();22            List<int[]> itemsOnLevel = new ArrayList<>();23 24            for (int i = 0; i < levelSize; i++) {25                int[] curr = queue.poll();26                int r = curr[0];27                int c = curr[1];28                int price = grid[r][c];29 30                if (price > 1 && price >= low && price <= high) {31                    itemsOnLevel.add(new int[]{price, r, c});32                }33 34                for (int j = 0; j < 4; j++) {35                    int nr = r + dr[j];36                    int nc = c + dc[j];37 38                    if (nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] != 0 && !visited[nr][nc]) {39                        visited[nr][nc] = true;40                        queue.offer(new int[]{nr, nc});41                    }42                }43            }44 45            // Sort items found on the current level46            Collections.sort(itemsOnLevel, (a, b) -> {47                if (a[0] != b[0]) return a[0] - b[0]; // price48                if (a[1] != b[1]) return a[1] - b[1]; // row49                return a[2] - b[2]; // col50            });51 52            // Add sorted items to result until we have k items53            for (int[] item : itemsOnLevel) {54                if (result.size() < k) {55                    result.add(Arrays.asList(item[1], item[2]));56                }57            }58            if (result.size() == k) {59                return result;60            }61        }62 63        return result;64    }65}

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.

This approach first determines the shortest distance from the start cell to every other reachable cell using a Breadth-First Search (BFS). After the BFS is complete, it iterates through the entire grid, collects all items that fall within the specified price range, and stores them along with their calculated distance. Finally, it sorts this entire collection of valid items based on the four ranking criteria and returns the top k items.

Algorithm

Initialize a dist matrix of size m x n with -1 to mark cells as unvisited.
Create a queue for BFS and add the start cell. Set its distance to 0.
Perform BFS:
- While the queue is not empty, dequeue a cell (r, c).
- For each of its four neighbors (nr, nc):
  - If the neighbor is within grid bounds, is not a wall (grid[nr][nc] != 0), and has not been visited (dist[nr][nc] == -1):
    - Update its distance: dist[nr][nc] = dist[r][c] + 1.
    - Enqueue the neighbor.
Create a list candidates to store valid items.
Iterate through the grid from (0, 0) to (m-1, n-1):
- If a cell (r, c) is reachable (dist[r][c] != -1), contains an item (grid[r][c] > 1), and its price is in the range [low, high]:
  - Add [dist[r][c], grid[r][c], r, c] to candidates.
Sort the candidates list using a custom comparator based on distance, then price, then row, then column, all in ascending order.
Create a result list and add the row and column of the first k items from the sorted candidates list.
Return the result list.

Walkthrough

The algorithm consists of three main phases:

Distance Calculation (BFS): We perform a BFS starting from the start coordinates to compute the shortest distance to all reachable cells. A 2D array dist is used to store these distances, initialized to a value indicating unreachability (e.g., -1). The BFS queue stores [row, col] pairs. When we explore a cell, we update the distances of its unvisited neighbors and add them to the queue.
Item Collection: After computing all distances, we iterate through every cell of the grid. If a cell (r, c) contains an item (price > 1), is reachable, and its price is within the [low, high] range, we add a structure representing this item (e.g., a list or object containing [distance, price, row, col]) to a list called candidates.
Sorting and Selection: We sort the candidates list. The custom sorting logic will compare two items based on the ranking criteria in order: distance (ascending), price (ascending), row (ascending), and finally column (ascending). After sorting, we take the first k items from the list (or all items if there are fewer than k) and format them as [row, col] for the final output.

1import java.util.*;2 3class Solution {4    public List<List<Integer>> highestRankedKItems(int[][] grid, int[] pricing, int[] start, int k) {5        int m = grid.length;6        int n = grid[0].length;7        int low = pricing[0];8        int high = pricing[1];9        int startRow = start[0];10        int startCol = start[1];11 12        // 1. BFS to find distances13        int[][] dist = new int[m][n];14        for (int[] row : dist) {15            Arrays.fill(row, -1); // -1 represents unvisited/unreachable16        }17 18        Queue<int[]> queue = new LinkedList<>();19        queue.offer(new int[]{startRow, startCol});20        dist[startRow][startCol] = 0;21 22        int[] dr = {-1, 1, 0, 0};23        int[] dc = {0, 0, -1, 1};24 25        int head = 0;26        while(!queue.isEmpty()){27            int[] curr = queue.poll();28            int r = curr[0];29            int c = curr[1];30 31            for (int i = 0; i < 4; i++) {32                int nr = r + dr[i];33                int nc = c + dc[i];34 35                if (nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] != 0 && dist[nr][nc] == -1) {36                    dist[nr][nc] = dist[r][c] + 1;37                    queue.offer(new int[]{nr, nc});38                }39            }40        }41 42        // 2. Collect valid items43        List<int[]> candidates = new ArrayList<>();44        for (int r = 0; r < m; r++) {45            for (int c = 0; c < n; c++) {46                if (dist[r][c] != -1 && grid[r][c] > 1 && grid[r][c] >= low && grid[r][c] <= high) {47                    candidates.add(new int[]{dist[r][c], grid[r][c], r, c});48                }49            }50        }51 52        // 3. Sort candidates53        Collections.sort(candidates, (a, b) -> {54            if (a[0] != b[0]) return a[0] - b[0]; // distance55            if (a[1] != b[1]) return a[1] - b[1]; // price56            if (a[2] != b[2]) return a[2] - b[2]; // row57            return a[3] - b[3]; // col58        });59 60        // 4. Get top k results61        List<List<Integer>> result = new ArrayList<>();62        for (int i = 0; i < Math.min(k, candidates.size()); i++) {63            int[] item = candidates.get(i);64            result.add(Arrays.asList(item[2], item[3]));65        }66 67        return result;68    }69}

Complexity

Time

O(M*N * log(M*N)). The BFS takes `O(M*N)` time. Collecting items takes `O(M*N)`. Sorting up to `M*N` items takes `O(M*N * log(M*N))`, which dominates the complexity.

Space

O(M*N). This is for the `dist` matrix, the BFS queue, and the `candidates` list, all of which can take up to `O(M*N)` space in the worst case.

Trade-offs

Pros

Conceptually simple and easy to implement correctly.
Guarantees finding the correct answer by exhaustively checking and sorting all possibilities.

Cons

Inefficient due to sorting all valid items, even if k is very small.
The O(M*N * log(M*N)) time complexity can be slow for large grids.

This approach provides the best worst-case time complexity by combining BFS with a data structure optimized for "top K" problems: a max-heap. It avoids sorting large lists by only maintaining the k highest-ranked items seen so far. While it traverses the entire grid, its use of a heap makes the cost of processing each item very low.

Algorithm

Initialize a max-priority queue maxHeap of size k. The comparator will order items by distance, price, row, and column, all in descending order.
Initialize a visited matrix and a queue for BFS. Add [start_row, start_col, 0] (row, col, distance) to the BFS queue and mark the start cell as visited.
Perform BFS:
- While the BFS queue is not empty, dequeue a cell (r, c) with distance d.
- Check the price p = grid[r][c]. If p > 1 and low <= p <= high:
  - Create an item representation [d, p, r, c].
  - If maxHeap.size() < k, add the item.
  - Else if the new item has a higher rank than the heap's top, poll() the top and offer() the new item.
- For each unvisited, valid neighbor (nr, nc):
  - Mark as visited and enqueue [nr, nc, d + 1].
After the BFS, extract all items from the maxHeap into a temporary list.
Reverse the temporary list to sort items from highest rank to lowest.
Return the result.

Walkthrough

The algorithm proceeds as follows:

Grid Traversal (BFS): A single BFS is performed starting from the start cell to visit all reachable cells. The BFS queue stores tuples of (row, col, distance) to keep track of the distance as we traverse.
Candidate Filtering with a Max-Heap: A max-heap (implemented as a PriorityQueue in Java) is used to maintain the k highest-ranked items. The heap's comparison logic is the inverse of the ranking criteria (i.e., it's ordered by distance descending, then price descending, etc.). This ensures the root of the heap is always the lowest-ranked item among the current top k candidates.
- As the BFS visits each cell (r, c), if it's a valid item, we compare it with the top of the heap.
- If the heap's size is less than k, the new item is simply added.
- If the heap is full (size k), and the new item has a higher rank (is 'smaller' by ranking criteria) than the heap's top element, the top element is removed, and the new item is inserted. Otherwise, the new item is discarded.
Result Extraction: After the BFS has traversed the entire reachable grid, the max-heap contains the k highest-ranked items. These are extracted from the heap one by one. Since a max-heap will yield them in lowest-to-highest rank order, we add them to a list and then reverse it to achieve the final sorted output.

1import java.util.*;2 3class Solution {4    public List<List<Integer>> highestRankedKItems(int[][] grid, int[] pricing, int[] start, int k) {5        int m = grid.length;6        int n = grid[0].length;7        int low = pricing[0];8        int high = pricing[1];9 10        // Max-heap to store top k items. The comparator is reversed to keep the lowest-ranked item at the top.11        PriorityQueue<int[]> maxHeap = new PriorityQueue<>((a, b) -> {12            if (a[0] != b[0]) return b[0] - a[0]; // distance13            if (a[1] != b[1]) return b[1] - a[1]; // price14            if (a[2] != b[2]) return b[2] - a[2]; // row15            return b[3] - a[3]; // col16        });17 18        Queue<int[]> queue = new LinkedList<>();19        boolean[][] visited = new boolean[m][n];20 21        queue.offer(new int[]{start[0], start[1], 0}); // r, c, dist22        visited[start[0]][start[1]] = true;23 24        int[] dr = {-1, 1, 0, 0};25        int[] dc = {0, 0, -1, 1};26 27        while (!queue.isEmpty()) {28            int[] curr = queue.poll();29            int r = curr[0];30            int c = curr[1];31            int dist = curr[2];32            int price = grid[r][c];33 34            // Check if current cell is a valid item35            if (price > 1 && price >= low && price <= high) {36                int[] item = new int[]{dist, price, r, c};37                if (maxHeap.size() < k) {38                    maxHeap.offer(item);39                } else {40                    // Compare with the lowest-ranked item in the heap41                    int[] top = maxHeap.peek();42                    // If new item is higher rank (smaller values)43                    if (dist < top[0] || 44                       (dist == top[0] && price < top[1]) || 45                       (dist == top[0] && price == top[1] && r < top[2]) || 46                       (dist == top[0] && price == top[1] && r == top[2] && c < top[3])) {47                        maxHeap.poll();48                        maxHeap.offer(item);49                    }50                }51            }52 53            // Explore neighbors54            for (int i = 0; i < 4; i++) {55                int nr = r + dr[i];56                int nc = c + dc[i];57 58                if (nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] != 0 && !visited[nr][nc]) {59                    visited[nr][nc] = true;60                    queue.offer(new int[]{nr, nc, dist + 1});61                }62            }63        }64 65        // Extract results from heap66        LinkedList<List<Integer>> result = new LinkedList<>();67        while (!maxHeap.isEmpty()) {68            int[] item = maxHeap.poll();69            result.addFirst(Arrays.asList(item[2], item[3]));70        }71 72        return result;73    }74}

Complexity

Time

O(M*N * log(k)). The BFS visits each cell once, taking `O(M*N)`. For each of the `P` valid items found (where `P <= M*N`), we perform a heap operation which takes `O(log k)`. This gives a total time of `O(M*N + P*log k)`, which simplifies to `O(M*N * log k)`. This is the best worst-case complexity.

Space

O(M*N). The `visited` matrix and BFS queue require `O(M*N)` space. The heap requires `O(k)` space. The dominant factor is `O(M*N)`.

Trade-offs

Pros

Most efficient in terms of worst-case time complexity.
The O(log k) cost per item is very efficient, especially when k is much smaller than the total number of items.
Provides a robust performance guarantee regardless of item distribution.

Cons

Always needs to traverse the entire reachable grid, even if the top k items are found close to the start position.
Can be slightly more complex to implement due to the heap and its custom comparator.

Solutions

Solution

1class Solution {2public3  List<List<Integer>> highestRankedKItems(int[][] grid, int[] pricing,4                                          int[] start, int k) {5    int m = grid.length, n = grid[0].length;6    int row = start[0], col = start[1];7    int low = pricing[0], high = pricing[1];8    List<int[]> items = new ArrayList<>();9    if (low <= grid[row][col] && grid[row][col] <= high) {10      items.add(new int[]{0, grid[row][col], row, col});11    }12    grid[row][col] = 0;13    Deque<int[]> q = new ArrayDeque<>();14    q.offer(new int[]{row, col, 0});15    int[] dirs = {-1, 0, 1, 0, -1};16    while (!q.isEmpty()) {17      int[] p = q.poll();18      int i = p[0], j = p[1], d = p[2];19      for (int l = 0; l < 4; ++l) {20        int x = i + dirs[l], y = j + dirs[l + 1];21        if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] > 0) {22          if (low <= grid[x][y] && grid[x][y] <= high) {23            items.add(new int[]{d + 1, grid[x][y], x, y});24          }25          grid[x][y] = 0;26          q.offer(new int[]{x, y, d + 1});27        }28      }29    }30    items.sort((a, b)->{31      if (a[0] != b[0]) {32        return a[0] - b[0];33      }34      if (a[1] != b[1]) {35        return a[1] - b[1];36      }37      if (a[2] != b[2]) {38        return a[2] - b[2];39      }40      return a[3] - b[3];41    });42    List<List<Integer>> ans = new ArrayList<>();43    for (int i = 0; i < items.size() && i < k; ++i) {44      int[] p = items.get(i);45      ans.add(Arrays.asList(p[2], p[3]));46    }47    return ans;48  }49}

1class Solution {2public:3  vector<vector<int>> highestRankedKItems(vector<vector<int>> &grid,4                                          vector<int> &pricing,5                                          vector<int> &start, int k) {6    int m = grid.size(), n = grid[0].size();7    int row = start[0], col = start[1];8    int low = pricing[0], high = pricing[1];9    vector<tuple<int, int, int, int>> items;10    if (low <= grid[row][col] && grid[row][col] <= high)11      items.emplace_back(0, grid[row][col], row, col);12    queue<tuple<int, int, int>> q;13    q.emplace(row, col, 0);14    grid[row][col] = 0;15    vector<int> dirs = {-1, 0, 1, 0, -1};16    while (!q.empty()) {17      auto [i, j, d] = q.front();18      q.pop();19      for (int l = 0; l < 4; ++l) {20        int x = i + dirs[l], y = j + dirs[l + 1];21        if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y]) {22          if (low <= grid[x][y] && grid[x][y] <= high)23            items.emplace_back(d + 1, grid[x][y], x, y);24          grid[x][y] = 0;25          q.emplace(x, y, d + 1);26        }27      }28    }29    sort(items.begin(), items.end());30    vector<vector<int>> ans;31    for (int i = 0; i < items.size() && i < k; ++i) {32      auto [d, p, x, y] = items[i];33      ans.push_back({x, y});34    }35    return ans;36  }37};

1class Solution:2    def highestRankedKItems(self, grid: List[List[int]], pricing: List[int], start: List[int], k: int) -> List[List[int]]: m, n = len(grid), len(grid[0]) row, col, low, high = start + pricing items = [] if low <= grid[row][col] <= high: items . append([0, grid[row][col], row, col]) q = deque([(row, col, 0)]) grid[row][col] = 0 while q: i, j, d = q . popleft() for a, b in [[0, 1], [0, - 1], [1, 0], [- 1, 0]]: x, y = i + a, j + b if 0 <= x < m and 0 <= y < n and grid[x][y]: if low <= grid[x][y] <= high: items . append([d + 1, grid[x][y], x, y]) q . append((x, y, d + 1)) grid[x][y] = 0 items . sort() return [item[2:] for item in items][: k]

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 problem

Solution

1class Solution {2public3  List<List<Integer>> highestRankedKItems(int[][] grid, int[] pricing,4                                          int[] start, int k) {5    int m = grid.length, n = grid[0].length;6    int row = start[0], col = start[1];7    int low = pricing[0], high = pricing[1];8    List<int[]> items = new ArrayList<>();9    if (low <= grid[row][col] && grid[row][col] <= high) {10      items.add(new int[]{0, grid[row][col], row, col});11    }12    grid[row][col] = 0;13    Deque<int[]> q = new ArrayDeque<>();14    q.offer(new int[]{row, col, 0});15    int[] dirs = {-1, 0, 1, 0, -1};16    while (!q.isEmpty()) {17      int[] p = q.poll();18      int i = p[0], j = p[1], d = p[2];19      for (int l = 0; l < 4; ++l) {20        int x = i + dirs[l], y = j + dirs[l + 1];21        if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] > 0) {22          if (low <= grid[x][y] && grid[x][y] <= high) {23            items.add(new int[]{d + 1, grid[x][y], x, y});24          }25          grid[x][y] = 0;26          q.offer(new int[]{x, y, d + 1});27        }28      }29    }30    items.sort((a, b)->{31      if (a[0] != b[0]) {32        return a[0] - b[0];33      }34      if (a[1] != b[1]) {35        return a[1] - b[1];36      }37      if (a[2] != b[2]) {38        return a[2] - b[2];39      }40      return a[3] - b[3];41    });42    List<List<Integer>> ans = new ArrayList<>();43    for (int i = 0; i < items.size() && i < k; ++i) {44      int[] p = items.get(i);45      ans.add(Arrays.asList(p[2], p[3]));46    }47    return ans;48  }49}

1class Solution {2public:3  vector<vector<int>> highestRankedKItems(vector<vector<int>> &grid,4                                          vector<int> &pricing,5                                          vector<int> &start, int k) {6    int m = grid.size(), n = grid[0].size();7    int row = start[0], col = start[1];8    int low = pricing[0], high = pricing[1];9    vector<tuple<int, int, int, int>> items;10    if (low <= grid[row][col] && grid[row][col] <= high)11      items.emplace_back(0, grid[row][col], row, col);12    queue<tuple<int, int, int>> q;13    q.emplace(row, col, 0);14    grid[row][col] = 0;15    vector<int> dirs = {-1, 0, 1, 0, -1};16    while (!q.empty()) {17      auto [i, j, d] = q.front();18      q.pop();19      for (int l = 0; l < 4; ++l) {20        int x = i + dirs[l], y = j + dirs[l + 1];21        if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y]) {22          if (low <= grid[x][y] && grid[x][y] <= high)23            items.emplace_back(d + 1, grid[x][y], x, y);24          grid[x][y] = 0;25          q.emplace(x, y, d + 1);26        }27      }28    }29    sort(items.begin(), items.end());30    vector<vector<int>> ans;31    for (int i = 0; i < items.size() && i < k; ++i) {32      auto [d, p, x, y] = items[i];33      ans.push_back({x, y});34    }35    return ans;36  }37};

1class Solution:2    def highestRankedKItems(self, grid: List[List[int]], pricing: List[int], start: List[int], k: int) -> List[List[int]]: m, n = len(grid), len(grid[0]) row, col, low, high = start + pricing items = [] if low <= grid[row][col] <= high: items . append([0, grid[row][col], row, col]) q = deque([(row, col, 0)]) grid[row][col] = 0 while q: i, j, d = q . popleft() for a, b in [[0, 1], [0, - 1], [1, 0], [- 1, 0]]: x, y = i + a, j + b if 0 <= x < m and 0 <= y < n and grid[x][y]: if low <= grid[x][y] <= high: items . append([d + 1, grid[x][y], x, y]) q . append((x, y, d + 1)) grid[x][y] = 0 items . sort() return [item[2:] for item in items][: k]

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.