Introduction

In this blog post, we will explore how to solve the LeetCode problem "2146" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

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. 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, defined as the length of the shortest path from the start (shorter distance has a higher rank). Price (lower price has a higher rank, but it must be in the price range). The row number (smaller row number has a higher rank). The column number (smaller column number has a higher rank). 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. Example 1: 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). With a price range of [2,5], we can take items from (0,1), (1,1), (2,1) and (2,2). The ranks of these items are: - (0,1) with distance 1 - (1,1) with distance 2 - (2,1) with distance 3 - (2,2) with distance 4 Thus, the 3 highest ranked items in the price range are (0,1), (1,1), and (2,1). Example 2: Input: grid = [[1,2,0,1],[1,3,3,1],[0,2,5,1]], pricing = [2,3], start = [2,3], k = 2 Output: [[2,1],[1,2]] Explanation: You start at (2,3). With a price range of [2,3], we can take items from (0,1), (1,1), (1,2) and (2,1). The ranks of these items are: - (2,1) with distance 2, price 2 - (1,2) with distance 2, price 3 - (1,1) with distance 3 - (0,1) with distance 4 Thus, the 2 highest ranked items in the price range are (2,1) and (1,2). Example 3: Input: grid = [[1,1,1],[0,0,1],[2,3,4]], pricing = [2,3], start = [0,0], k = 3 Output: [[2,1],[2,0]] Explanation: You start at (0,0). With a price range of [2,3], we can take items from (2,0) and (2,1). The ranks of these items are: - (2,1) with distance 5 - (2,0) with distance 6 Thus, the 2 highest ranked items in the price range are (2,1) and (2,0). Note that k = 3 but there are only 2 reachable items within the price range. Constraints: m == grid.length n == grid[i].length 1 <= m, n <= 105 1 <= m n <= 105 0 <= grid[i][j] <= 105 pricing.length == 2 2 <= low <= high <= 105 start.length == 2 0 <= row <= m - 1 0 <= col <= n - 1 grid[row][col] > 0 1 <= k <= m n

Explanation

Here's the solution to the problem:

• BFS for Distance: Use Breadth-First Search (BFS) to calculate the shortest distance from the start position to all other cells in the grid.
• Filter and Rank: Iterate through the grid, and if a cell's price falls within the pricing range, store its row, column, price, and calculated distance. Sort these items based on the specified ranking criteria (distance, price, row, column).

• Return Top K: Return the top k items from the sorted list.

• Runtime Complexity: O(m*n*log(m*n)), where m and n are the dimensions of the grid.

• Storage Complexity: O(m*n)

Code

    from collections import deque

def highestRankedKItems(grid, pricing, start, k):
    m, n = len(grid), len(grid[0])
    low, high = pricing
    row, col = start

    distances = [[-1] * n for _ in range(m)]
    distances[row][col] = 0
    q = deque([(row, col)])

    reachable_items = []

    while q:
        r, c = q.popleft()

        price = grid[r][c]
        if low <= price <= high:
            reachable_items.append((r, c, distances[r][c], price))

        directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        for dr, dc in directions:
            nr, nc = r + dr, c + dc
            if 0 <= nr < m and 0 <= nc < n and grid[nr][nc] != 0 and distances[nr][nc] == -1:
                distances[nr][nc] = distances[r][c] + 1
                q.append((nr, nc))

    reachable_items.sort(key=lambda x: (x[2], x[3], x[0], x[1]))

    result = []
    for i in range(min(k, len(reachable_items))):
        result.append([reachable_items[i][0], reachable_items[i][1]])

    return result