K Highest Ranked Items Within a Price Range

Medium
1700.

K Highest Ranked Items Within a Price Range

K Highest Ranked Items Within a Price Range is a medium coding problem on arrays, sorting and matrix, asked in Amazon and Google interviews.

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

  • 0 is a wall you cannot enter,
  • 1 is an empty aisle cell,
  • any value greater than 1 is 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:

  1. shorter walking distance from start ranks higher;
  2. lower price ranks higher;
  3. smaller row number ranks higher;
  4. 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.length
  • n == grid[i].length
  • 1 <= m, n <= 10^5
  • 1 <= m * n <= 10^5
  • 0 <= grid[i][j] <= 10^5
  • pricing.length == 2
  • 2 <= low <= high <= 10^5
  • start.length == 2
  • grid[start[0]][start[1]] > 0
  • 1 <= k <= m * n
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} grid
 * @param {number[]} pricing
 * @param {number[]} start
 * @param {number} k
 * @return {number[][]}
 */
var highestRankedKItems = function(grid, pricing, start, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

Problem statement

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

  • 0 is a wall you cannot enter,
  • 1 is an empty aisle cell,
  • any value greater than 1 is 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:

  1. shorter walking distance from start ranks higher;
  2. lower price ranks higher;
  3. smaller row number ranks higher;
  4. 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.length
  • n == grid[i].length
  • 1 <= m, n <= 10^5
  • 1 <= m * n <= 10^5
  • 0 <= grid[i][j] <= 10^5
  • pricing.length == 2
  • 2 <= low <= high <= 10^5
  • start.length == 2
  • grid[start[0]][start[1]] > 0
  • 1 <= k <= m * n

Hints for K Highest Ranked Items Within a Price Range

  1. Hint 1

    The first ranking key is the walking distance, and every step costs 1 — that is a breadth-first search from start.

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

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

  1. BFS from start over non-wall cells, writing each cell's distance when it is first reached.
  2. For every reached cell with low <= grid[r][c] <= high, record (dist, price, r, c).
  3. Sort the records lexicographically.
  4. Return the [r, c] of the first min(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 k positions 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