2146. K Highest Ranked Items Within a Price Range
Description
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:
0represents a wall that you cannot pass through.1represents 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:
- Distance, defined as the length of the shortest path from the
start(shorter distance has a higher rank). - Price (lower price has a higher rank, but it must be in the price range).
- The row number (smaller row number has a higher rank).
- 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:
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.
Constraints:
m == grid.lengthn == grid[i].length1 <= m, n <= 1051 <= m * n <= 1050 <= grid[i][j] <= 105pricing.length == 22 <= low <= high <= 105start.length == 20 <= row <= m - 10 <= col <= n - 1grid[row][col] > 01 <= k <= m * n
Solutions
Solution 1: BFS + Sorting
We can start from $(\textit{row}, \textit{col})$ and use breadth-first search to find all items with prices in the range $[\textit{low}, \textit{high}]$. Store the distance, price, row coordinate, and column coordinate of these items in the array $\textit{pq}$.
Finally, sort $\textit{pq}$ by distance, price, row coordinate, and column coordinate, and return the coordinates of the first $k$ items.
The time complexity is $O(m \times n \times \log (m \times n))$, and the space complexity is $O(m \times n)$. Here, $m$ and $n$ are the number of rows and columns of the 2D array $\textit{grid}$, respectively.
Python3
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 = start
low, high = pricing
q = deque([(row, col)])
pq = []
if low <= grid[row][col] <= high:
pq.append((0, grid[row][col], row, col))
grid[row][col] = 0
dirs = (-1, 0, 1, 0, -1)
step = 0
while q:
step += 1
for _ in range(len(q)):
x, y = q.popleft()
for a, b in pairwise(dirs):
nx, ny = x + a, y + b
if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] > 0:
if low <= grid[nx][ny] <= high:
pq.append((step, grid[nx][ny], nx, ny))
grid[nx][ny] = 0
q.append((nx, ny))
pq.sort()
return [list(x[2:]) for x in pq[:k]]
Java
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 row = start[0], col = start[1];
int low = pricing[0], high = pricing[1];
Deque<int[]> q = new ArrayDeque<>();
q.offer(new int[] {row, col});
List<int[]> pq = new ArrayList<>();
if (low <= grid[row][col] && grid[row][col] <= high) {
pq.add(new int[] {0, grid[row][col], row, col});
}
grid[row][col] = 0;
final int[] dirs = {-1, 0, 1, 0, -1};
for (int step = 1; !q.isEmpty(); ++step) {
for (int size = q.size(); size > 0; --size) {
int[] curr = q.poll();
int x = curr[0], y = curr[1];
for (int j = 0; j < 4; j++) {
int nx = x + dirs[j];
int ny = y + dirs[j + 1];
if (0 <= nx && nx < m && 0 <= ny && ny < n && grid[nx][ny] > 0) {
if (low <= grid[nx][ny] && grid[nx][ny] <= high) {
pq.add(new int[] {step, grid[nx][ny], nx, ny});
}
grid[nx][ny] = 0;
q.offer(new int[] {nx, ny});
}
}
}
}
pq.sort((a, b) -> {
if (a[0] != b[0]) return Integer.compare(a[0], b[0]);
if (a[1] != b[1]) return Integer.compare(a[1], b[1]);
if (a[2] != b[2]) return Integer.compare(a[2], b[2]);
return Integer.compare(a[3], b[3]);
});
List<List<Integer>> ans = new ArrayList<>();
for (int i = 0; i < Math.min(k, pq.size()); i++) {
ans.add(List.of(pq.get(i)[2], pq.get(i)[3]));
}
return ans;
}
}
C++
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];
queue<pair<int, int>> q;
q.push({row, col});
vector<tuple<int, int, int, int>> pq;
if (low <= grid[row][col] && grid[row][col] <= high) {
pq.push_back({0, grid[row][col], row, col});
}
grid[row][col] = 0;
vector<int> dirs = {-1, 0, 1, 0, -1};
for (int step = 1; q.size(); ++step) {
int sz = q.size();
for (int i = 0; i < sz; ++i) {
auto [x, y] = q.front();
q.pop();
for (int j = 0; j < 4; ++j) {
int nx = x + dirs[j];
int ny = y + dirs[j + 1];
if (0 <= nx && nx < m && 0 <= ny && ny < n && grid[nx][ny] > 0) {
if (low <= grid[nx][ny] && grid[nx][ny] <= high) {
pq.push_back({step, grid[nx][ny], nx, ny});
}
grid[nx][ny] = 0;
q.push({nx, ny});
}
}
}
}
sort(pq.begin(), pq.end());
vector<vector<int>> ans;
for (int i = 0; i < min(k, (int) pq.size()); ++i) {
ans.push_back({get<2>(pq[i]), get<3>(pq[i])});
}
return ans;
}
};
Go
func highestRankedKItems(grid [][]int, pricing []int, start []int, k int) (ans [][]int) {
m, n := len(grid), len(grid[0])
row, col := start[0], start[1]
low, high := pricing[0], pricing[1]
q := [][2]int{{row, col}}
pq := [][]int{}
if low <= grid[row][col] && grid[row][col] <= high {
pq = append(pq, []int{0, grid[row][col], row, col})
}
grid[row][col] = 0
dirs := [5]int{-1, 0, 1, 0, -1}
for step := 1; len(q) > 0; step++ {
for sz := len(q); sz > 0; sz-- {
x, y := q[0][0], q[0][1]
q = q[1:]
for j := 0; j < 4; j++ {
nx, ny := x+dirs[j], y+dirs[j+1]
if nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] > 0 {
if low <= grid[nx][ny] && grid[nx][ny] <= high {
pq = append(pq, []int{step, grid[nx][ny], nx, ny})
}
grid[nx][ny] = 0
q = append(q, [2]int{nx, ny})
}
}
}
}
sort.Slice(pq, func(i, j int) bool {
a, b := pq[i], pq[j]
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]
})
for i := 0; i < len(pq) && i < k; i++ {
ans = append(ans, pq[i][2:])
}
return
}
TypeScript
function highestRankedKItems(
grid: number[][],
pricing: number[],
start: number[],
k: number,
): number[][] {
const [m, n] = [grid.length, grid[0].length];
const [row, col] = start;
const [low, high] = pricing;
let q: [number, number][] = [[row, col]];
const pq: [number, number, number, number][] = [];
if (low <= grid[row][col] && grid[row][col] <= high) {
pq.push([0, grid[row][col], row, col]);
}
grid[row][col] = 0;
const dirs = [-1, 0, 1, 0, -1];
for (let step = 1; q.length > 0; ++step) {
const nq: [number, number][] = [];
for (const [x, y] of q) {
for (let j = 0; j < 4; j++) {
const nx = x + dirs[j];
const ny = y + dirs[j + 1];
if (nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] > 0) {
if (low <= grid[nx][ny] && grid[nx][ny] <= high) {
pq.push([step, grid[nx][ny], nx, ny]);
}
grid[nx][ny] = 0;
nq.push([nx, ny]);
}
}
}
q = nq;
}
pq.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];
});
const ans: number[][] = [];
for (let i = 0; i < Math.min(k, pq.length); i++) {
ans.push([pq[i][2], pq[i][3]]);
}
return ans;
}