{"id":9458,"date":"2022-02-03T17:23:04","date_gmt":"2022-02-04T01:23:04","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=9458"},"modified":"2022-02-03T17:31:18","modified_gmt":"2022-02-04T01:31:18","slug":"leetcode-2146-k-highest-ranked-items-within-a-price-range","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/searching\/leetcode-2146-k-highest-ranked-items-within-a-price-range\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 2146. K Highest Ranked Items Within a Price Range"},"content":{"rendered":"\n<p>You are given a&nbsp;<strong>0-indexed<\/strong>&nbsp;2D integer array&nbsp;<code>grid<\/code>&nbsp;of size&nbsp;<code>m x n<\/code>&nbsp;that represents a map of the items in a shop. The integers in the grid represent the following:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>0<\/code>&nbsp;represents a wall that you cannot pass through.<\/li><li><code>1<\/code>&nbsp;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>\n\n\n\n<p>It takes&nbsp;<code>1<\/code>&nbsp;step to travel between adjacent grid cells.<\/p>\n\n\n\n<p>You are also given integer arrays&nbsp;<code>pricing<\/code>&nbsp;and&nbsp;<code>start<\/code>&nbsp;where&nbsp;<code>pricing = [low, high]<\/code>&nbsp;and&nbsp;<code>start = [row, col]<\/code>&nbsp;indicates that you start at the position&nbsp;<code>(row, col)<\/code>&nbsp;and are interested only in items with a price in the range of&nbsp;<code>[low, high]<\/code>&nbsp;(<strong>inclusive<\/strong>). You are further given an integer&nbsp;<code>k<\/code>.<\/p>\n\n\n\n<p>You are interested in the&nbsp;<strong>positions<\/strong>&nbsp;of the&nbsp;<code>k<\/code>&nbsp;<strong>highest-ranked<\/strong>&nbsp;items whose prices are&nbsp;<strong>within<\/strong>&nbsp;the given price range. The rank is determined by the&nbsp;<strong>first<\/strong>&nbsp;of these criteria that is different:<\/p>\n\n\n\n<ol class=\"wp-block-list\"><li>Distance, defined as the length of the shortest path from the&nbsp;<code>start<\/code>&nbsp;(<strong>shorter<\/strong>&nbsp;distance has a higher rank).<\/li><li>Price (<strong>lower<\/strong>&nbsp;price has a higher rank, but it must be&nbsp;<strong>in the price range<\/strong>).<\/li><li>The row number (<strong>smaller<\/strong>&nbsp;row number has a higher rank).<\/li><li>The column number (<strong>smaller<\/strong>&nbsp;column number has a higher rank).<\/li><\/ol>\n\n\n\n<p>Return&nbsp;<em>the&nbsp;<\/em><code>k<\/code><em>&nbsp;highest-ranked items within the price range&nbsp;<strong>sorted<\/strong>&nbsp;by their rank (highest to lowest)<\/em>. If there are fewer than&nbsp;<code>k<\/code>&nbsp;reachable items within the price range, return&nbsp;<em><strong>all<\/strong>&nbsp;of them<\/em>.<\/p>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/assets.leetcode.com\/uploads\/2021\/12\/16\/example1drawio.png\" alt=\"\"\/><\/figure>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> grid = [[1,2,0,1],[1,3,0,1],[0,2,5,1]], pricing = [2,5], start = [0,0], k = 3\n<strong>Output:<\/strong> [[0,1],[1,1],[2,1]]\n<strong>Explanation:<\/strong> You start at (0,0).\nWith a price range of [2,5], we can take items from (0,1), (1,1), (2,1) and (2,2).\nThe ranks of these items are:\n- (0,1) with distance 1\n- (1,1) with distance 2\n- (2,1) with distance 3\n- (2,2) with distance 4\nThus, the 3 highest ranked items in the price range are (0,1), (1,1), and (2,1).\n<\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/assets.leetcode.com\/uploads\/2021\/12\/16\/example2drawio1.png\" alt=\"\"\/><\/figure>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> grid = [[1,2,0,1],[1,3,3,1],[0,2,5,1]], pricing = [2,3], start = [2,3], k = 2\n<strong>Output:<\/strong> [[2,1],[1,2]]\n<strong>Explanation:<\/strong> You start at (2,3).\nWith a price range of [2,3], we can take items from (0,1), (1,1), (1,2) and (2,1).\nThe ranks of these items are:\n- (2,1) with distance 2, price 2\n- (1,2) with distance 2, price 3\n- (1,1) with distance 3\n- (0,1) with distance 4\nThus, the 2 highest ranked items in the price range are (2,1) and (1,2).\n<\/pre>\n\n\n\n<p><strong>Example 3:<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/assets.leetcode.com\/uploads\/2021\/12\/30\/example3.png\" alt=\"\"\/><\/figure>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> grid = [[1,1,1],[0,0,1],[2,3,4]], pricing = [2,3], start = [0,0], k = 3\n<strong>Output:<\/strong> [[2,1],[2,0]]\n<strong>Explanation:<\/strong> You start at (0,0).\nWith a price range of [2,3], we can take items from (2,0) and (2,1). \nThe ranks of these items are: \n- (2,1) with distance 5\n- (2,0) with distance 6\nThus, the 2 highest ranked items in the price range are (2,1) and (2,0). \nNote that k = 3 but there are only 2 reachable items within the price range.\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>m == grid.length<\/code><\/li><li><code>n == grid[i].length<\/code><\/li><li><code>1 &lt;= m, n &lt;= 10<sup>5<\/sup><\/code><\/li><li><code>1 &lt;= m * n &lt;= 10<sup>5<\/sup><\/code><\/li><li><code>0 &lt;= grid[i][j] &lt;= 10<sup>5<\/sup><\/code><\/li><li><code>pricing.length == 2<\/code><\/li><li><code>2 &lt;= low &lt;= high &lt;= 10<sup>5<\/sup><\/code><\/li><li><code>start.length == 2<\/code><\/li><li><code>0 &lt;= row &lt;= m - 1<\/code><\/li><li><code>0 &lt;= col &lt;= n - 1<\/code><\/li><li><code>grid[row][col] &gt; 0<\/code><\/li><li><code>1 &lt;= k &lt;= m * n<\/code><\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: BFS + Sorting<\/strong><\/h2>\n\n\n\n<p>Use BFS to collect reachable cells and sort afterwards.<\/p>\n\n\n\n<p>Time complexity: O(mn + KlogK) where K = # of reachable cells.<\/p>\n\n\n\n<p>Space complexity: O(mn)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\n\/\/ Author: Huahua\nclass Solution {\npublic:\n  vector<vector<int>> highestRankedKItems(vector<vector<int>>& grid, vector<int>& pricing, vector<int>& start, int k) {\n    const int m = grid.size();\n    const int n = grid[0].size();    \n    const vector<int> dirs{1, 0, -1, 0, 1};    \n    vector<vector<int>> seen(m, vector<int>(n));\n    seen[start[0]][start[1]] = 1;\n    vector<vector<int>> cells;\n    queue<array<int, 3>> q;\n    q.push({start[0], start[1], 0});\n    while (!q.empty()) {\n      auto [y, x, d] = q.front(); q.pop();\n      if (grid[y][x] >= pricing[0] && grid[y][x] <= pricing[1])\n          cells.push_back({d, grid[y][x], y, x});\n      for (int i = 0; i < 4; ++i) {\n        const int tx = x + dirs[i];\n        const int ty = y + dirs[i + 1];\n        if (tx < 0 || tx >= n || ty < 0 || ty >= m \n            || !grid[ty][tx] || seen[ty][tx]++) continue;\n        q.push({ty, tx, d + 1});\n      }\n    }\n    sort(begin(cells), end(cells), less<vector<int>>());\n    vector<vector<int>> ans;\n    for (int i = 0; i < min(k, (int)(cells.size())); ++i)\n      ans.push_back({cells[i][2], cells[i][3]});\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>You are given a&nbsp;0-indexed&nbsp;2D integer array&nbsp;grid&nbsp;of size&nbsp;m x n&nbsp;that represents a map of the items in a shop. The integers in the grid represent the&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[44],"tags":[34,278,177,87,15],"class_list":["post-9458","post","type-post","status-publish","format-standard","hentry","category-searching","tag-bfs","tag-grid","tag-medium","tag-shortest-path","tag-sorting","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9458","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=9458"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9458\/revisions"}],"predecessor-version":[{"id":9460,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9458\/revisions\/9460"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=9458"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=9458"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=9458"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}