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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

K Highest Ranked Items Within a Price Range

Number: 2250

Difficulty: Medium

Paid? No

Companies: Booking.com

Problem Description

Given an m x n grid representing a shop, each cell is either a wall (0), an empty cell (1), or an item (a value greater than 1 representing its price). Starting from a given cell, you are to identify items whose price falls within a specified range [low, high]. The goal is to return the positions of the k highest-ranked items reachable, where ranking is determined by:

  1. Shortest distance from the start.
  2. Lower price.
  3. Smaller row index.
  4. Smaller column index. If fewer than k eligible items exist, return all of them.

Key Insights

  • Use a Breadth-First Search (BFS) starting from the given cell to explore the grid and calculate the shortest path distances.
  • Only consider cells that are reachable (i.e., not walls) and have an item price within the given range.
  • Collect eligible items along with their distance, price, row, and column.
  • Sort the collected items based on the required ranking criteria.
  • Return the first k items according to the ranking.

Space and Time Complexity

Time Complexity: O(mn) due to the BFS traversal of the grid and O(E log E) for sorting E eligible items. Space Complexity: O(mn) for the visited array and BFS queue, plus O(E) for storing eligible items.

Solution

We solve the problem by performing a BFS starting from the given starting cell. During the BFS, each reachable cell is examined. If the cell contains an item whose price is between low and high (inclusive), the item along with its computed distance and position is added to a list of candidates. After the BFS completes, the candidates are sorted by distance, price, row, and column. Finally, the positions of the first k sorted candidates are returned. The primary data structures used are a queue for BFS and a list for storing candidate items.

Code Solutions

Below are code samples in Python, JavaScript, C++, and Java with line-by-line comments.

from collections import deque

def highestRankedKItems(grid, pricing, start, k):
    # Get grid dimensions and pricing details
    m, n = len(grid), len(grid[0])
    low, high = pricing
    # Directions for movement: right, left, down, up
    directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
    # Initialize BFS queue with the starting cell and distance 0
    queue = deque([(start[0], start[1], 0)])
    visited = [[False] * n for _ in range(m)]
    visited[start[0]][start[1]] = True
    # List to store candidates as tuples: (distance, price, row, col)
    candidates = []
    
    # Perform BFS traversal
    while queue:
        row, col, dist = queue.popleft()
        # If current cell contains an item within the price range, record it
        if grid[row][col] > 1 and low <= grid[row][col] <= high:
            candidates.append((dist, grid[row][col], row, col))
        # Explore adjacent cells
        for dr, dc in directions:
            newRow, newCol = row + dr, col + dc
            if 0 <= newRow < m and 0 <= newCol < n and not visited[newRow][newCol] and grid[newRow][newCol] != 0:
                visited[newRow][newCol] = True
                queue.append((newRow, newCol, dist + 1))
                
    # Sort candidates by distance, then price, then row, then column
    candidates.sort()
    # Return the positions of the top k candidates
    return [[row, col] for dist, price, row, col in candidates[:k]]

# Example usage:
grid = [[1,2,0,1],[1,3,0,1],[0,2,5,1]]
pricing = [2,5]
start = [0,0]
k = 3
print(highestRankedKItems(grid, pricing, start, k))
← Back to All Questions