LeetCode 2146: K Highest Ranked Items Within a Price Range Solution

Master LeetCode problem 2146 (K Highest Ranked Items Within a Price Range), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

2146. K Highest Ranked Items Within a Price Range

Medium

Array Breadth-First Search Sorting Heap (Priority Queue)Matrix

Problem Explanation

Explanation

To solve this problem, we can use a breadth-first search (BFS) algorithm starting from the given start position. During the BFS traversal, we keep track of the distance, price, row number, and column number for each cell. We can prioritize the cells based on these criteria to find the k highest-ranked items within the price range.

Start the BFS from the given start position.
At each step, explore the neighboring cells and calculate the distance, price, row number, and column number for each neighbor.
Keep a priority queue to store the cells based on the ranking criteria.
Continue the BFS until we have explored all reachable cells within the price range.
Extract the top k cells from the priority queue and return their positions.

Time Complexity: O(m * n * log(k)) where m and n are the dimensions of the grid.

Space Complexity: O(m * n) for storing the visited cells and the priority queue.

Solution Code

import java.util.*;

class Solution {
    public int[][] kHighestItems(int[][] grid, int[] pricing, int[] start, int k) {
        int m = grid.length, n = grid[0].length;
        int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> {
            int distA = a[0], priceA = a[1], rowA = a[2], colA = a[3];
            int distB = b[0], priceB = b[1], rowB = b[2], colB = b[3];
            if (distA != distB) return Integer.compare(distB, distA); // Higher distance has higher rank
            if (priceA != priceB) return Integer.compare(priceA, priceB); // Lower price has higher rank
            if (rowA != rowB) return Integer.compare(rowA, rowB); // Smaller row number has higher rank
            return Integer.compare(colA, colB); // Smaller column number has higher rank
        });
        
        boolean[][] visited = new boolean[m][n];
        visited[start[0]][start[1]] = true;
        pq.offer(new int[]{0, grid[start[0]][start[1]], start[0], start[1]});
        
        List<int[]> result = new ArrayList<>();
        
        while (!pq.isEmpty() && result.size() < k) {
            int[] curr = pq.poll();
            result.add(new int[]{curr[2], curr[3]});
            
            for (int[] dir : directions) {
                int newRow = curr[2] + dir[0];
                int newCol = curr[3] + dir[1];
                if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n && !visited[newRow][newCol]) {
                    visited[newRow][newCol] = true;
                    int dist = curr[0] + 1;
                    int price = grid[newRow][newCol];
                    if (price >= pricing[0] && price <= pricing[1]) {
                        pq.offer(new int[]{dist, price, newRow, newCol});
                    }
                }
            }
        }
        
        return result.toArray(new int[0][]);
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 2146 (K Highest Ranked Items Within a Price Range)?

This page provides optimized solutions for LeetCode problem 2146 (K Highest Ranked Items Within a Price Range) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 2146 (K Highest Ranked Items Within a Price Range)?

The time complexity for LeetCode 2146 (K Highest Ranked Items Within a Price Range) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 2146 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 2146 in Java, C++, or Python.

Back to LeetCode Solutions