2146. K Highest Ranked Items Within a Price Range

Problem Description

You are presented with a scenario where you're inside a shop represented by a 2D integer array called grid. Each cell in this array can be:

• A 0 indicating a wall, through which you cannot pass.
• A 1 indicating an empty space, through which you can move freely.
• Any other positive integer representing the price of an item located at that cell, which you can also move to and from.

Your movement is constrained such that you can only travel to adjacent cells horizontally or vertically, not diagonally, and each move counts as 1 step.

You have specific requirements for the items you are interested in: they must fall within a certain price range, [low, high], based on the pricing array. The starting point of your search is given by the start array [row, col], signifying the grid cell where you begin.

Your task is to find the k highest-ranked items based on the following criteria in order of priority:

1. Distance: The number of steps from the start. A shorter distance means a higher ranking.
2. Price: A lower price means a higher ranking, but it must be within your specified range.
3. Row Number: Items in a lower row are ranked higher.
4. Column Number: Among items in the same row, those in a lower column are ranked higher.

Your objective is to return the top k items' positions, ranked from highest to lowest based on these criteria. However, if there are less than k items that are reachable and within the price range, you must return the positions of all these items.

Intuition

To solve this problem, a Breadth-First Search (BFS) approach is intuitive because we're looking for the shortest path from our starting point to each item, fulfilling the first and most critical ranking criterion: distance.

BFS allows us to explore the grid level by level, starting from the initial position. As we move from one cell to its adjacent cells, we keep track of the distance we've covered in steps. We can then simultaneously check each newly discovered cell to determine whether it contains an item within our price range.

While performing BFS, for each item we encounter that fits within our budget, we store its distance from the start, its price, and its coordinates. We then mark the cell as visited (i.e., set it to 0 to indicate a wall) to avoid revisiting it.

After the BFS is completed and we’ve explored all the reachable cells, we have a list of items, each with its distance, price, and position. We sort this list according to our ranking criteria. First by distance, then by price, then by row, and finally by column number.

Once sorted, we slice the list to retrieve the top k ranked items. If there were fewer than k items available, we would end up with a list of all applicable items. Only the row and column positions of these top k ranked items are returned, as specified by the problem description.

The key to making this approach work is to prioritize our sorting according to the stated ranking criteria and to carefully implement BFS to ensure that we do not miss any items or consider any twice.

Learn more about Breadth-First Search, Sorting and Heap (Priority Queue) patterns.

Solution Approach

The provided solution implements the BFS (Breadth-First Search) strategy using the following steps:

1. Initialization: Before starting the BFS, the initial setup is done by defining the size of the grid (m x n), and combining the start and pricing arrays to obtain the starting row (row), column (col), and the low and high price limits. An empty list is created to store details of the items found (items), and an initial check is performed to see if the starting position itself is an item within the price range and gets added to items if so.

2. BFS Queue: A queue data structure is used to perform the BFS. This is initialized with the starting position and an initial depth (distance) of 0. The value of the starting position in the grid is set to 0 which both marks it as visited and prevents it from being returned more than once.

3. BFS Execution: The BFS is then carried out until the queue is empty. Each element in the queue is a tuple with the current cell's coordinates and the distance from the start. In the loop, adjacent cells are calculated and checked against grid boundaries and whether they've been visited (not a 0).

4. Item Discovery & Queue Update: For every unvisited and valid adjacent cell that lies within the specified price range, its details are appended to items (including its distance, price, and coordinates). Regardless of whether the cell has an item or is just an empty cell, it's marked as visited, and the new cell with the updated distance is added to the queue for further exploration.

5. Sorting: After BFS concludes, we have potentially discovered all items in the grid. This list of items is then sorted by the sort() method of the list, which applies the sorting based on the tuples inside items. The list is sorted by the distance first (since the distances are the first element of the tuples), then by price (second element), row number (third element), and column number (fourth element). This automated sorting by tuple comparison naturally sorts according to all the ranking criteria specified.

6. Result Formation: Finally, we slice the sorted list to only take the first k elements with [:k]. The list slicing accommodates the situation where there may be fewer than k items found. We only return the row and column positions of these items, hence we map the item[2:] (row and column) of each item to the output list.

This solution approach ensures that we respect the priority of the ranking criteria, beginning with finding the shortest paths using BFS, then selecting and ordering the target items as needed. The BFS strategy effectively handles the grid exploration, while Python's built-in sorting mechanisms and list operations allow us to efficiently organize and return the final results.

