K Highest Ranked Items Within a Price Range
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 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 [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
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 from highest to lowest. If there are fewer than k reachable items within the price range, return all of them.
1 2 0 1 1 3 0 1 0 2 5 1
grid = [[1,2,0,1],[1,3,0,1],[0,2,5,1]], pricing = [2,5], start = [0,0], k = 3[[0,1],[1,1],[2,1]]1 2 0 1 1 3 3 1 0 2 5 1
grid = [[1,2,0,1],[1,3,3,1],[0,2,5,1]], pricing = [2,3], start = [2,3], k = 2[[2,1],[1,2]]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