How hard is LeetCode 2146. K Highest Ranked Items Within a Price Range?

LeetCode 2146. K Highest Ranked Items Within a Price Range is rated Medium on LeetCode.

What is the time complexity of LeetCode 2146. K Highest Ranked Items Within a Price Range?

The Python solution on this page runs in O(m \times n \times \log (m \times n)).

What is the space complexity of LeetCode 2146. K Highest Ranked Items Within a Price Range?

The Python solution on this page uses O(m \times n) auxiliary space.

What topics does LeetCode 2146. K Highest Ranked Items Within a Price Range cover?

LeetCode 2146. K Highest Ranked Items Within a Price Range is tagged Breadth-First Search, Array, Matrix, Sorting and Heap (Priority Queue) on LeetCode.

K Highest Ranked Items Within a Price Range — LeetCode 2146 Python Solution

MediumBreadth-First SearchArrayMatrixSortingHeap (Priority Queue)

Problem: #2146
Pattern: Heap / Priority Queue
Reading time: 5 min
Source: leetcode.com

The problem

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.

Example

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).

Python solution

Python

class Solution:
    def highestRankedKItems(
        self, grid: List[List[int]], pricing: List[int], start: List[int], k: int
    ) -> List[List[int]]:
        m, n = len(grid), len(grid[0])
        row, col = start
        low, high = pricing
        q = deque([(row, col)])
        pq = []
        if low <= grid[row][col] <= high:
            pq.append((0, grid[row][col], row, col))
        grid[row][col] = 0
        dirs = (-1, 0, 1, 0, -1)
        step = 0
        while q:
            step += 1
            for _ in range(len(q)):
                x, y = q.popleft()
                for a, b in pairwise(dirs):
                    nx, ny = x + a, y + b
                    if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] > 0:
                        if low <= grid[nx][ny] <= high:
                            pq.append((step, grid[nx][ny], nx, ny))
                        grid[nx][ny] = 0
                        q.append((nx, ny))
        pq.sort()
        return [list(x[2:]) for x in pq[:k]]

Complexity

Measure	Complexity
Time	O(m \times n \times \log (m \times n))
Space	O(m \times n) auxiliary

Pattern: Heap / Priority Queue

Keep only the best k elements, or always pull the smallest, in log time. LeetCode 2146. K Highest Ranked Items Within a Price Range is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Heap (Priority Queue).

The heap / priority queue guide has the Python template for the pattern and the 163 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 2146. K Highest Ranked Items Within a Price Range?: LeetCode 2146. K Highest Ranked Items Within a Price Range is rated Medium on LeetCode.
What is the time complexity of LeetCode 2146. K Highest Ranked Items Within a Price Range?: The Python solution on this page runs in O(m \times n \times \log (m \times n)).
What is the space complexity of LeetCode 2146. K Highest Ranked Items Within a Price Range?: The Python solution on this page uses O(m \times n) auxiliary space.
What topics does LeetCode 2146. K Highest Ranked Items Within a Price Range cover?: LeetCode 2146. K Highest Ranked Items Within a Price Range is tagged Breadth-First Search, Array, Matrix, Sorting and Heap (Priority Queue) on LeetCode.