# 2146. K Highest Ranked Items Within a Price Range

• Time: $O(\texttt{sort}(mn))$
• Space: $O(mn)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 class Solution { public: vector> highestRankedKItems(vector>& grid, vector& pricing, vector& start, int k) { const int m = grid.size(); const int n = grid[0].size(); const int low = pricing[0]; const int high = pricing[1]; const int row = start[0]; const int col = start[1]; const vector dirs{0, 1, 0, -1, 0}; vector> ans; if (low <= grid[row][col] && grid[row][col] <= high) { ans.push_back({row, col}); if (k == 1) return ans; } queue> q{{{row, col}}}; vector> seen(m, vector(n)); seen[row][col] = true; // Mark as visited. while (!q.empty()) { vector> neighbors; for (int sz = q.size(); sz > 0; --sz) { const auto [i, j] = q.front(); q.pop(); for (int k = 0; k < 4; ++k) { const int x = i + dirs[k]; const int y = j + dirs[k + 1]; if (x < 0 || x == m || y < 0 || y == n) continue; if (!grid[x][y] || seen[x][y]) continue; if (low <= grid[x][y] && grid[x][y] <= high) neighbors.push_back({x, y}); q.emplace(x, y); seen[x][y] = true; } } ranges::sort(neighbors, [&](const auto& a, const auto& b) { const int x1 = a[0]; const int y1 = a[1]; const int x2 = b[0]; const int y2 = b[1]; if (grid[x1][y1] != grid[x2][y2]) return grid[x1][y1] < grid[x2][y2]; return x1 == x2 ? y1 < y2 : x1 < x2; }); for (const vector& neighbor : neighbors) { if (ans.size() < k) ans.push_back(neighbor); if (ans.size() == k) return ans; } } return ans; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 class Solution { public List> highestRankedKItems(int[][] grid, int[] pricing, int[] start, int k) { final int m = grid.length; final int n = grid[0].length; final int low = pricing[0]; final int high = pricing[1]; final int row = start[0]; final int col = start[1]; final int[] dirs = {0, 1, 0, -1, 0}; List> ans = new ArrayList<>(); if (low <= grid[row][col] && grid[row][col] <= high) { ans.add(Arrays.asList(row, col)); if (k == 1) return ans; } Queue> q = new ArrayDeque<>(Arrays.asList(new Pair<>(row, col))); boolean[][] seen = new boolean[m][n]; seen[row][col] = true; // Mark as visited. while (!q.isEmpty()) { List> neighbors = new ArrayList<>(); for (int sz = q.size(); sz > 0; --sz) { final int i = q.peek().getKey(); final int j = q.poll().getValue(); for (int t = 0; t < 4; ++t) { final int x = i + dirs[t]; final int y = j + dirs[t + 1]; if (x < 0 || x == m || y < 0 || y == n) continue; if (grid[x][y] == 0 || seen[x][y]) continue; if (low <= grid[x][y] && grid[x][y] <= high) neighbors.add(Arrays.asList(x, y)); q.offer(new Pair<>(x, y)); seen[x][y] = true; } } Collections.sort(neighbors, new Comparator>() { @Override public int compare(List a, List b) { final int x1 = a.get(0); final int y1 = a.get(1); final int x2 = b.get(0); final int y2 = b.get(1); if (grid[x1][y1] != grid[x2][y2]) return grid[x1][y1] - grid[x2][y2]; return x1 == x2 ? y1 - y2 : x1 - x2; } }); for (List neighbor : neighbors) { if (ans.size() < k) ans.add(neighbor); if (ans.size() == k) return ans; } } return ans; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 class Solution: def highestRankedKItems(self, grid: List[List[int]], pricing: List[int], start: List[int], k: int) -> List[List[int]]: m = len(grid) n = len(grid[0]) low, high = pricing row, col = start dirs = [0, 1, 0, -1, 0] ans = [] if low <= grid[row][col] <= high: ans.append([row, col]) if k == 1: return ans q = collections.deque([(row, col)]) seen = {(row, col)} # Mark as visited. while q: neighbors = [] for _ in range(len(q)): i, j = q.popleft() for t in range(4): x = i + dirs[t] y = j + dirs[t + 1] if x < 0 or x == m or y < 0 or y == n: continue if not grid[x][y] or (x, y) in seen: continue if low <= grid[x][y] <= high: neighbors.append([x, y]) q.append((x, y)) seen.add((x, y)) neighbors.sort(key=lambda x: (grid[x[0]][x[1]], x[0], x[1])) for neighbor in neighbors: if len(ans) < k: ans.append(neighbor) if len(ans) == k: return ans return ans