# K Highest Ranked Items Within a Price Range
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/k-highest-ranked-items-within-a-price-range)
Canonical: https://scaleengineer.com/dsa/problems/k-highest-ranked-items-within-a-price-range
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting), [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search)
**Data structures:** Array, Heap (Priority Queue), Matrix
**Companies:** [Booking.com](https://scaleengineer.com/companies/booking.com)
---
## Problem
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:**

![](https://assets.glich.co/dsa/k-highest-ranked-items-within-a-price-range/image0.png) 

**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:**

![](https://assets.glich.co/dsa/k-highest-ranked-items-within-a-price-range/image1.png) 

**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:**

![](https://assets.glich.co/dsa/k-highest-ranked-items-within-a-price-range/image2.png) 

**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
## Brute Force: BFS, Collect, and Full Sort
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.
**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.
**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.
### Explanation
The algorithm consists of three main phases:
1.  **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.
2.  **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`.
3.  **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.

```java
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];
        int startRow = start[0];
        int startCol = start[1];

        // 1. BFS to find distances
        int[][] dist = new int[m][n];
        for (int[] row : dist) {
            Arrays.fill(row, -1); // -1 represents unvisited/unreachable
        }

        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{startRow, startCol});
        dist[startRow][startCol] = 0;

        int[] dr = {-1, 1, 0, 0};
        int[] dc = {0, 0, -1, 1};

        int head = 0;
        while(!queue.isEmpty()){
            int[] curr = queue.poll();
            int r = curr[0];
            int c = curr[1];

            for (int i = 0; i < 4; i++) {
                int nr = r + dr[i];
                int nc = c + dc[i];

                if (nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] != 0 && dist[nr][nc] == -1) {
                    dist[nr][nc] = dist[r][c] + 1;
                    queue.offer(new int[]{nr, nc});
                }
            }
        }

        // 2. Collect valid items
        List<int[]> candidates = new ArrayList<>();
        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                if (dist[r][c] != -1 && grid[r][c] > 1 && grid[r][c] >= low && grid[r][c] <= high) {
                    candidates.add(new int[]{dist[r][c], grid[r][c], r, c});
                }
            }
        }

        // 3. Sort candidates
        Collections.sort(candidates, (a, b) -> {
            if (a[0] != b[0]) return a[0] - b[0]; // distance
            if (a[1] != b[1]) return a[1] - b[1]; // price
            if (a[2] != b[2]) return a[2] - b[2]; // row
            return a[3] - b[3]; // col
        });

        // 4. Get top k results
        List<List<Integer>> result = new ArrayList<>();
        for (int i = 0; i < Math.min(k, candidates.size()); i++) {
            int[] item = candidates.get(i);
            result.add(Arrays.asList(item[2], item[3]));
        }

        return result;
    }
}
```
### 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.

## Optimized Traversal: Level-by-Level BFS with Early Exit
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.
**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.
**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.
### Explanation
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.

```java
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;
    }
}
```
### 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.

## Efficient Selection: BFS with a Max-Heap for Top K
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.
**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)`.
**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.
### Explanation
The algorithm proceeds as follows:
1.  **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.
2.  **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.
3.  **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.

```java
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];

        // Max-heap to store top k items. The comparator is reversed to keep the lowest-ranked item at the top.
        PriorityQueue<int[]> maxHeap = new PriorityQueue<>((a, b) -> {
            if (a[0] != b[0]) return b[0] - a[0]; // distance
            if (a[1] != b[1]) return b[1] - a[1]; // price
            if (a[2] != b[2]) return b[2] - a[2]; // row
            return b[3] - a[3]; // col
        });

        Queue<int[]> queue = new LinkedList<>();
        boolean[][] visited = new boolean[m][n];

        queue.offer(new int[]{start[0], start[1], 0}); // r, c, dist
        visited[start[0]][start[1]] = true;

        int[] dr = {-1, 1, 0, 0};
        int[] dc = {0, 0, -1, 1};

        while (!queue.isEmpty()) {
            int[] curr = queue.poll();
            int r = curr[0];
            int c = curr[1];
            int dist = curr[2];
            int price = grid[r][c];

            // Check if current cell is a valid item
            if (price > 1 && price >= low && price <= high) {
                int[] item = new int[]{dist, price, r, c};
                if (maxHeap.size() < k) {
                    maxHeap.offer(item);
                } else {
                    // Compare with the lowest-ranked item in the heap
                    int[] top = maxHeap.peek();
                    // If new item is higher rank (smaller values)
                    if (dist < top[0] || 
                       (dist == top[0] && price < top[1]) || 
                       (dist == top[0] && price == top[1] && r < top[2]) || 
                       (dist == top[0] && price == top[1] && r == top[2] && c < top[3])) {
                        maxHeap.poll();
                        maxHeap.offer(item);
                    }
                }
            }

            // Explore neighbors
            for (int i = 0; i < 4; i++) {
                int nr = r + dr[i];
                int nc = c + dc[i];

                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, dist + 1});
                }
            }
        }

        // Extract results from heap
        LinkedList<List<Integer>> result = new LinkedList<>();
        while (!maxHeap.isEmpty()) {
            int[] item = maxHeap.poll();
            result.addFirst(Arrays.asList(item[2], item[3]));
        }

        return result;
    }
}
```
### 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.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<vector<int>> highestRankedKItems(vector<vector<int>> &grid,
                                          vector<int> &pricing,
                                          vector<int> &start, int k) {
    int m = grid.size(), n = grid[0].size();
    int row = start[0], col = start[1];
    int low = pricing[0], high = pricing[1];
    vector<tuple<int, int, int, int>> items;
    if (low <= grid[row][col] && grid[row][col] <= high)
      items.emplace_back(0, grid[row][col], row, col);
    queue<tuple<int, int, int>> q;
    q.emplace(row, col, 0);
    grid[row][col] = 0;
    vector<int> dirs = {-1, 0, 1, 0, -1};
    while (!q.empty()) {
      auto [i, j, d] = q.front();
      q.pop();
      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]) {
          if (low <= grid[x][y] && grid[x][y] <= high)
            items.emplace_back(d + 1, grid[x][y], x, y);
          grid[x][y] = 0;
          q.emplace(x, y, d + 1);
        }
      }
    }
    sort(items.begin(), items.end());
    vector<vector<int>> ans;
    for (int i = 0; i < items.size() && i < k; ++i) {
      auto [d, p, x, y] = items[i];
      ans.push_back({x, y});
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    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]

```