Question

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:

• 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 _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.length
• n == grid[i].length
• 1 <= m, n <= 105
• 1 <= m * n <= 105
• 0 <= grid[i][j] <= 105
• pricing.length == 2
• 2 <= low <= high <= 105
• start.length == 2
• 0 <= row <= m - 1
• 0 <= col <= n - 1
• grid[row][col] > 0
• 1 <= k <= m * n

Solutions

Solution 1

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, low, high = start + pricing
    items = []
    if low <= grid[row][col] <= high:
      items.append([0, grid[row][col], row, col])
    q = deque([(row, col, 0)])
    grid[row][col] = 0
    while q:
      i, j, d = q.popleft()
      for a, b in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
        x, y = i + a, j + b
        if 0 <= x < m and 0 <= y < n and grid[x][y]:
          if low <= grid[x][y] <= high:
            items.append([d + 1, grid[x][y], x, y])
          q.append((x, y, d + 1))
          grid[x][y] = 0
    items.sort()
    return [item[2:] for item in items][:k]

class Solution {
  public List<List<Integer>> highestRankedKItems(
    int[][] grid, int[] pricing, int[] start, int k) {
    int m = grid.length, n = grid[0].length;
    int row = start[0], col = start[1];
    int low = pricing[0], high = pricing[1];
    List<int[]> items = new ArrayList<>();
    if (low <= grid[row][col] && grid[row][col] <= high) {
      items.add(new int[] {0, grid[row][col], row, col});
    }
    grid[row][col] = 0;
    Deque<int[]> q = new ArrayDeque<>();
    q.offer(new int[] {row, col, 0});
    int[] dirs = {-1, 0, 1, 0, -1};
    while (!q.isEmpty()) {
      int[] p = q.poll();
      int i = p[0], j = p[1], d = p[2];
      for (int l = 0; l < 4; ++l) {
        int x = i + dirs[l], y = j + dirs[l + 1];
        if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] > 0) {
          if (low <= grid[x][y] && grid[x][y] <= high) {
            items.add(new int[] {d + 1, grid[x][y], x, y});
          }
          grid[x][y] = 0;
          q.offer(new int[] {x, y, d + 1});
        }
      }
    }
    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() && i < k; ++i) {
      int[] p = items.get(i);
      ans.add(Arrays.asList(p[2], p[3]));
    }
    return ans;
  }
}

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];
    vector<tuple<int, int, int, int>> items;
    if (low <= grid[row][col] && grid[row][col] <= high)
      items.emplace_back(0, grid[row][col], row, col);
    queue<tuple<int, int, int>> q;
    q.emplace(row, col, 0);
    grid[row][col] = 0;
    vector<int> dirs = {-1, 0, 1, 0, -1};
    while (!q.empty()) {
      auto [i, j, d] = q.front();
      q.pop();
      for (int l = 0; l < 4; ++l) {
        int x = i + dirs[l], y = j + dirs[l + 1];
        if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y]) {
          if (low <= grid[x][y] && grid[x][y] <= high) items.emplace_back(d + 1, grid[x][y], x, y);
          grid[x][y] = 0;
          q.emplace(x, y, d + 1);
        }
      }
    }
    sort(items.begin(), items.end());
    vector<vector<int>> ans;
    for (int i = 0; i < items.size() && i < k; ++i) {
      auto [d, p, x, y] = items[i];
      ans.push_back({x, y});
    }
    return ans;
  }
};

func highestRankedKItems(grid [][]int, pricing []int, start []int, k int) [][]int {
  m, n := len(grid), len(grid[0])
  row, col := start[0], start[1]
  low, high := pricing[0], pricing[1]
  var items [][]int
  if low <= grid[row][col] && grid[row][col] <= high {
    items = append(items, []int{0, grid[row][col], row, col})
  }
  q := [][]int{{row, col, 0}}
  grid[row][col] = 0
  dirs := []int{-1, 0, 1, 0, -1}
  for len(q) > 0 {
    p := q[0]
    q = q[1:]
    i, j, d := p[0], p[1], p[2]
    for l := 0; l < 4; l++ {
      x, y := i+dirs[l], j+dirs[l+1]
      if x >= 0 && x < m && y >= 0 && y < n && grid[x][y] > 0 {
        if low <= grid[x][y] && grid[x][y] <= high {
          items = append(items, []int{d + 1, grid[x][y], x, y})
        }
        grid[x][y] = 0
        q = append(q, []int{x, y, d + 1})
      }
    }
  }
  sort.Slice(items, func(i, j int) bool {
    a, b := items[i], items[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]
  })
  var ans [][]int
  for i := 0; i < len(items) && i < k; i++ {
    ans = append(ans, items[i][2:])
  }
  return ans
}