1
/**
2
 * @param {number[][]} heights
3
 * @return {number}
4
 * T: O((M*N)log(M*N))
5
 * S: O(M*N)
6
 */
7
var minimumEffortPath = function (heights) {
8
  const directions = [
9
    [1, 0],
10
    [0, 1],
11
    [-1, 0],
12
    [0, -1],
13
  ];
14
  const row = heights.length;
15
  const col = heights[0].length;
16
  const differences = [];
17
  for (let i = 0; i < row; i++) {
18
    for (let j = 0; j < col; j++) {
19
      if (!differences[i]) {
20
        differences[i] = [Infinity];
21
      } else {
22
        differences[i].push(Infinity);
23
      }
24
    }
25
  }
26
  differences[0][0] = 0;
27
  const pq = new PriorityQueue();
28
  pq.push([0, 0], 0);
29
  while (pq.data.length > 0) {
30
    const node = pq.shift();
31
    const difference = node.priority;
32
    const [x, y] = node.val;
33
    directions.forEach(([dx, dy]) => {
34
      const newX = x + dx;
35
      const newY = y + dy;
36
      if (newX >= 0 && newX < row && newY >= 0 && newY < col) {
37
        const currentDiff = Math.abs(heights[newX][newY] - heights[x][y]);
38
        const maxDiff = Math.max(currentDiff, differences[x][y]);
39
        if (differences[newX][newY] > maxDiff) {
40
          differences[newX][newY] = maxDiff;
41
          pq.push([newX, newY], maxDiff);
42
        }
43
      }
44
    });
45
  }
46
  return differences[row - 1][col - 1];
47
};
48

49
const swap = (arr, i, j) => {
50
  const temp = arr[i];
51
  arr[i] = arr[j];
52
  arr[j] = temp;
53
};
54

55
function Node(val, priority) {
56
  this.val = val;
57
  this.priority = priority;
58
}
59

60
function PriorityQueue() {
61
  this.data = [];
62
}
63

64
PriorityQueue.prototype.push = function push(val, priority) {
65
  const node = new Node(val, priority);
66
  this.data.push(node);
67
  let index = this.data.length - 1;
68
  while (index > 0) {
69
    const parentIndex = Math.floor((index - 1) / 2);
70
    const parent = this.data[parentIndex];
71
    if (parent.priority > node.priority) {
72
      swap(this.data, parentIndex, index);
73
      index = parentIndex;
74
    } else {
75
      break;
76
    }
77
  }
78
};
79

80
PriorityQueue.prototype.shift = function shift() {
81
  const minNode = this.data[0] || {};
82
  const lastNode = this.data.pop();
83
  if (this.data.length < 1) {
84
    return minNode;
85
  }
86
  this.data[0] = lastNode;
87
  let index = 0;
88
  while (index < this.data.length) {
89
    const leftIndex = 2 * index + 1;
90
    const rightIndex = 2 * index + 2;
91
    const leftNode = this.data[leftIndex] || {};
92
    const rightNode = this.data[rightIndex] || {};
93
    let smallerIndex;
94
    if (leftNode.priority < lastNode.priority) {
95
      smallerIndex = leftIndex;
96
    }
97
    if (!smallerIndex && rightNode.priority < lastNode.priority) {
98
      smallerIndex = rightIndex;
99
    }
100
    if (smallerIndex && rightNode.priority < leftNode.priority) {
101
      smallerIndex = rightIndex;
102
    }
103
    if (!smallerIndex) {
104
      break;
105
    }
106
    swap(this.data, index, smallerIndex);
107
    index = smallerIndex;
108
  }
109
  return minNode;
110
};