LeetCode 2146 - K Highest Ranked Items Within a Price Range

This problem gives us a 2D grid representing a shop layout. Every cell in the grid has one of three meanings: - 0 means the cell is blocked by a wall and cannot be traversed. - 1 means the cell is empty space and can be walked through.

leetcodemediumarraybreadth-first-searchsortingheap-(priority-queue)matrix

LeetCode Problem 2146

Difficulty: 🟡 Medium
Topics: Array, Breadth-First Search, Sorting, Heap (Priority Queue), Matrix

Solution

Problem Understanding

This problem gives us a 2D grid representing a shop layout. Every cell in the grid has one of three meanings:

  • 0 means the cell is blocked by a wall and cannot be traversed.
  • 1 means the cell is empty space and can be walked through.
  • Any value greater than 1 represents an item whose value is also its price.

We are also given:

  • A starting position start = [row, col]
  • A valid price range pricing = [low, high]
  • An integer k

The task is to find the positions of the top k items that satisfy the price range condition and rank them according to several rules.

The ranking priority is:

  1. Shorter distance from the start cell
  2. Lower price
  3. Smaller row index
  4. Smaller column index

The distance is defined as the shortest path length using only up, down, left, and right movements through non-wall cells.

The output must contain the coordinates of the selected items in sorted ranking order.

A very important detail is that we are not simply searching for nearby cells. We must search for reachable item cells whose prices lie inside the range [low, high]. Since movement cost is uniform, shortest path distance naturally suggests Breadth-First Search.

The constraints tell us several important things:

  • m * n <= 10^5, so the total number of cells is at most one hundred thousand.
  • This size is too large for repeatedly running shortest path searches from scratch.
  • Because all edges have equal weight, BFS is the optimal shortest path algorithm here.
  • We must avoid unnecessary sorting of the entire grid when possible.

Several edge cases are important:

  • The start cell itself may contain a valid item.
  • Some items may be unreachable because of walls.
  • There may be fewer than k valid reachable items.
  • Multiple items may have identical distance and price, requiring row and column tie-breaking.
  • The grid may contain large open regions, so efficient visitation tracking is essential.

Approaches

Brute Force Approach

A brute-force solution would attempt to compute the shortest path from the start position to every reachable cell. One way to do this would be:

  1. For every cell in the grid:

  • If the cell contains a valid item in the price range:

  • Run BFS from the start position to compute its shortest distance.

  1. Store all reachable valid items.
  2. Sort them according to the ranking rules.
  3. Return the first k.

This works because BFS correctly computes shortest paths in an unweighted grid.

However, this approach is extremely inefficient. If there are O(m * n) candidate items, and each BFS takes O(m * n), then the total complexity becomes:

$$O((m \cdot n)^2)$$

With up to 10^5 cells, this is far too slow.

Optimal Approach

The key observation is that we do not need to run BFS multiple times.

A single BFS starting from start already computes the shortest distance to every reachable cell. During this traversal:

  • We discover cells in increasing order of distance.
  • We can immediately check whether a cell contains a valid item.
  • We collect all valid items along with their ranking attributes.

After BFS completes, we sort the collected items according to:

  1. Distance
  2. Price
  3. Row
  4. Column

Then we return the first k.

This reduces the expensive repeated shortest path computation into one traversal.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O((m × n)²) O(m × n) Runs BFS separately for many cells
Optimal O(m × n + r log r) O(m × n) Single BFS, then sort reachable valid items

Here, r is the number of reachable items within the price range.

Algorithm Walkthrough

  1. Initialize the BFS traversal from the starting position.

We use a queue because BFS explores cells level by level, which naturally gives shortest path distances in an unweighted grid. 2. Create a visited matrix.

This prevents revisiting the same cell multiple times, which avoids infinite loops and redundant work. 3. Start BFS with distance 0.

Each queue entry stores:

  • Row
  • Column
  • Distance from the start
  1. While the queue is not empty:

Remove the front cell from the queue. 5. Check whether the current cell contains a valid item.

A valid item must:

  • Have value between low and high
  • Be reachable

If valid, store:

  • Distance
  • Price
  • Row
  • Column
  1. Explore all four neighboring directions.

For each neighbor:

  • Ensure it stays inside the grid
  • Ensure it is not a wall (0)
  • Ensure it has not been visited

If valid:

  • Mark visited
  • Push into the queue with distance + 1
  1. After BFS completes, sort the collected items.

Python tuple ordering or Go custom sorting can directly enforce:

  • Distance ascending
  • Price ascending
  • Row ascending
  • Column ascending
  1. Extract the first k coordinates.

If fewer than k items exist, return all of them.

Why it works

BFS guarantees that the first time we reach a cell, we have found its shortest distance from the start. Therefore, every collected item's distance is correct.

After collecting all reachable valid items, sorting by the required ranking criteria exactly matches the problem definition. Since the sort order directly implements the ranking rules, the returned list is guaranteed to be correct.

Python Solution

from collections import deque
from typing import List

