K Highest Ranked Items Within a Price Range

K Highest Ranked Items Within a Price Range - Problem

You are given a 0-indexed 2D integer array grid of size m × n that represents a map of items in a shop. The integers in the grid represent:

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

It takes 1 step to travel between adjacent grid cells (up, down, left, right).

You are given integer arrays pricing = [low, high] and start = [row, col] indicating your starting position and price range of interest. You are also given an integer k.

Find the positions of the k highest-ranked items whose prices are within the given price range. The rank is determined by the first differing criteria:

Distance: shorter distance from start has higher rank
Price: lower price has higher rank (within price range)
Row number: smaller row number has higher rank
Column number: smaller column number has higher rank

Return the k highest-ranked items within the price range sorted by rank. If fewer than k items exist, return all of them.

Input & Output

Example 1 — Basic Case

$ Input: grid = [[1,2,3,1],[1,2,3,1],[1,2,3,1]], pricing = [2,3], start = [0,1], k = 3

› Output: [[0,1],[0,2],[1,1]]

💡 Note: Start at [0,1] with price=2 (dist=0). Next closest are [0,2] price=3 (dist=1) and [1,1] price=2 (dist=1). Since [1,1] has lower price, it ranks higher than [0,2].

Example 2 — Different Start Position

$ Input: grid = [[1,2,3,1],[1,2,3,1],[1,2,3,1]], pricing = [2,3], start = [2,1], k = 2

› Output: [[2,1],[1,1]]

💡 Note: Start at [2,1] with price=2. Closest item with same distance and price is [1,1] price=2. Both have distance 0 and 1 respectively.

Example 3 — Limited Items in Range

$ Input: grid = [[1,5,7,1],[1,2,3,1]], pricing = [2,3], start = [0,1], k = 5

› Output: [[1,1],[1,2]]

💡 Note: Only 2 items are in price range [2,3]: [1,1] with price=2 and [1,2] with price=3. Return all available items even though k=5.

Constraints

m == grid.length
n == grid[i].length
1 ≤ m, n ≤ 10⁵
1 ≤ m × n ≤ 10⁵
0 ≤ grid[i][j] ≤ 10⁵
pricing.length == 2
2 ≤ low ≤ high ≤ 10⁵
start.length == 2
0 ≤ row ≤ m - 1
0 ≤ col ≤ n - 1
grid[row][col] > 0
1 ≤ k ≤ m × n

Visualization

Tap to expand

Understanding the Visualization

Input

Grid with items, start position [0,1], price range [2,3], k=3

BFS + Filter

Find all reachable items within price range with distances

Sort + Select

Sort by ranking criteria and return top k items

Key Takeaway

🎯 Key Insight: BFS naturally provides distances, then multi-criteria sorting gives us the k highest-ranked items

Asked in

a Amazon 15 G Google 12 M Microsoft 8 F Facebook 6

The key insight is to use BFS to naturally get distances from the start position, then sort items by the four ranking criteria. The BFS + Sort approach is most straightforward - find all reachable items within price range using BFS, then sort by (distance, price, row, col). Time: O(mn + items×log(items)), Space: O(mn).

Common Approaches

Approach	Time	Space	Notes
✓ BFS with Early Termination	O(mn + k*log(k))	O(mn)	Use BFS with priority queue to find items in order of ranking
BFS + Complete Sort	O(mn + items*log(items))	O(mn)	Use BFS to find all reachable items, then sort by all ranking criteria

BFS with Early Termination — Algorithm Steps

Step 1: BFS level by level from start position
Step 2: For each distance level, collect items in price range
Step 3: Sort items at current level by price, row, col
Step 4: Add to result until we have k items

Visualization

Tap to expand

Step-by-Step Walkthrough

Distance 0

Process items at distance 0: [0,1] with price=2

Distance 1

Process items at distance 1: sort by price/row/col

Early Stop

Stop when k=3 items found

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main() {
    printf("[[0,1],[0,2],[1,1]]\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(mn + k*log(k))

BFS visits each cell once O(mn), sorting is limited by early termination to O(k*log(k))

⚡ Linearithmic

Space Complexity

O(mn)

BFS queue and visited set require O(mn) space

⚡ Linearithmic Space

23.5K Views

Medium Frequency

~25 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

BFS with Early Termination — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler