K Highest Ranked Items Within a Price Range

K Highest Ranked Items Within a Price Range

1. What is this problem about?

The K Highest Ranked Items interview question asks you to find the "best" $k$ items in a grid starting from a specific coordinate. Items are ranked by four criteria in order:

1. Shortest distance from start.
2. Lowest price.
3. Lower row index.
4. Lower column index. Only items within a specific priceRange and reachable (not blocked by walls) are considered.

2. Why is this asked in interviews?

Companies like Booking.com use this to test a candidate's mastery of Breadth-First Search (BFS) and Custom Sorting. It evaluations your ability to handle multi-level tie-breaking and grid traversal. It’s a comprehensive Matrix interview pattern that combines pathfinding with ranking.

3. Algorithmic pattern used

This problem follows the BFS with Priority Queue Ranking pattern.

1. BFS: Start a BFS from the source. This ensures we visit nodes in order of increasing distance.
2. Collect Valid Items: During BFS, if a cell's value is within the priceRange, store it as a candidate along with its distance, price, and coordinates.
3. Sorting: After the BFS (or using a Priority Queue during the BFS), sort the candidate list based on the four-priority rule.
4. Result: Return the top $k$ candidates.

4. Example explanation

Start (0,0), Prices: [[1, 2], [0, 1]], Price Range: [1, 2], $k=2$.

• Dist 0: (0,0), price 1. Candidate!
• Dist 1: (0,1), price 2. Candidate!
• Dist 1: (1,1), price 1. Candidate! Ranking:
• (0,0) wins (dist 0).
• Between (0,1) and (1,1) (dist 1): (1,1) wins on price (1 < 2). Result: [[0,0], [1,1]].

5. Common mistakes candidates make

• DFS for distance: Using Depth-First Search, which doesn't find the shortest distance in unweighted grids.
• Incomplete Sorting: Forgetting one of the tie-breaking rules (like row or column index).
• Redundant Work: Sorting every node visited by BFS instead of only those that fall within the price range.

6. Interview preparation tip

Practice using a Comparator or a lambda function for complex sorting. In many BFS interview patterns, the sorting logic is just as important as the traversal itself.