K Highest Ranked Items Within a Price Range — Solution
K Highest Ranked Items Within a Price Range solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
K Highest Ranked Items Within a Price Range is a medium coding problem on arrays, sorting and matrix, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Arrays, Sorting, Matrix, Breadth-First Search, Heap
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A shop floor is described by an m x n integer matrix grid:
0is a wall you cannot enter,1is an empty aisle cell,- any value greater than
1is a cell holding an item whose price is that value (you can walk through it).
Moving to one of the four neighbouring cells takes one step. You stand at start = [row, col] and are interested only in items whose price lies in pricing = [low, high] (inclusive) and that you can reach.
Items are ranked by these keys, in order — the earlier key decides:
- shorter walking distance from
startranks higher; - lower price ranks higher;
- smaller row number ranks higher;
- smaller column number ranks higher.
Return the positions [row, col] of the k highest-ranked items, highest first. If fewer than k items qualify, return all of them in rank order.
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: The items at (0,1), (1,1), (2,1) and (2,2) are in range at distances 1, 2, 3 and 4; the first three are returned.
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: (2,1) and (1,2) are both 2 steps away; (2,1) is cheaper (2 < 3), so it ranks first.
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: Only two items are in range, so both are returned: (2,1) at distance 5 before (2,0) at distance 6.
Constraints
m == grid.lengthn == grid[i].length1 <= m, n <= 10^51 <= m * n <= 10^50 <= grid[i][j] <= 10^5pricing.length == 22 <= low <= high <= 10^5start.length == 2grid[start[0]][start[1]] > 01 <= k <= m * n
Hints for K Highest Ranked Items Within a Price Range
Hint 1
The first ranking key is the walking distance, and every step costs 1 — that is a breadth-first search from
start.Hint 2
During the BFS, record every reached cell whose value lies in
[low, high]together with its distance (the start cell itself counts, at distance 0).Hint 3
Sort the recorded items by (distance, price, row, column) and keep the first
k.
How to solve K Highest Ranked Items Within a Price Range
Distances on an unweighted grid come from one BFS. Once every reachable item has its distance, the ranking is a plain lexicographic sort on the four keys.
Approach
- BFS from
startover non-wall cells, writing each cell's distance when it is first reached. - For every reached cell with
low <= grid[r][c] <= high, record(dist, price, r, c). - Sort the records lexicographically.
- Return the
[r, c]of the firstmin(k, count)records.
Why it works
BFS assigns each cell its true shortest walking distance, so the first key is exact; the remaining keys are values read off the cell. Sorting the tuples applies the keys in exactly the order the statement gives.
Complexity
- Time —
O(mn log(mn)) - Space —
O(mn)
Pitfalls
- The starting cell is itself an item if its price is in range — at distance 0 it ranks first.
- Cells with value 1 are walkable but are never items, since
low >= 2. - Return fewer than
kpositions when fewer items qualify; an empty list is a valid answer.
Reference solution
Python
from typing import List
from collections import deque
def highestRankedKItems(grid: List[List[int]], pricing: List[int], start: List[int], k: int) -> List[List[int]]:
m, n = len(grid), len(grid[0])
low, high = pricing
dist = [[-1] * n for _ in range(m)]
sr, sc = start
dist[sr][sc] = 0
q = deque([(sr, sc)])
items = []
while q:
r, c = q.popleft()
v = grid[r][c]
if low <= v <= high:
items.append((dist[r][c], v, r, c))
for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
nr, nc = r + dr, c + dc
if 0 <= nr < m and 0 <= nc < n and grid[nr][nc] != 0 and dist[nr][nc] < 0:
dist[nr][nc] = dist[r][c] + 1
q.append((nr, nc))
items.sort()
return [[r, c] for _, _, r, c in items[:k]]Java
public static int[][] highestRankedKItems(int[][] grid, int[] pricing, int[] start, int k) {
int m = grid.length, n = grid[0].length;
int[][] dist = new int[m][n];
for (int[] row : dist) Arrays.fill(row, -1);
dist[start[0]][start[1]] = 0;
ArrayDeque<int[]> q = new ArrayDeque<>();
q.add(new int[]{start[0], start[1]});
List<int[]> items = new ArrayList<>();
int[] DR = {1, -1, 0, 0}, DC = {0, 0, 1, -1};
while (!q.isEmpty()) {
int[] cur = q.poll();
int r = cur[0], c = cur[1], v = grid[r][c];
if (v >= pricing[0] && v <= pricing[1]) items.add(new int[]{dist[r][c], v, r, c});
for (int d = 0; d < 4; d++) {
int nr = r + DR[d], nc = c + DC[d];
if (nr < 0 || nc < 0 || nr >= m || nc >= n || grid[nr][nc] == 0 || dist[nr][nc] >= 0) continue;
dist[nr][nc] = dist[r][c] + 1;
q.add(new int[]{nr, nc});
}
}
items.sort((a, b) -> a[0] != b[0] ? a[0] - b[0] : a[1] != b[1] ? a[1] - b[1] : a[2] != b[2] ? a[2] - b[2] : a[3] - b[3]);
int take = Math.min(k, items.size());
int[][] res = new int[take][];
for (int t = 0; t < take; t++) res[t] = new int[]{items.get(t)[2], items.get(t)[3]};
return res;
}C++
vector<vector<int>> highestRankedKItems(vector<vector<int>>& grid, vector<int>& pricing, vector<int>& start, int k) {
int m = grid.size(), n = grid[0].size();
vector<vector<int>> dist(m, vector<int>(n, -1));
dist[start[0]][start[1]] = 0;
vector<pair<int, int>> q = {{start[0], start[1]}};
vector<array<int, 4>> items;
int DR[4] = {1, -1, 0, 0}, DC[4] = {0, 0, 1, -1};
for (size_t h = 0; h < q.size(); h++) {
int r = q[h].first, c = q[h].second, v = grid[r][c];
if (v >= pricing[0] && v <= pricing[1]) items.push_back({dist[r][c], v, r, c});
for (int d = 0; d < 4; d++) {
int nr = r + DR[d], nc = c + DC[d];
if (nr < 0 || nc < 0 || nr >= m || nc >= n || grid[nr][nc] == 0 || dist[nr][nc] >= 0) continue;
dist[nr][nc] = dist[r][c] + 1;
q.push_back({nr, nc});
}
}
sort(items.begin(), items.end());
vector<vector<int>> res;
for (size_t t = 0; t < items.size() && (int) t < k; t++) res.push_back({items[t][2], items[t][3]});
return res;
}JavaScript
var highestRankedKItems = function(grid, pricing, start, k) {
var m = grid.length, n = grid[0].length;
var low = pricing[0], high = pricing[1];
var dist = [];
for (var i = 0; i < m; i++) { dist.push([]); for (var j = 0; j < n; j++) dist[i].push(-1); }
dist[start[0]][start[1]] = 0;
var q = [[start[0], start[1]]];
var items = [];
var DR = [1, -1, 0, 0], DC = [0, 0, 1, -1];
for (var h = 0; h < q.length; h++) {
var r = q[h][0], c = q[h][1], v = grid[r][c];
if (v >= low && v <= high) items.push([dist[r][c], v, r, c]);
for (var d = 0; d < 4; d++) {
var nr = r + DR[d], nc = c + DC[d];
if (nr < 0 || nc < 0 || nr >= m || nc >= n || grid[nr][nc] === 0 || dist[nr][nc] >= 0) continue;
dist[nr][nc] = dist[r][c] + 1;
q.push([nr, nc]);
}
}
items.sort(function(a, b) { return a[0] - b[0] || a[1] - b[1] || a[2] - b[2] || a[3] - b[3]; });
var res = [];
for (var t = 0; t < items.length && t < k; t++) res.push([items[t][2], items[t][3]]);
return res;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Sorting Algorithms