K Highest Ranked Items Within a Price Range LeetCode solution in Java

1
class Solution {
2
  public List<List<Integer>> highestRankedKItems(int[][] grid, int[] pricing, int[] start, int k) {
3
    int low = pricing[0];
4
    int high = pricing[1];
5
    int n = grid.length;
6
    int m = grid[0].length;
7
    Queue<Pair> q = new LinkedList<>();
8
    boolean[][] visited = new boolean[n][m];
9
    ArrayList<Pair> list = new ArrayList<>();
10
    int dis = 0;
11
    q.add(new Pair(start[0], start[1], grid[start[0]][start[1]], 0));
12
    visited[start[0]][start[1]] = true;
13
    // normal bfs starts here.
14
    while (!q.isEmpty()) {
15
      int size = q.size();
16
      dis++;
17
      while (size-- > 0) {
18
        Pair p = q.remove();
19
        int x = p.x;
20
        int y = p.y;
21
        int val = p.val;
22
        // if nearby cells in range add that element to queue and mark the cell as visited.
23
        if (isInRange(x + 1, y, n, m, grid, visited, low, high)) {
24
          q.add(new Pair(x + 1, y, grid[x + 1][y], dis));
25
          visited[x + 1][y] = true;
26
        }
27
        if (isInRange(x - 1, y, n, m, grid, visited, low, high)) {
28
          q.add(new Pair(x - 1, y, grid[x - 1][y], dis));
29
          visited[x - 1][y] = true;
30
        }
31
        if (isInRange(x, y + 1, n, m, grid, visited, low, high)) {
32
          q.add(new Pair(x, y + 1, grid[x][y + 1], dis));
33
          visited[x][y + 1] = true;
34
        }
35
        if (isInRange(x, y - 1, n, m, grid, visited, low, high)) {
36
          q.add(new Pair(x, y - 1, grid[x][y - 1], dis));
37
          visited[x][y - 1] = true;
38
        }
39
        // add every element of queue to list.
40
        list.add(new Pair(p.x, p.y, p.val, p.dis));
41
      }
42
    }
43
    ArrayList<Pair> list2 = new ArrayList<>();
44
    for (Pair p : list) {
45
      // remove the values from list if they are not in pricing range and add that to list2.
46
      if (p.val != 1 && p.val >= low && p.val <= high) {
47
        list2.add(new Pair(p.x, p.y, p.val, p.dis));
48
      }
49
    }
50
    // Most important part. Sorting the list2 on basis of the conditions given in question. Higher
51
    // rank cells must be added first(before) in the list.
52
    Collections.sort(
53
        list2,
54
        new Comparator<Pair>() {
55
          @Override
56
          public int compare(Pair p1, Pair p2) {
57
            // first check on basis of distance (high value, then add it before the second pair).
58
            if (p1.dis > p2.dis) {
59
              return 1;
60
            } else if (p1.dis < p2.dis) {
61
              return -1;
62
            } else {
63
              // if distances are equal, then second check on basis of value (high value, then add
64
              // it before the second pair).
65
              if (p1.val > p2.val) {
66
                return 1;
67
              } else if (p1.val < p2.val) {
68
                return -1;
69
              } else {
70
                // if distances and values are equal, then third check on basis of x-coordinate
71
                // (high value, then add it before the second pair).
72
                if (p1.x > p2.x) {
73
                  return 1;
74
                } else if (p1.x < p2.x) {
75
                  return -1;
76
                } else {
77
                  // if distances, values and x-coordinate are equal, then fourth check on basis of
78
                  // y-coordinate (high value, then add it before the second pair).).
79
                  if (p1.y > p2.y) {
80
                    return 1;
81
                  } else {
82
                    return -1;
83
                  }
84
                }
85
              }
86
            }
87
          }
88
        });
89
    List<List<Integer>> ans = new ArrayList<>();
90
    // selecting only first k values from list2, and adding there x,y - coordinates in ans
91
    // arraylist.
92
    for (Pair p : list2) {
93
      if (k == 0) {
94
        break;
95
      }
96
      k--;
97
      List<Integer> temp = new ArrayList<>();
98
      temp.add(p.x);
99
      temp.add(p.y);
100
      ans.add(new ArrayList<>(temp));
101
    }
102
    return ans;
103
  }
104

105
  // check whether i, j is in range or not (ignore visited cells and cells with zero value)
106
  private boolean isInRange(
107
      int i, int j, int n, int m, int[][] grid, boolean[][] visited, int low, int high) {
108
    if (i < 0 || j < 0 || i >= n || j >= m || grid[i][j] == 0 || visited[i][j]) {
109
      return false;
110
    }
111
    return true;
112
  }
113
}
114

115
// Pair class for x-coordinate, y-coordinate, grid value, distance from start point
116
class Pair {
117
  int x;
118
  int y;
119
  int val;
120
  int dis;
121

122
  public Pair(int x, int y, int val, int dis) {
123
    this.x = x;
124
    this.y = y;
125
    this.val = val;
126
    this.dis = dis;
127
  }
128
}