Jump Game V LeetCode solution in JavaScript

1
var maxJumps = function (arr, d) {
2
  let n = arr.length;
3
  let dp = new Array(n).fill(0);
4
  let result = 0;
5

6
  // Time complexity:
7
  // O(nlogn) + O(n*d) => O(ologn)
8

9
  // First we sort the arr (small -> large) , then calculating DP by sortedArr.
10
  // O(nlogn)
11
  let sortedArr = arr.map((v, i) => [v, i]).sort((a, b) => a[0] - b[0]);
12

13
  // Shifting with single way
14
  // mid -> left ; mid -> right
15
  // O(n*d)
16
  for (let index = 1; index < n; index++) {
17
    let [v, i] = sortedArr[index];
18

19
    for (let shift = 1; shift <= d; shift++) {
20
      if (i + shift >= n || arr[i + shift] >= arr[i]) break;
21
      dp[i] = Math.max(dp[i], dp[i + shift] + 1);
22
      if (dp[i] > result) result = dp[i];
23
    }
24

25
    for (let shift = -1; shift >= -d; shift--) {
26
      if (i + shift < 0 || arr[i + shift] >= arr[i]) break;
27
      dp[i] = Math.max(dp[i], dp[i + shift] + 1);
28
      if (dp[i] > result) result = dp[i];
29
    }
30
  }
31

32
  return result + 1;
33
};