TheRealSamuel/LeetCodeProblem
0572
1{2 "id": 2250,3 "name": "k_highest_ranked_items_within_a_price_range",4 "difficulty": "Medium",5 "link": "https://leetcode.com/problems/k-highest-ranked-items-within-a-price-range/",6 "date": "1641600000000",7 "task_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: 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.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`",8 "public_test_cases": [9 {10 "label": "Example 1",11 "input": "grid = [[1,2,0,1],[1,3,0,1],[0,2,5,1]], pricing = [2,5], start = [0,0], k = 3",12 "output": "[[0,1],[1,1],[2,1]] "13 },14 {15 "label": "Example 2",16 "input": "grid = [[1,2,0,1],[1,3,3,1],[0,2,5,1]], pricing = [2,3], start = [2,3], k = 2",17 "output": "[[2,1],[1,2]] "18 },19 {20 "label": "Example 3",21 "input": "grid = [[1,1,1],[0,0,1],[2,3,4]], pricing = [2,3], start = [0,0], k = 3",22 "output": "[[2,1],[2,0]] "23 }24 ],25 "private_test_cases": [26 {27 "input": [28 [29 [30 0,31 33,32 66,33 86,34 0,35 0,36 1737 ],38 [39 7,40 0,41 1,42 17,43 24,44 0,45 3946 ],47 [48 0,49 15,50 83,51 8,52 53,53 0,54 5755 ]56 ],57 [58 31,59 7460 ],61 [62 0,63 364 ],65 1266 ],67 "output": [68 [69 0,70 271 ],72 [73 0,74 175 ],76 [77 2,78 479 ]80 ]81 },82 {83 "input": [84 [85 [86 3,87 0,88 0,89 26,90 34,91 0,92 81,93 3994 ],95 [96 97,97 68,98 0,99 11,100 65,101 10,102 9,103 79104 ],105 [106 13,107 98,108 32,109 18,110 72,111 0,112 79,113 75114 ],115 [116 0,117 24,118 70,119 65,120 58,121 39,122 78,123 74124 ],125 [126 74,127 35,128 75,129 48,130 0,131 0,132 91,133 76134 ],135 [136 77,137 98,138 91,139 5,140 18,141 72,142 0,143 24144 ]145 ],146 [147 41,148 74149 ],150 [151 3,152 4153 ],154 19155 ],156 "output": [157 [158 3,159 4160 ],161 [162 3,163 3164 ],165 [166 2,167 4168 ],169 [170 4,171 3172 ],173 [174 1,175 4176 ],177 [178 3,179 2180 ],181 [182 3,183 7184 ],185 [186 1,187 1188 ],189 [190 5,191 5192 ],193 [194 4,195 0196 ]197 ]198 },199 {200 "input": [201 [202 [203 0,204 27,205 0,206 47,207 79,208 89,209 92,210 78,211 93,212 99213 ],214 [215 13,216 50,217 41,218 0,219 0,220 95,221 0,222 100,223 44,224 97225 ],226 [227 28,228 0,229 67,230 40,231 0,232 0,233 73,234 0,235 20,236 41237 ],238 [239 68,240 66,241 0,242 95,243 59,244 59,245 0,246 23,247 62,248 0249 ],250 [251 18,252 72,253 0,254 0,255 0,256 0,257 8,258 16,259 24,260 88261 ]262 ],263 [264 11,265 44266 ],267 [268 3,269 9270 ],271 4272 ],273 "output": [274 [275 2,276 9277 ],278 [279 2,280 8281 ],282 [283 3,284 7285 ],286 [287 4,288 8289 ]290 ]291 },292 {293 "input": [294 [295 [296 89,297 5,298 22,299 0,300 45,301 98,302 22303 ],304 [305 13,306 56,307 0,308 95,309 94,310 12,311 95312 ],313 [314 59,315 0,316 0,317 0,318 40,319 90,320 99321 ],322 [323 32,324 86,325 12,326 3,327 0,328 95,329 89330 ],331 [332 74,333 47,334 54,335 29,336 0,337 2,338 0339 ],340 [341 55,342 19,343 77,344 0,345 7,346 69,347 30348 ],349 [350 61,351 22,352 0,353 0,354 62,355 37,356 88357 ],358 [359 0,360 0,361 75,362 0,363 40,364 97,365 0366 ],367 [368 0,369 61,370 45,371 0,372 34,373 0,374 0375 ]376 ],377 [378 34,379 91380 ],381 [382 2,383 2384 ],385 35386 ],387 "output": [388 [389 4,390 2391 ],392 [393 3,394 1395 ],396 [397 4,398 1399 ],400 [401 5,402 2403 ],404 [405 2,406 0407 ],408 [409 4,410 0411 ],412 [413 5,414 0415 ],416 [417 1,418 1419 ],420 [421 6,422 0423 ],424 [425 0,426 0427 ]428 ]429 },430 {431 "input": [432 [433 [434 37,435 44436 ],437 [438 77,439 0440 ],441 [442 0,443 43444 ],445 [446 21,447 79448 ],449 [450 42,451 30452 ],453 [454 0,455 90456 ],457 [458 22,459 71460 ]461 ],462 [463 8,464 44465 ],466 [467 0,468 0469 ],470 3471 ],472 "output": [473 [474 0,475 0476 ],477 [478 0,479 1480 ]481 ]482 },483 {484 "input": [485 [486 [487 0,488 58,489 98,490 2,491 0,492 42,493 0,494 9495 ],496 [497 45,498 49,499 10,500 0,501 53,502 13,503 0,504 40505 ],506 [507 0,508 26,509 81,510 52,511 0,512 79,513 21,514 73515 ],516 [517 14,518 29,519 98,520 0,521 66,522 17,523 28,524 16525 ]526 ],527 [528 19,529 93530 ],531 [532 1,533 3534 ],535 7536 ],537 "output": [538 [539 2,540 3541 ],542 [543 1,544 4545 ],546 [547 1,548 1549 ],550 [551 2,552 2553 ],554 [555 2,556 1557 ],558 [559 0,560 5561 ],562 [563 1,564 0565 ]566 ]567 },568 {569 "input": [570 [571 [572 62,573 34,574 23,575 88,576 0,577 90,578 0,579 5,580 19,581 0582 ],583 [584 0,585 0,586 0,587 33,588 4,589 0,590 69,591 48,592 80,593 0594 ],595 [596 96,597 0,598 93,599 0,600 0,601 0,602 66,603 0,604 60,605 24606 ],607 [608 58,609 87,610 31,611 9,612 43,613 20,614 5,615 82,616 23,617 0618 ],619 [620 4,621 45,622 15,623 8,624 44,625 76,626 47,627 62,628 0,629 2630 ],631 [632 58,633 33,634 66,635 73,636 0,637 77,638 80,639 39,640 0,641 12642 ]643 ],644 [645 9,646 64647 ],648 [649 2,650 4651 ],652 45653 ],654 "output": [655 [656 3,657 4658 ],659 [660 3,661 3662 ],663 [664 3,665 5666 ],667 [668 1,669 3670 ],671 [672 4,673 4674 ],675 [676 3,677 2678 ],679 [680 4,681 2682 ],683 [684 0,685 2686 ],687 [688 4,689 6690 ],691 [692 3,693 8694 ],695 [696 0,697 1698 ],699 [700 4,701 1702 ],703 [704 3,705 0706 ],707 [708 4,709 7710 ],711 [712 5,713 1714 ],715 [716 5,717 7718 ],719 [720 1,721 7722 ],723 [724 2,725 8726 ],727 [728 0,729 0730 ],731 [732 2,733 9734 ],735 [736 5,737 0738 ],739 [740 0,741 8742 ]743 ]744 },745 {746 "input": [747 [748 [749 0,750 0,751 11,752 0,753 0,754 23,755 0,756 0,757 44,758 18759 ]760 ],761 [762 48,763 92764 ],765 [766 0,767 5768 ],769 4770 ],771 "output": []772 },773 {774 "input": [775 [776 [777 0,778 32,779 44,780 51,781 2,782 98783 ]784 ],785 [786 43,787 52788 ],789 [790 0,791 5792 ],793 2794 ],795 "output": [796 [797 0,798 3799 ],800 [801 0,802 2803 ]804 ]805 },806 {807 "input": [808 [809 [810 0,811 0,812 48,813 33,814 7,815 3816 ],817 [818 99,819 0,820 0,821 71,822 1,823 0824 ],825 [826 0,827 0,828 10,829 0,830 0,831 87832 ],833 [834 89,835 69,836 66,837 20,838 72,839 35840 ],841 [842 15,843 0,844 100,845 0,846 88,847 31848 ],849 [850 38,851 0,852 68,853 73,854 14,855 32856 ],857 [858 99,859 27,860 86,861 71,862 98,863 86864 ],865 [866 49,867 60,868 21,869 81,870 3,871 95872 ],873 [874 62,875 0,876 0,877 0,878 97,879 65880 ],881 [882 89,883 69,884 33,885 6,886 92,887 80888 ]889 ],890 [891 5,892 12893 ],894 [895 7,896 3897 ],898 57899 ],900 "output": [901 [902 9,903 3904 ],905 [906 2,907 2908 ]909 ]910 }911 ],912 "haskell_template": "highestRankedKItems :: [[Int]] -> [Int] -> [Int] -> Int -> [[Int]]\nhighestRankedKItems grid pricing start k ",913 "ocaml_template": "let highestRankedKItems (grid: int list list) (pricing: int list) (start: int list) (k: int) : int list list = ",914 "scala_template": "def highestRankedKItems(grid: List[List[Int]],pricing: List[Int],start: List[Int],k: Int): List[List[Int]] = { \n \n}",915 "java_template": "public static List<List<Integer>> highestRankedKItems(List<List<Integer>> grid, List<Integer> pricing, List<Integer> start, int k) {\n\n}",916 "python_template": "class Solution(object):\n def highestRankedKItems(self, grid, pricing, start, k):\n \"\"\"\n :type grid: List[List[int]]\n :type pricing: List[int]\n :type start: List[int]\n :type k: int\n :rtype: List[List[int]]\n \"\"\"\n "917}