We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

K Highest Ranked Items Within a Price Range

Difficulty: Medium

Problem Description

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, 1 represents an empty cell that you can freely move to and from, and all other positive integers represent the price of an item in that cell. You may also freely move to and from these item cells.

It takes 1 step to travel between adjacent grid cells. You are also given integer arrays pricing and start where pricing = [low, high] and start = [row, col] indicates that you start at the position (row, col) and are interested only in items with a price in the range of [low, high] (inclusive). You are further given an integer k. You are interested in the positions of the k highest-ranked items whose prices are within the given price range. The rank is determined by the first of these criteria that is different: Distance, Price, Row number, Column number. Return the k highest-ranked items within the price range sorted by their rank (highest to lowest). If there are fewer than k reachable items within the price range, return all of them.

Key Insights

  • Use Breadth-First Search (BFS) to explore all reachable cells from the starting position.
  • Collect items that fall within the specified price range during the BFS traversal.
  • Use a priority queue (or max heap) to efficiently sort and retrieve the top k items based on distance, price, and position.
  • The BFS ensures that we explore the grid in layers, maintaining the shortest distance to each cell.

Space and Time Complexity

Time Complexity: O(m * n log k) - for BFS to traverse the grid and insertion into a heap of size k. Space Complexity: O(m * n) - for the visited grid and the queue storage in BFS.

Solution

We will use a Breadth-First Search (BFS) starting from the start position to explore the grid. During the traversal, we will collect the items that fall within the specified price range. As we collect these items, we will maintain their distances from the start position and push them into a max-heap (or priority queue) based on the specified ranking criteria. Finally, we will extract and return the top k items.

Code Solutions

from collections import deque
import heapq

def k_highest_ranked_items(grid, pricing, start, k):
    m, n = len(grid), len(grid[0])
    low, high = pricing
    directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    queue = deque([start])
    visited = set()
    visited.add(tuple(start))
    items = []

    # BFS to find all reachable items within the price range
    while queue:
        x, y = queue.popleft()
        
        # Check the price of the current cell
        price = grid[x][y]
        if low <= price <= high:
            distance = abs(start[0] - x) + abs(start[1] - y)
            items.append((distance, price, x, y))
        
        # Explore neighbors
        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            if 0 <= nx < m and 0 <= ny < n and (nx, ny) not in visited and grid[nx][ny] != 0:
                visited.add((nx, ny))
                queue.append((nx, ny))

    # Use a max heap to sort the items based on the criteria
    items.sort(key=lambda item: (item[0], item[1], item[2], item[3]))
    
    return [[x[2], x[3]] for x in items[:k]]
← Back to All Questions