Grokking #198

class Solution {

  // Dijkstra
  class NodeValue {
    Integer value; // the current effort to reach from start to current cell
    int row;
    int col;

    public NodeValue(int row, int col, Integer value) {
      this.row = row;
      this.col = col;
      this.value = value;
    }
  }

  int[][] DIRS = { {-1, 0}, {0, 1}, {1, 0}, {0, -1} };

  public int minimumEffortPath(int[][] heights) {
    int rows = heights.length;
    int cols = heights[0].length;

    int[][] distance = new int[rows][cols];
    for (int[] row : distance) {
      Arrays.fill(row, Integer.MAX_VALUE);
    }

    distance[0][0] = 0;

    PriorityQueue<NodeValue> pq = new PriorityQueue<NodeValue>((a,b) -> (a.value.compareTo(b.value)));
    pq.offer(new NodeValue(0, 0, 0));

    while (!pq.isEmpty()) {
      NodeValue at = pq.poll();
      int r = at.row;
      int c = at.col;

      // Early stop if met destination
      if (r == rows - 1 && c == cols - 1) {
        return distance[r][c];
      }

      // Skip if we have smaller distance value
      if (at.value > distance[r][c]) {
        continue;
      }

      for (int i = 0; i < 4; i++) {
        int rr = r + DIRS[i][0];
        int cc = c + DIRS[i][1];

        if (0 <= rr && rr < rows && 0 <= cc && cc < cols) {
          // Effort to move from current cell (r, c) to next cell (rr, cc)
          int effort = Math.abs(heights[rr][cc] - heights[r][c]);

          // New effort is the max of 2 following values:
          // 1. The effort from the start cell to current cell (r, c)
          // 2. And the effort from current cell (r, c) to next cell (rr, cc)
          int newEffort = Math.max(distance[r][c], effort);

          if (newEffort < distance[rr][cc]) {
            // Update current distance if we found less effort path
            distance[rr][cc] = newEffort;

            pq.offer(new NodeValue(rr, cc, distance[rr][cc]));
          }
        }
      }
    }

    return distance[rows - 1][cols - 1];
  }
}