Skip to main content
Talentd

K Highest Ranked Items Within a Price Range - Solution & Explanation

MediumArrayBreadth-First SearchSortingHeap (Priority Queue)16 min readAsked at: Booking.com
Practice this problem

Problem Statement

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:

  1. Distance, defined as the length of the shortest path from the start (shorter distance has a higher rank).
  2. Price (lower price has a higher rank, but it must be in the price range).
  3. The row number (smaller row number has a higher rank).
  4. 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

Approach Overview

Problem Overview: You start at a position in a grid representing a store. Each cell contains a price or a wall. The task is to find the k highest ranked items whose prices fall within a given range. Ranking follows strict rules: shortest distance from the start first, then lower price, then smaller row index, then smaller column index.

Approach 1: Breadth-First Search (BFS) with Sorting (Time: O(mn log(mn)), Space: O(mn))

The grid behaves like an unweighted graph, so Breadth-First Search naturally finds cells in order of increasing distance from the start. Traverse the grid using BFS while tracking visited cells. Whenever you encounter a cell whose value falls within the price range, store it along with its ranking attributes: distance, price, row, and column. After the traversal finishes, sort the collected candidates using the ranking rules and return the first k positions. Sorting ensures the correct ordering across all valid items.

This approach is straightforward and easy to reason about. BFS guarantees correct distance ordering, while a final sorting step resolves ties using price and coordinates. The downside is that you may collect many candidates and then sort them, which increases the overall cost.

Approach 2: BFS with Priority Queue (Time: O(mn log k), Space: O(mn))

This method still uses BFS to explore the matrix in increasing distance order, but instead of storing every candidate, it maintains a bounded priority queue. During traversal, each valid item is pushed into the heap with its ranking tuple (distance, price, row, col). If the heap grows larger than k, remove the lowest priority element according to the ranking rules. This keeps only the best k candidates while scanning the grid.

Because the heap never stores more than k elements, insertion and removal cost O(log k). The BFS still touches each reachable cell once, but the ranking maintenance becomes more efficient than sorting all candidates at the end.

Recommended for interviews: Start by explaining the BFS traversal since the grid is an unweighted graph and distance is the primary ranking factor. The BFS + sorting approach clearly demonstrates the ranking logic and is easy to implement. The BFS with a priority queue is the more optimized solution and shows stronger algorithmic thinking, especially when the grid contains many candidate items but only a small k is required.

Approach 1: Breadth-First Search (BFS) with Sorting

This approach involves using BFS to navigate through the grid starting from the given 'start' position. During the BFS, calculate the distance of each item from the start and filter based on the price range. Once the valid items are identified, sort them according to the criteria specified (distance, price, row, column) and pick the top k items.

The Python solution uses a deque for the BFS queue to ensure efficient popping from the left. We use a priority queue (min-heap) to keep track of items based on the ranking criteria, storing tuples of the form (distance, price, x-coordinate, y-coordinate). The result list is constructed by popping the top k items from the heap.

Code

PythonJavaScript

Python

JavaScript

Complexity

Time Complexity: O(m * n * log(m * n)), as we potentially explore each cell and sort up to m * n items.
Space Complexity: O(m * n), due to additional space for queues and visited tracking.

Try this approach in the editor →

Approach 2: Breadth-First Search with Priority Queue

This approach combines BFS with a priority queue to dynamically maintain the top k items. As we perform BFS, items are immediately added to the priority queue with the necessary criteria for comparison, maintaining only the top k items efficiently without needing to sort all possible items at the end.

The C++ solution uses a BFS that incorporates a priority queue to maintain the top k items by criteria. The BFS is similar to a standard traversal but continuously updates the priority queue using a custom comparator to ensure the items are ranked according to distance, price, and then position. Once BFS is complete, the selected items are ordered by their criteria and returned.

Code

C++Java

C++

Java

Complexity

Time Complexity: O(m * n * log(k)), where k is much smaller than m*n, optimizing storage in the priority queue.
Space Complexity: O(k + m * n), using additional space for the visit tracking and priority queue.

Try this approach in the editor →

Approach 3: BFS + Sorting

We can start from (row, col) and use breadth-first search to find all items with prices in the range [low, high]. Store the distance, price, row coordinate, and column coordinate of these items in the array pq.

Finally, sort pq by distance, price, row coordinate, and column coordinate, and return the coordinates of the first k items.

The time complexity is O(m times n times log (m times n)), and the space complexity is O(m times n). Here, m and n are the number of rows and columns of the 2D array grid, respectively.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Breadth-First Search (BFS) with Sorting

Time Complexity: O(m * n * log(m * n)), as we potentially explore each cell and sort up to m * n items.
Space Complexity: O(m * n), due to additional space for queues and visited tracking.

Breadth-First Search with Priority Queue

Time Complexity: O(m * n * log(k)), where k is much smaller than m*n, optimizing storage in the priority queue.
Space Complexity: O(k + m * n), using additional space for the visit tracking and priority queue.

BFS + Sorting—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
BFS with SortingO(mn log(mn))O(mn)Simple implementation when the number of valid items is small or clarity is preferred
BFS with Priority QueueO(mn log k)O(mn)Better when the grid is large but only the top k ranked items are required

Video Solution

2146 K Highest Ranked Items Within a Price Range | LeetCode 2146 || BiWeekly- 70 || Graph || BFS || • Bro Coders • 1,430 views views

Watch 5 more video solutions →

Frequently Asked Questions

Is K Highest Ranked Items Within a Price Range easy or hard?
The problem is rated Medium on LeetCode. The BFS traversal is straightforward, but the challenge comes from implementing the multi-level ranking rules correctly and optimizing the selection of the top k items.
How to solve K Highest Ranked Items Within a Price Range in optimal time?
Run BFS from the starting position to explore cells in distance order. For each cell whose price falls within the range, push it into a priority queue ordered by distance, price, row, and column. Keep the heap size at most k. This yields an overall complexity of O(mn log k).
What is the best approach for K Highest Ranked Items Within a Price Range?
Breadth-First Search combined with ranking logic is the most effective approach. BFS guarantees that cells are explored in increasing distance from the start. You then rank valid items by distance, price, row, and column using either sorting or a priority queue. The heap-based approach reduces sorting overhead when k is small.
What data structure is used in K Highest Ranked Items Within a Price Range?
The core data structure is a queue for Breadth-First Search to explore the grid level by level. A sorting structure or a heap (priority queue) is used to rank items by distance, price, and coordinates according to the problem rules.
What is the time complexity of K Highest Ranked Items Within a Price Range?
The BFS traversal itself takes O(mn) because every grid cell may be visited once. If you collect all candidates and sort them, the total complexity becomes O(mn log(mn)). Using a priority queue limited to k elements improves the ranking cost to O(mn log k).
K Highest Ranked Items Within a Price Range Python or Java solution approach
Python solutions typically run BFS with a deque and store candidates for sorting or use heapq for ranking. Java and C++ implementations often use a PriorityQueue with a custom comparator to maintain the best k items while traversing the grid.
Is K Highest Ranked Items Within a Price Range asked at Google, Amazon, or Meta?
Grid traversal and ranking problems like this frequently appear in interviews at companies such as Amazon, Google, and Meta. The problem tests BFS fundamentals, matrix traversal, and custom sorting or heap usage for multi-criteria ranking.

Ready to solve this problem?

Practice K Highest Ranked Items Within a Price Range with our built-in code editor and test cases.

Practice on FleetCode
Previous

As Far from Land as Possible

Next

Kth Largest Element in an Array