Example Walkthrough

Let's consider a small grid to illustrate the solution approach:

Suppose our grid looks like this, where S denotes the starting position:

1S 1 4
21 0 2
35 1 3

We're given the following input parameters:

• start = [0, 0] (the position of S)
• pricing = [2, 5] (the price range)
• k = 2 (we are interested in the top 2 items)

Let's walk through the solution steps with this grid:

1. Initialization: We set row = 0 and col = 0 as our starting point. The price limits are low = 2 and high = 5. The items list is created and starts off empty, as S is not an item.

2. BFS Queue: We initialize our BFS queue with [(0, 0, 0)] where the tuple represents (row, col, distance). The grid's starting position is marked as visited by setting it to 0.

3. BFS Execution: We begin BFS, taking items from the queue one by one. We first dequeue the starting point (0, 0, 0) and look at its adjacent open cells (0, 1) and (1, 0) since only horizontal and vertical moves are allowed.

4. Item Discovery & Queue Update:

   • At (0, 1), there's a 1, which is an open space but not an item within the price range. Mark it visited and enqueue (0, 1, 1) for distance 1.
   • At (1, 0), there's also a 1, treated similarly as above.

   Now our queue has two positions: [(0, 1, 1), (1, 0, 1)].

   Dequeue (0, 1, 1), check its adjacent cells:

   • (0, 2) has an item priced 4, which is within the range. We add (1, 4, 0, 2) to items (distance, price, row, col) and enqueue the position for further BFS.

   Do the same for (1, 0, 1):

   • (2, 0) contains an item priced 5, within range. (1, 5, 2, 0) is added to items.
   • (1, 1) is a wall, thus ignored.

   The queue now contains [(0, 2, 1), (2, 0, 1), (1, 0, 1)].

Continue BFS until the queue is empty, adding discovered items within the price range to the items list.

5. Sorting: After BFS, we have items = [(1, 4, 0, 2), (1, 5, 2, 0)]. We sort this list:

   • First by distance: Both items have the same distance, so no change.
   • Then by price: Both items are also priced within our range, so no change again.
   • Then by row number: The item at (0, 2) is in a higher row (closer to the top) than the item at (2, 0), so the order remains the same.
   • Lastly, by column number: No need to sort since they are in different rows.

6. Result Formation: We want the top k=2 ranked items, so we take the first 2 elements in items and map only their row and column positions to the output format: The final output is [ [0, 2], [2, 0] ] representing the grid positions of the items.

These steps concatenate to provide a solution that respects the priority of distance, price, row and column positions while seeking the top k items within the specified range using Breadth-First Search.

Solution Implementation

Time and Space Complexity

The given Python code performs a breadth-first search (BFS) on the given grid to find items within the specified pricing range that are reachable from the start position, then ranks those items and returns up to k of the highest-ranked items.

Time Complexity:

The BFS algorithm traverses each cell of the grid at most once. Therefore, the time complexity of the BFS traversal is O(m*n), where m is the number of rows and n is the number of columns in the grid, because it needs to process every cell. In addition to the traversal, the algorithm appends items to the items list if they fall within the pricing range and are not already visited.

In the worst-case scenario, the number of items appended to the items list can be O(m*n) if every cell falls within the pricing range. Sorting these items contributes to an additional time complexity of O((m*n)*log(m*n)) due to the use of the sort function on the items list.

Hence, the time complexity of this algorithm is dominated by the sorting operation, resulting in an overall time complexity of O((m*n)*log(m*n)).

Space Complexity:

Space complexity consists of the space required to store the q (queue), the items list, and the modifications to the grid. The queue, in the worst case, can contain O(min(m*n, k)) elements, when the BFS has found k items and they are pending to be processed or until all the cells are visited in a case where k is large.

The items list also can take up to O(m*n) space in the worst case, when every cell falls within the pricing range. The grid is modified in-place without using additional space, except for storing the modified values which do not take extra space beyond what is given as input.

Considering both the queue and the items list, the overall space complexity is O(m*n) because the space complexity does not depend on k. The largest area of space is taken by the items list which can potentially hold an item for every cell in the grid.

In conclusion, the time complexity of the code is O((m*n)*log(m*n)), and the space complexity is O(m*n).

Learn more about how to find time and space complexity quickly using problem constraints.