class Solution:
    def highestRankedKItems(
        self,
        grid: List[List[int]],
        pricing: List[int],
        start: List[int],
        k: int
    ) -> List[List[int]]:

        rows = len(grid)
        cols = len(grid[0])

        low, high = pricing

        visited = [[False] * cols for _ in range(rows)]

        queue = deque()
        start_row, start_col = start

        queue.append((start_row, start_col, 0))
        visited[start_row][start_col] = True

        items = []

        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

        while queue:
            row, col, dist = queue.popleft()

            price = grid[row][col]

            if low <= price <= high:
                items.append((dist, price, row, col))

            for dr, dc in directions:
                new_row = row + dr
                new_col = col + dc

                if (
                    0 <= new_row < rows
                    and 0 <= new_col < cols
                    and not visited[new_row][new_col]
                    and grid[new_row][new_col] != 0
                ):
                    visited[new_row][new_col] = True
                    queue.append((new_row, new_col, dist + 1))

        items.sort()

        result = []

        for i in range(min(k, len(items))):
            result.append([items[i][2], items[i][3]])

        return result

The implementation begins by initializing BFS structures, including the queue and visited matrix. The queue stores coordinates along with the current shortest distance.

During traversal, every reachable non-wall cell is visited exactly once. Whenever a cell's value falls within the desired pricing range, its ranking information is stored as a tuple.

The tuple ordering is extremely convenient in Python because tuples are compared lexicographically. This means:

(dist, price, row, col)

is automatically sorted according to the exact ranking rules required by the problem.

After sorting, we extract the first k coordinates and return them.

Go Solution

package main

import (
	"sort"
)

func highestRankedKItems(grid [][]int, pricing []int, start []int, k int) [][]int {
	rows := len(grid)
	cols := len(grid[0])

	low := pricing[0]
	high := pricing[1]

	type Node struct {
		row  int
		col  int
		dist int
	}

	queue := []Node{{start[0], start[1], 0}}

	visited := make([][]bool, rows)
	for i := range visited {
		visited[i] = make([]bool, cols)
	}

	visited[start[0]][start[1]] = true

	type Item struct {
		dist  int
		price int
		row   int
		col   int
	}

	items := []Item{}

	directions := [][]int{
		{1, 0},
		{-1, 0},
		{0, 1},
		{0, -1},
	}

	head := 0

	for head < len(queue) {
		current := queue[head]
		head++

		row := current.row
		col := current.col
		dist := current.dist

		price := grid[row][col]

		if low <= price && price <= high {
			items = append(items, Item{
				dist:  dist,
				price: price,
				row:   row,
				col:   col,
			})
		}

		for _, dir := range directions {
			newRow := row + dir[0]
			newCol := col + dir[1]

			if newRow >= 0 &&
				newRow < rows &&
				newCol >= 0 &&
				newCol < cols &&
				!visited[newRow][newCol] &&
				grid[newRow][newCol] != 0 {

				visited[newRow][newCol] = true

				queue = append(queue, Node{
					row:  newRow,
					col:  newCol,
					dist: dist + 1,
				})
			}
		}
	}

	sort.Slice(items, func(i, j int) bool {
		if items[i].dist != items[j].dist {
			return items[i].dist < items[j].dist
		}

		if items[i].price != items[j].price {
			return items[i].price < items[j].price
		}

		if items[i].row != items[j].row {
			return items[i].row < items[j].row
		}

		return items[i].col < items[j].col
	})

	limit := k
	if len(items) < k {
		limit = len(items)
	}

	result := make([][]int, 0, limit)

	for i := 0; i < limit; i++ {
		result = append(result, []int{
			items[i].row,
			items[i].col,
		})
	}

	return result
}

The Go implementation follows the same BFS logic as the Python version.

One notable difference is queue handling. Instead of repeatedly removing the first element of a slice, which is inefficient, we maintain a head index that advances through the slice.

Sorting also requires a custom comparator because Go does not provide automatic tuple comparison like Python.

Worked Examples

Example 1

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

pricing = [2,5]
start = [0,0]
k = 3

BFS Traversal

Step Cell Distance Valid Item? Collected Items
1 (0,0) 0 No []
2 (0,1) 1 Yes, price=2 [(1,2,0,1)]
3 (1,0) 1 No unchanged
4 (1,1) 2 Yes, price=3 [(1,2,0,1),(2,3,1,1)]
5 (2,1) 3 Yes, price=2 add (3,2,2,1)
6 (2,2) 4 Yes, price=5 add (4,5,2,2)

Sorted order remains:

(1,2,0,1)
(2,3,1,1)
(3,2,2,1)
(4,5,2,2)

Take first k=3:

[[0,1],[1,1],[2,1]]

Example 2

start = [2,3]
pricing = [2,3]
k = 2

Reachable valid items:

Position Distance Price
(2,1) 2 2
(1,2) 2 3
(1,1) 3 3
(0,1) 4 2

Sorting first compares distance.

Both (2,1) and (1,2) have distance 2, so price breaks the tie.

