Problem Description

You have a 2D grid representing a shop layout where:

• 0 represents walls (impassable)
• 1 represents empty cells (can move through)
• Other positive integers represent item prices at those locations (can move through)

Given:

• A price range [low, high]
• A starting position [row, col]
• A number k

You need to find the k highest-ranked items whose prices fall within the given range [low, high] (inclusive).

Items are ranked by these criteria (in order of priority):

1. Distance: Shortest path from start position (closer items rank higher)
2. Price: Among items at same distance, lower price ranks higher
3. Row number: Among items with same distance and price, smaller row number ranks higher
4. Column number: Among items with same distance, price, and row, smaller column number ranks higher

Movement between adjacent cells (up, down, left, right) takes 1 step.

Return the positions [row, col] of the k highest-ranked items, sorted by rank (highest to lowest). If fewer than k items are reachable within the price range, return all of them.

The solution uses BFS to explore the grid level by level from the starting position, ensuring we find items in order of increasing distance. As we discover items within the price range, we store them with their distance, price, and coordinates. After exploring the entire reachable area, we sort these items according to the ranking criteria and return the top k positions.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: The 2D grid represents a graph where each cell is a node, and adjacent cells (up, down, left, right) are connected by edges. We need to traverse this graph to find reachable items.

Is it a tree?

• No: The grid is not a tree structure. It's a general graph that may contain cycles (you can move in circles through empty cells).

Is the problem related to directed acyclic graphs?

• No: The grid allows bidirectional movement between cells, and cycles are possible.

Is the problem related to shortest paths?

• Yes: The primary ranking criterion is distance, which is defined as the length of the shortest path from the start position. We need to find the shortest distance to each item.

Is the graph Weighted?

• No: Each move between adjacent cells takes exactly 1 step. All edges have the same weight (unweighted graph).

BFS

• Yes: For unweighted graphs where we need shortest paths, BFS is the optimal choice.

Conclusion: The flowchart correctly leads us to use BFS (Breadth-First Search) for this problem. BFS explores the grid level by level, ensuring that when we first reach an item, we've found it via the shortest path. This perfectly aligns with the ranking criteria where distance is the primary factor. The solution then collects all items within the price range along with their distances, sorts them according to the ranking rules, and returns the top k items.

Intuition

The key insight is recognizing that this problem combines two main challenges: finding shortest distances and ranking items by multiple criteria.

Since distance is the primary ranking factor, we need to find the shortest path from the start position to each item. In an unweighted grid (where each move costs 1 step), BFS naturally gives us shortest paths because it explores cells level by level - all cells at distance 1 are found before any cell at distance 2, and so on.

Why not just use BFS and stop after finding k items? The trick is that items at the same distance need to be ranked by additional criteria (price, row, column). If we stopped immediately after finding k items, we might miss items at the same distance that should rank higher based on these secondary criteria.

The solution elegantly handles this by:

1. Running BFS to completion, finding ALL reachable items within the price range
2. Recording each item's distance (which BFS gives us naturally), price, and coordinates
3. Sorting the collected items by all ranking criteria

During BFS, we mark visited cells by setting them to 0, preventing revisits and ensuring we find the shortest path to each cell. As we explore each level, we check if items fall within the price range [low, high] and collect them with their metadata.

The final sort operation handles the complex ranking rules automatically - Python's tuple sorting naturally compares elements in order: first by distance, then price, then row, then column. This gives us the exact ranking specified in the problem.

By collecting all valid items first and then sorting, we ensure we never miss a higher-ranked item that might be at the same distance as a lower-ranked one.

Learn more about Breadth-First Search, Sorting and Heap (Priority Queue) patterns.

Solution Approach

The implementation uses BFS with a queue to explore the grid level by level, combined with sorting to handle the ranking criteria.

Data Structures Used:

• deque for BFS queue to efficiently add/remove elements from both ends
• pq (priority queue/list) to store items with their ranking attributes
• Modified grid to track visited cells

Step-by-step Implementation:

1. Initialization:

   • Extract grid dimensions m, n and starting position row, col
   • Initialize BFS queue with starting position: q = deque([(row, col)])
   • Create empty list pq to store valid items
   • If the starting cell itself contains an item within price range, add it with distance 0: (0, grid[row][col], row, col)
   • Mark starting cell as visited by setting grid[row][col] = 0

2. BFS Traversal:

   • Use step counter to track current distance from start
   • Process cells level by level using for _ in range(len(q)) to ensure all cells at distance step are processed before moving to step + 1
   • For each cell (x, y), explore 4 directions using pairwise(dirs) where dirs = (-1, 0, 1, 0, -1) generates pairs: (-1, 0), (0, 1), (1, 0), (0, -1) representing up, right, down, left

3. Processing Each Cell:

   • Check if next position (nx, ny) is within bounds and not visited (grid[nx][ny] > 0)
   • If cell contains an item within price range [low, high], add tuple (step, grid[nx][ny], nx, ny) to pq
   • Mark cell as visited by setting grid[nx][ny] = 0
   • Add cell to queue for further exploration

4. Sorting and Result:

   • After BFS completes, pq contains all reachable items with their attributes
   • Sort pq using Python's default tuple comparison: first by distance (step), then price, then row, then column
   • Extract coordinates from first k items: [list(x[2:]) for x in pq[:k]]
   • The slice x[2:] extracts (row, col) from each tuple, discarding distance and price

Key Optimizations:

• Modifying the grid in-place to mark visited cells avoids using a separate visited set
• Level-order BFS ensures we find shortest distances without additional distance tracking
• Tuple sorting leverages Python's natural comparison order, eliminating need for custom comparator

The time complexity is O(mn + p log p) where p is the number of items in price range, and space complexity is O(min(mn, p)) for the queue and result list.

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Given:

• Grid:

  [[1, 2, 0, 1],
   [1, 5, 0, 2],
   [3, 0, 0, 3]]

• Start position: [1, 1] (the cell with value 5)
• Price range: [2, 5]
• k = 3

Step 1: Initialization

• Start at position [1, 1] with value 5
• Since 5 is within range [2, 5], add (0, 5, 1, 1) to our list (distance=0, price=5, row=1, col=1)
• Mark this cell as visited by setting it to 0
• Add [1, 1] to BFS queue

Step 2: BFS Level 0 (distance = 1) From [1, 1], explore 4 directions:

• Up [0, 1]: value = 2, within range! Add (1, 2, 0, 1) to list
• Right [1, 2]: value = 0 (wall), skip
• Down [2, 1]: value = 0 (wall), skip
• Left [1, 0]: value = 1, not in range [2, 5], skip but add to queue

Queue now contains: [[0, 1], [1, 0]]

Step 3: BFS Level 1 (distance = 2) From [0, 1]:

• Up: out of bounds
• Right [0, 2]: value = 0 (wall), skip
• Down [1, 1]: already visited (value = 0)
• Left [0, 0]: value = 1, not in range

From [1, 0]:

• Up [0, 0]: value = 1, not in range
• Right [1, 1]: already visited
• Down [2, 0]: value = 3, within range! Add (2, 3, 2, 0) to list
• Left: out of bounds

Queue now contains: [[0, 0], [2, 0]]

Step 4: Continue BFS From [0, 0] (distance = 3):

• Only unvisited neighbor is [0, 3]: value = 1, not in range

From [2, 0] (distance = 3):

• All neighbors are walls or visited

From [0, 3] (distance = 4):

• Only unvisited neighbor is [1, 3]: value = 2, within range! Add (4, 2, 1, 3) to list

Step 5: Sort and Return Collected items:

• (0, 5, 1, 1) - distance=0, price=5, position=[1,1]
• (1, 2, 0, 1) - distance=1, price=2, position=[0,1]
• (2, 3, 2, 0) - distance=2, price=3, position=[2,0]
• (4, 2, 1, 3) - distance=4, price=2, position=[1,3]

