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 thek highest-ranked items within the price rangesorted by their rank (highest to lowest). If there are fewer than k reachable items within the price range, return all of them.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


![](https://assets.leetcode.com/uploads/2021/12/16/example1drawio.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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


![](https://assets.leetcode.com/uploads/2021/12/16/example2drawio1.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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


![](https://assets.leetcode.com/uploads/2021/12/30/example3.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 <= 10^5
  • 1 <= m * n <= 10^5
  • 0 <= grid[i][j] <= 10^5
  • pricing.length == 2
  • 2 <= low <= high <= 10^5
  • start.length == 2
  • 0 <= row <= m - 1
  • 0 <= col <= n - 1
  • grid[row][col] > 0
  • 1 <= k <= m * n

Solution

Method 1 – Breadth-First Search with Sorting

Intuition

We want to find the k highest-ranked items within a price range, where rank is determined by shortest distance from the start, then by lowest price, then by row, then by column. BFS is ideal for finding shortest paths in a grid, and we can collect all valid items and sort them by the required criteria.

Approach

  1. Use BFS from the start cell to explore all reachable cells, tracking distance.
  2. For each cell, if its value is within the price range, record its (distance, price, row, col).
  3. After BFS, sort the collected items by (distance, price, row, col).
  4. Return the first k items’ positions.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

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();
        vector<vector<bool>> vis(m, vector<bool>(n, false));
        queue<pair<int, int>> q;
        vector<tuple<int, int, int, int>> items;
        int dirs[4][2] = {{0,1},{1,0},{0,-1},{-1,0}};
        q.push({start[0], start[1]});
        vis[start[0]][start[1]] = true;
        int dist = 0;
        while (!q.empty()) {
            int sz = q.size();
            for (int i = 0; i < sz; ++i) {
                auto [r, c] = q.front(); q.pop();
                int val = grid[r][c];
                if (val >= pricing[0] && val <= pricing[1])
                    items.emplace_back(dist, val, r, c);
                for (auto& d : dirs) {
                    int nr = r + d[0], nc = c + d[1];
                    if (nr >= 0 && nr < m && nc >= 0 && nc < n && !vis[nr][nc] && grid[nr][nc] != 0) {
                        vis[nr][nc] = true;
                        q.push({nr, nc});
                    }
                }
            }
            ++dist;
        }
        sort(items.begin(), items.end());
        vector<vector<int>> ans;
        for (int i = 0; i < items.size() && ans.size() < k; ++i) {
            auto [d, v, r, c] = items[i];
            ans.push_back({r, c});
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

type tuple struct{d, v, r, c int}
func highestRankedKItems(grid [][]int, pricing []int, start []int, k int) [][]int {
    m, n := len(grid), len(grid[0])
    vis := make([][]bool, m)
    for i := range vis { vis[i] = make([]bool, n) }
    dirs := [][2]int{{0,1},{1,0},{0,-1},{-1,0}}
    q := [][2]int{{start[0], start[1]}}
    vis[start[0]][start[1]] = true
    items := []tuple{}
    dist := 0
    for len(q) > 0 {
        sz := len(q)
        for i := 0; i < sz; i++ {
            r, c := q[0][0], q[0][1]
            q = q[1:]
            v := grid[r][c]
            if v >= pricing[0] && v <= pricing[1] {
                items = append(items, tuple{dist, v, r, c})
            }
            for _, d := range dirs {
                nr, nc := r+d[0], c+d[1]
                if nr>=0 && nr<m && nc>=0 && nc<n && !vis[nr][nc] && grid[nr][nc]!=0 {
                    vis[nr][nc] = true
                    q = append(q, [2]int{nr, nc})
                }
            }
        }
        dist++
    }
    sort.Slice(items, func(i, j int) bool {
        a, b := items[i], items[j]
        if a.d != b.d { return a.d < b.d }
        if a.v != b.v { return a.v < b.v }
        if a.r != b.r { return a.r < b.r }
        return a.c < b.c
    })
    ans := [][]int{}
    for i := 0; i < len(items) && len(ans) < k; i++ {
        ans = append(ans, []int{items[i].r, items[i].c})
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

class Solution {
    public List<List<Integer>> highestRankedKItems(int[][] grid, int[] pricing, int[] start, int k) {
        int m = grid.length, n = grid[0].length;
        boolean[][] vis = new boolean[m][n];
        Queue<int[]> q = new LinkedList<>();
        List<int[]> items = new ArrayList<>();
        int[][] dirs = {{0,1},{1,0},{0,-1},{-1,0}};
        q.offer(new int[]{start[0], start[1]});
        vis[start[0]][start[1]] = true;
        int dist = 0;
        while (!q.isEmpty()) {
            int sz = q.size();
            for (int i = 0; i < sz; ++i) {
                int[] cur = q.poll();
                int r = cur[0], c = cur[1];
                int v = grid[r][c];
                if (v >= pricing[0] && v <= pricing[1])
                    items.add(new int[]{dist, v, r, c});
                for (int[] d : dirs) {
                    int nr = r + d[0], nc = c + d[1];
                    if (nr >= 0 && nr < m && nc >= 0 && nc < n && !vis[nr][nc] && grid[nr][nc] != 0) {
                        vis[nr][nc] = true;
                        q.offer(new int[]{nr, nc});
                    }
                }
            }
            ++dist;
        }
        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() && ans.size() < k; ++i) {
            ans.add(Arrays.asList(items.get(i)[2], items.get(i)[3]));
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

class Solution {
    fun highestRankedKItems(grid: Array<IntArray>, pricing: IntArray, start: IntArray, k: Int): List<List<Int>> {
        val m = grid.size
        val n = grid[0].size
        val vis = Array(m) { BooleanArray(n) }
        val dirs = arrayOf(intArrayOf(0,1), intArrayOf(1,0), intArrayOf(0,-1), intArrayOf(-1,0))
        val q = ArrayDeque<Pair<Int, Int>>()
        val items = mutableListOf<Quadruple>()
        q.add(Pair(start[0], start[1]))
        vis[start[0]][start[1]] = true
        var dist = 0
        data class Quadruple(val d: Int, val v: Int, val r: Int, val c: Int)
        while (q.isNotEmpty()) {
            repeat(q.size) {
                val (r, c) = q.removeFirst()
                val v = grid[r][c]
                if (v in pricing[0]..pricing[1]) items.add(Quadruple(dist, v, r, c))
                for (d in dirs) {
                    val nr = r + d[0]
                    val nc = c + d[1]
                    if (nr in 0 until m && nc in 0 until n && !vis[nr][nc] && grid[nr][nc] != 0) {
                        vis[nr][nc] = true
                        q.add(Pair(nr, nc))
                    }
                }
            }
            dist++
        }
        items.sortWith(compareBy({it.d}, {it.v}, {it.r}, {it.c}))
        return items.take(k).map { listOf(it.r, it.c) }
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

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])
        vis = [[False]*n for _ in range(m)]
        q = [(start[0], start[1])]
        vis[start[0]][start[1]] = True
        items: list[tuple[int,int,int,int]] = []
        dist = 0
        dirs = [(0,1),(1,0),(0,-1),(-1,0)]
        while q:
            nq = []
            for r, c in q:
                v = grid[r][c]
                if pricing[0] <= v <= pricing[1]:
                    items.append((dist, v, r, c))
                for dr, dc in dirs:
                    nr, nc = r+dr, c+dc
                    if 0<=nr<m and 0<=nc<n and not vis[nr][nc] and grid[nr][nc]!=0:
                        vis[nr][nc] = True
                        nq.append((nr, nc))
            q = nq
            dist += 1
        items.sort()
        ans = []
        for d, v, r, c in items:
            if len(ans) == k: break
            ans.append([r, c])
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

impl Solution {
    pub fn highest_ranked_k_items(grid: Vec<Vec<i32>>, pricing: Vec<i32>, start: Vec<i32>, k: i32) -> Vec<Vec<i32>> {
        use std::collections::{VecDeque, HashSet};
        let m = grid.len();
        let n = grid[0].len();
        let mut vis = vec![vec![false; n]; m];
        let mut q = VecDeque::new();
        let mut items = vec![];
        let dirs = [(0,1),(1,0),(0,-1),(-1,0)];
        q.push_back((start[0] as usize, start[1] as usize));
        vis[start[0] as usize][start[1] as usize] = true;
        let mut dist = 0;
        while !q.is_empty() {
            for _ in 0..q.len() {
                let (r, c) = q.pop_front().unwrap();
                let v = grid[r][c];
                if v >= pricing[0] && v <= pricing[1] {
                    items.push((dist, v, r, c));
                }
                for (dr, dc) in dirs.iter() {
                    let nr = r as i32 + dr;
                    let nc = c as i32 + dc;
                    if nr>=0 && nr<m as i32 && nc>=0 && nc<n as i32 {
                        let (nr, nc) = (nr as usize, nc as usize);
                        if !vis[nr][nc] && grid[nr][nc]!=0 {
                            vis[nr][nc] = true;
                            q.push_back((nr, nc));
                        }
                    }
                }
            }
            dist += 1;
        }
        items.sort();
        let mut ans = vec![];
        for (d, v, r, c) in items {
            if ans.len() == k as usize { break; }
            ans.push(vec![r as i32, c as i32]);
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

class Solution {
    highestRankedKItems(grid: number[][], pricing: number[], start: number[], k: number): number[][] {
        const m = grid.length, n = grid[0].length;
        const vis = Array.from({length: m}, () => Array(n).fill(false));
        const q: [number, number][] = [[start[0], start[1]]];
        vis[start[0]][start[1]] = true;
        let dist = 0;
        const items: [number, number, number, number][] = [];
        const dirs = [[0,1],[1,0],[0,-1],[-1,0]];
        while (q.length) {
            const nq: [number, number][] = [];
            for (const [r, c] of q) {
                const v = grid[r][c];
                if (v >= pricing[0] && v <= pricing[1]) items.push([dist, v, r, c]);
                for (const [dr, dc] of dirs) {
                    const nr = r+dr, nc = c+dc;
                    if (nr>=0 && nr<m && nc>=0 && nc<n && !vis[nr][nc] && grid[nr][nc]!=0) {
                        vis[nr][nc] = true;
                        nq.push([nr, nc]);
                    }
                }
            }
            q.splice(0, q.length, ...nq);
            dist++;
        }
        items.sort((a, b) => {
            for (let i = 0; i < 4; ++i) if (a[i] !== b[i]) return a[i] - b[i];
            return 0;
        });
        const ans: number[][] = [];
        for (const [d, v, r, c] of items) {
            if (ans.length === k) break;
            ans.push([r, c]);
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(m*n*log(m*n)), where m and n are grid dimensions. BFS visits each cell once, and sorting all found items takes O(N log N) where N is the number of items.
  • 🧺 Space complexity: O(m*n), for visited array, queue, and storing all valid items.