Since 2 < 3, (2,1) ranks higher.

Result:

[[2,1],[1,2]]

Example 3

grid =
[
  [1,1,1],
  [0,0,1],
  [2,3,4]
]

The wall row blocks direct downward movement.

BFS path:

(0,0)
-> (0,1)
-> (0,2)
-> (1,2)
-> (2,2)
-> (2,1)
-> (2,0)

Distances:

Position Distance Price
(2,1) 5 3
(2,0) 6 2

Result:

[[2,1],[2,0]]

Complexity Analysis

Measure Complexity Explanation
Time O(m × n + r log r) BFS visits each cell once, sorting reachable items costs O(r log r)
Space O(m × n) Queue and visited matrix may store all cells

The BFS traversal is linear because every cell is visited at most once. The sorting cost depends only on the number of reachable valid items, not the entire grid. Since r ≤ m × n, the worst-case complexity is still efficient enough for the given constraints.

Test Cases

from typing import List

class Solution:
    def highestRankedKItems(
        self,
        grid: List[List[int]],
        pricing: List[int],
        start: List[int],
        k: int
    ) -> List[List[int]]:

        from collections import deque

        rows = len(grid)
        cols = len(grid[0])

        low, high = pricing

        visited = [[False] * cols for _ in range(rows)]

        queue = deque([(start[0], start[1], 0)])
        visited[start[0]][start[1]] = True

        items = []

        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

        while queue:
            row, col, dist = queue.popleft()

            if low <= grid[row][col] <= high:
                items.append((dist, grid[row][col], row, col))

            for dr, dc in directions:
                nr = row + dr
                nc = col + dc

                if (
                    0 <= nr < rows
                    and 0 <= nc < cols
                    and not visited[nr][nc]
                    and grid[nr][nc] != 0
                ):
                    visited[nr][nc] = True
                    queue.append((nr, nc, dist + 1))

        items.sort()

        return [[r, c] for _, _, r, c in items[:k]]

sol = Solution()

# Example 1
assert sol.highestRankedKItems(
    [[1,2,0,1],[1,3,0,1],[0,2,5,1]],
    [2,5],
    [0,0],
    3
) == [[0,1],[1,1],[2,1]]

# Example 2
assert sol.highestRankedKItems(
    [[1,2,0,1],[1,3,3,1],[0,2,5,1]],
    [2,3],
    [2,3],
    2
) == [[2,1],[1,2]]

# Example 3
assert sol.highestRankedKItems(
    [[1,1,1],[0,0,1],[2,3,4]],
    [2,3],
    [0,0],
    3
) == [[2,1],[2,0]]

# Start cell itself is valid
assert sol.highestRankedKItems(
    [[2]],
    [2,3],
    [0,0],
    1
) == [[0,0]]

# No reachable valid items
assert sol.highestRankedKItems(
    [[1,0,2]],
    [2,2],
    [0,0],
    1
) == []

# Tie on distance, compare by price
assert sol.highestRankedKItems(
    [[1,2,3]],
    [2,3],
    [0,0],
    2
) == [[0,1],[0,2]]

# Tie on distance and price, compare by row
assert sol.highestRankedKItems(
    [[1,2],[2,1]],
    [2,2],
    [0,0],
    2
) == [[0,1],[1,0]]

# k larger than number of valid items
assert sol.highestRankedKItems(
    [[1,2]],
    [2,2],
    [0,0],
    10
) == [[0,1]]

# Large open grid behavior
assert sol.highestRankedKItems(
    [
        [1,2,2],
        [1,2,2],
        [1,2,2]
    ],
    [2,2],
    [0,0],
    4
) == [[0,1],[1,1],[0,2],[2,1]]

Test Summary

Test Why
Example 1 Basic BFS traversal
Example 2 Distance and price tie-breaking
Example 3 Indirect path around walls
Single-cell valid start Ensures start item is considered
Unreachable item Verifies walls block traversal
Distance tie Confirms price comparison
Distance and price tie Confirms row ordering
Large k Handles fewer results than requested
Large open grid Stress-tests BFS traversal

Edge Cases

One important edge case occurs when the starting cell itself contains a valid item. A buggy implementation might only check neighboring cells and forget to process the start position. In this solution, the start cell is inserted into the BFS queue immediately and processed exactly like every other cell, so it is correctly included if its price lies within the valid range.

Another important edge case involves unreachable items. Some item cells may technically satisfy the pricing requirement but cannot be reached because walls block all possible paths. Since BFS only traverses non-wall reachable cells, unreachable items are never visited and therefore never added to the result list.

A third subtle edge case involves ranking ties. Multiple items may share the same distance and even the same price. In that situation, row and column ordering become critical. The implementation avoids mistakes by storing ranking information in a sortable tuple or structured comparator that exactly mirrors the required ranking order:

(distance, price, row, column).

A final edge case occurs when k exceeds the number of valid reachable items. Instead of attempting to access nonexistent elements, both implementations safely return all available items using min(k, len(items)) in Python or an adjusted limit in Go.