#2146

K Highest Ranked Items Within a Price Range

specialist · 950 · lc medium +32 · verified · 46.4% accepted · 532 likes · top 31%

⚑ Multi-Source BFS

Description

You are given a 0-indexed 2D integer array grid of size m x n representing a shop map. Cell values mean:

 - 0 represents a wall you cannot pass through.

 - 1 represents an empty passable cell.

 - Any other positive integer represents an item with that price.

Moving between adjacent cells costs 1 step.

You are also given pricing = [low, high], start = [row, col], and an integer k.

Return the positions of the k highest-ranked items with prices in [low, high], ranked first by:

 - Distance from start (shorter is better).

 - Price (lower is better, within the price range).

 - Row number (smaller is better).

 - Column number (smaller is better).

If fewer than k qualifying items are reachable, 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.

Code

1
2
3