2146. K Highest Ranked Items Within a Price Range LeetCode Solution
In this guide, you will get 2146. K Highest Ranked Items Within a Price Range LeetCode Solution with the best time and space complexity. The solution to K Highest Ranked Items Within a Price Range problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Table of Contents
- Problem Statement
- Complexity Analysis
- K Highest Ranked Items Within a Price Range solution in C++
- K Highest Ranked Items Within a Price Range solution in Java
- K Highest Ranked Items Within a Price Range solution in Python
- Additional Resources
Problem Statement of K Highest Ranked Items Within a Price Range
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 0
1 <= k <= m * n
Complexity Analysis
- Time Complexity: O(\texttt{sort}(mn))
- Space Complexity: O(mn)
2146. K Highest Ranked Items Within a Price Range LeetCode Solution in C++
class Solution {
public:
vector<vector<int>> highestRankedKItems(vector<vector<int>>& grid,
vector<int>& pricing,
vector<int>& start, int k) {
constexpr int dirs[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
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];
vector<vector<int>> ans;
if (low <= grid[row][col] && grid[row][col] <= high) {
ans.push_back({row, col});
if (k == 1)
return ans;
}
queue<pair<int, int>> q{{{row, col}}};
vector<vector<bool>> seen(m, vector<bool>(n));
seen[row][col] = true; // Mark as visited.
while (!q.empty()) {
vector<vector<int>> neighbors;
for (int sz = q.size(); sz > 0; --sz) {
const auto [i, j] = q.front();
q.pop();
for (const auto& [dx, dy] : dirs) {
const int x = i + dx;
const int y = j + dy;
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 vector<int>& a, const vector<int>& 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<int>& neighbor : neighbors) {
if (ans.size() < k)
ans.push_back(neighbor);
if (ans.size() == k)
return ans;
}
}
return ans;
}
};
/* code provided by PROGIEZ */2146. K Highest Ranked Items Within a Price Range LeetCode Solution in Java
class Solution {
public List<List<Integer>> highestRankedKItems(int[][] grid, int[] pricing, int[] start, int k) {
final int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
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];
List<List<Integer>> ans = new ArrayList<>();
if (low <= grid[row][col] && grid[row][col] <= high) {
ans.add(Arrays.asList(row, col));
if (k == 1)
return ans;
}
Queue<Pair<Integer, Integer>> q = new ArrayDeque<>(List.of(new Pair<>(row, col)));
boolean[][] seen = new boolean[m][n];
seen[row][col] = true; // Mark as visited.
while (!q.isEmpty()) {
List<List<Integer>> 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[] dir : dirs) {
final int x = i + dir[0];
final int y = j + dir[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<List<Integer>>() {
@Override
public int compare(List<Integer> a, List<Integer> 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<Integer> neighbor : neighbors) {
if (ans.size() < k)
ans.add(neighbor);
if (ans.size() == k)
return ans;
}
}
return ans;
}
}
// code provided by PROGIEZ2146. K Highest Ranked Items Within a Price Range LeetCode Solution in Python
class Solution:
def highestRankedKItems(
self,
grid: list[list[int]],
pricing: list[int],
start: list[int],
k: int
) -> list[list[int]]:
dirs = ((0, 1), (1, 0), (0, -1), (-1, 0))
m = len(grid)
n = len(grid[0])
low, high = pricing
row, col = start
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][0]
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
# code by PROGIEZAdditional Resources
- Explore all LeetCode problem solutions at Progiez here
- Explore all problems on LeetCode website here
Happy Coding! Keep following PROGIEZ for more updates and solutions.