g2101_2200.s2146_k_highest_ranked_items_within_a_price_range.Solution

public class Solution extends Object

2146 - K Highest Ranked Items Within a Price Range.Medium You are given a 0-indexed 2D integer array <code>grid</code> of size <code>m x n</code> that represents a map of the items in a shop. The integers in the grid represent the following: <ul> <li><code>0</code> represents a wall that you cannot pass through.</li> <li><code>1</code> represents an empty cell that you can freely move to and from.</li> <li>All other positive integers represent the price of an item in that cell. You may also freely move to and from these item cells.</li> </ul> It takes <code>1</code> step to travel between adjacent grid cells. You are also given integer arrays <code>pricing</code> and <code>start</code> where <code>pricing = [low, high]</code> and <code>start = [row, col]</code> indicates that you start at the position <code>(row, col)</code> and are interested only in items with a price in the range of <code>[low, high]</code> ( inclusive ). You are further given an integer <code>k</code>. You are interested in the positions of the <code>k</code> highest-ranked items whose prices are within the given price range. The rank is determined by the first of these criteria that is different: <ol> <li>Distance, defined as the length of the shortest path from the <code>start</code> ( shorter distance has a higher rank).</li> <li>Price ( lower price has a higher rank, but it must be in the price range ).</li> <li>The row number ( smaller row number has a higher rank).</li> <li>The column number ( smaller column number has a higher rank).</li> </ol> Return the <code>k</code> highest-ranked items within the price range sorted by their rank (highest to lowest). If there are fewer than <code>k</code> reachable items within the price range, return all of them. Example 1: <img src="https://assets.leetcode.com/uploads/2021/12/16/example1drawio.png" alt="" /> 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: <ul> <li> (0,1) with distance 1 </li> <li> (1,1) with distance 2 </li> <li> (2,1) with distance 3 </li> <li> (2,2) with distance 4 </li> </ul> Thus, the 3 highest ranked items in the price range are (0,1), (1,1), and (2,1). Example 2: <img src="https://assets.leetcode.com/uploads/2021/12/16/example2drawio1.png" alt="" /> 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: <ul> <li> (2,1) with distance 2, price 2 </li> <li> (1,2) with distance 2, price 3 </li> <li> (1,1) with distance 3 </li> <li> (0,1) with distance 4 </li> </ul> Thus, the 2 highest ranked items in the price range are (2,1) and (1,2). Example 3: <img src="https://assets.leetcode.com/uploads/2021/12/30/example3.png" alt="" /> 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: <ul> <li> (2,1) with distance 5 </li> <li> (2,0) with distance 6 </li> </ul> Thus, the 2 highest ranked items in the price range are (2,1) and (2,0). <pre><code> Note that k = 3 but there are only 2 reachable items within the price range. </code></pre> Constraints: <ul> <li><code>m == grid.length</code></li> <li><code>n == grid[i].length</code></li> <li><code>1 <= m, n <= 105</code></li> <li><code>1 <= m * n <= 105</code></li> <li><code>0 <= grid[i][j] <= 105</code></li> <li><code>pricing.length == 2</code></li> <li><code>2 <= low <= high <= 105</code></li> <li><code>start.length == 2</code></li> <li><code>0 <= row <= m - 1</code></li> <li><code>0 <= col <= n - 1</code></li> <li><code>grid[row][col] > 0</code></li> <li><code>1 <= k <= m * n</code></li> </ul>

Constructor Summary

Constructors

Constructor

Description

Solution()
Method Summary

Modifier and Type

Method

Description

List<List<Integer>>

highestRankedKItems(int[][] grid, int[] pricing, int[] start, int k)

Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Details
- Solution
  
  public Solution()
Method Details
- highestRankedKItems
 
 public List<List<Integer>> highestRankedKItems(int[][] grid, int[] pricing, int[] start, int k)

Class Solution

Constructor Summary

Method Summary

Methods inherited from class java.lang.Object

Constructor Details

Solution

Method Details

highestRankedKItems