After sorting by (distance, price, row, col):

1. (0, 5, 1, 1) - Closest item
2. (1, 2, 0, 1) - Distance 1, price 2
3. (2, 3, 2, 0) - Distance 2, price 3
4. (4, 2, 1, 3) - Distance 4, price 2

Return top k=3 positions: [[1, 1], [0, 1], [2, 0]]

Solution Implementation

Time and Space Complexity

Time Complexity: O(m × n × log(m × n))

The algorithm performs a BFS traversal to explore all reachable cells in the grid. In the worst case, we visit all m × n cells exactly once, which takes O(m × n) time. For each cell that meets the pricing criteria, we add it to the pq list. In the worst case, all m × n cells could be valid items within the price range, so pq could contain up to m × n elements. After the BFS completes, we sort the pq list, which contains at most m × n elements, taking O(m × n × log(m × n)) time. The final list comprehension to extract the top k items takes O(k) time, which is bounded by O(m × n). Therefore, the overall time complexity is dominated by the sorting step: O(m × n × log(m × n)).

Space Complexity: O(m × n)

The space complexity consists of several components: the BFS queue q can hold at most O(m × n) cells in the worst case when all cells are reachable. The priority queue list pq can store at most m × n items if all cells are within the price range. The modification of the grid in-place doesn't require additional space beyond the input. The output list contains at most k items, which is bounded by O(m × n). Therefore, the overall space complexity is O(m × n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Modifying the Original Grid

The solution modifies the input grid in-place by setting visited cells to 0. This destructive approach can cause issues if:

• The grid needs to be reused later
• The function is called multiple times with the same grid
• Test cases verify the grid remains unchanged

Solution: Use a separate visited set instead of modifying the grid:

visited = set()
visited.add((start_row, start_col))

# When checking if a cell is valid:
if (0 <= next_row < rows and 
    0 <= next_col < cols and 
    grid[next_row][next_col] > 0 and
    (next_row, next_col) not in visited):
  
    visited.add((next_row, next_col))
    # ... rest of the logic

2. Incorrect Distance Tracking

A common mistake is incrementing the distance for each cell processed rather than for each level:

# WRONG: Distance increments for each cell
while bfs_queue:
    current_row, current_col = bfs_queue.popleft()
    current_distance += 1  # This is incorrect!

Solution: Process all cells at the same distance level before incrementing:

# CORRECT: Process entire level before incrementing distance
while bfs_queue:
    current_distance += 1
    level_size = len(bfs_queue)
    for _ in range(level_size):
        current_row, current_col = bfs_queue.popleft()
        # Process cell

3. Missing Edge Case: Starting Cell is a Wall

If the starting position itself is a wall (value 0), the code will still try to process it, potentially causing incorrect behavior.

Solution: Add validation at the beginning:

if grid[start_row][start_col] == 0:
    return []  # Cannot start from a wall

4. Confusion Between Item Value 1 and Empty Cell

The problem states that 1 represents empty cells, but the code treats any positive value as passable. This works but can be confusing when 1 could also be an item price.

Solution: Be explicit about the distinction:

cell_value = grid[next_row][next_col]
if cell_value == 0:  # Wall
    continue
elif cell_value == 1:  # Empty cell
    # Mark as visited and add to queue
    pass
else:  # Item with price > 1
    if min_price <= cell_value <= max_price:
        valid_items.append(...)

5. Inefficient Sorting for Large Datasets

When only k items are needed but many items exist, sorting all items is inefficient.

Solution: Use a heap to maintain only the top k items:

import heapq

# During BFS, maintain a max heap of size k
if len(valid_items) < k:
    heapq.heappush(valid_items, (-current_distance, -grid[next_row][next_col], 
                                  -next_row, -next_col))
elif (-current_distance, -grid[next_row][next_col], -next_row, -next_col) > valid_items[0]:
    heapq.heapreplace(valid_items, (-current_distance, -grid[next_row][next_col], 
                                    -next_row, -next_col))