K Highest Ranked Items Within a Price Range

This approach leverages the properties of Breadth-First Search more effectively. BFS naturally explores the grid in layers of increasing distance. By processing items level by level, we can find the highest-ranked items in the correct order of the primary ranking criterion (distance). This allows us to stop the search as soon as we have found k items, avoiding unnecessary exploration of the grid.

• Initialize an empty list result to store the answers.
• Initialize a BFS queue with the start coordinates and a visited matrix.
• Start a while loop that runs as long as the queue is not empty. This loop represents processing levels.
  • Inside the loop, get the current levelSize of the queue.
  • Create a temporary list itemsOnLevel to store valid items found at the current distance.
  • Loop levelSize times to process all nodes at the current level:
    • Dequeue a cell (r, c).
    • If grid[r][c] is a valid item within the price range, add [price, r, c] to itemsOnLevel.
    • Enqueue all valid, unvisited neighbors.
  • After the inner loop, sort itemsOnLevel based on price, then row, then column.
  • Iterate through the sorted itemsOnLevel and add each item's coordinates [r, c] to the result list.
  • If result.size() becomes equal to k, return result immediately.
• If the while loop finishes (queue becomes empty) and we have fewer than k items, return the result list as is.

The algorithm works by performing a level-order (or layer-by-layer) BFS.

1. Initialization: We start a BFS from the start cell. We use a queue for the BFS, a visited set or array to avoid cycles, and a list to store the final results.
2. Level-Order Traversal: The BFS proceeds in levels, where each level corresponds to a specific distance from the start. In each iteration of the main loop, we process all nodes at the current distance.
   • We find all items at the current level that are within the price range and add them to a temporary list for this level.
   • Since all items found in the same level have the same distance, we only need to sort this temporary list based on the remaining criteria: price, row, and column.
   • After sorting, we add these items to our final result list.
3. Early Exit: We continuously check the size of our result list. As soon as it contains k items, we have found the k highest-ranked items because any item found in subsequent BFS levels will have a greater distance and thus a lower rank. We can then terminate the BFS and return the result. If the BFS completes before we find k items, we return all the valid items found.

import java.util.*;

class Solution {
    public List<List<Integer>> highestRankedKItems(int[][] grid, int[] pricing, int[] start, int k) {
        int m = grid.length;
        int n = grid[0].length;
        int low = pricing[0];
        int high = pricing[1];

        List<List<Integer>> result = new ArrayList<>();
        Queue<int[]> queue = new LinkedList<>();
        boolean[][] visited = new boolean[m][n];

        queue.offer(new int[]{start[0], start[1]});
        visited[start[0]][start[1]] = true;

        int[] dr = {-1, 1, 0, 0};
        int[] dc = {0, 0, -1, 1};

        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            List<int[]> itemsOnLevel = new ArrayList<>();

            for (int i = 0; i < levelSize; i++) {
                int[] curr = queue.poll();
                int r = curr[0];
                int c = curr[1];
                int price = grid[r][c];

                if (price > 1 && price >= low && price <= high) {
                    itemsOnLevel.add(new int[]{price, r, c});
                }

                for (int j = 0; j < 4; j++) {
                    int nr = r + dr[j];
                    int nc = c + dc[j];

                    if (nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] != 0 && !visited[nr][nc]) {
                        visited[nr][nc] = true;
                        queue.offer(new int[]{nr, nc});
                    }
                }
            }

            // Sort items found on the current level
            Collections.sort(itemsOnLevel, (a, b) -> {
                if (a[0] != b[0]) return a[0] - b[0]; // price
                if (a[1] != b[1]) return a[1] - b[1]; // row
                return a[2] - b[2]; // col
            });

            // Add sorted items to result until we have k items
            for (int[] item : itemsOnLevel) {
                if (result.size() < k) {
                    result.add(Arrays.asList(item[1], item[2]));
                }
            }
            if (result.size() == k) {
                return result;
            }
        }

        return result;
    }
}