Jump Game

Input: [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

Input: [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum
             jump length is 0, which makes it impossible to reach the last index.

/**
 * BACKTRACKING approach of solving Jump Game.
 *
 * This is the inefficient solution where we try every single jump
 * pattern that takes us from the first position to the last.
 * We start from the first position and jump to every index that
 * is reachable. We repeat the process until last index is reached.
 * When stuck, backtrack.
 *
 * @param {number[]} numbers - array of possible jump length.
 * @param {number} startIndex - index from where we start jumping.
 * @param {number[]} currentJumps - current jumps path.
 * @return {boolean}
 */
export default function backtrackingJumpGame(numbers, startIndex = 0, currentJumps = []) {
  if (startIndex === numbers.length - 1) {
    // We've jumped directly to last cell. This situation is a solution.
    return true;
  }

  // Check what the longest jump we could make from current position.
  // We don't need to jump beyond the array.
  const maxJumpLength = Math.min(
    numbers[startIndex], // Jump is within array.
    numbers.length - 1 - startIndex, // Jump goes beyond array.
  );

  // Let's start jumping from startIndex and see whether any
  // jump is successful and has reached the end of the array.
  for (let jumpLength = maxJumpLength; jumpLength > 0; jumpLength -= 1) {
    // Try next jump.
    const nextIndex = startIndex + jumpLength;
    currentJumps.push(nextIndex);

    const isJumpSuccessful = backtrackingJumpGame(numbers, nextIndex, currentJumps);

    // Check if current jump was successful.
    if (isJumpSuccessful) {
      return true;
    }

    // BACKTRACKING.
    // If previous jump wasn't successful then retreat and try the next one.
    currentJumps.pop();
  }

  return false;
}

/**
 * DYNAMIC PROGRAMMING BOTTOM-UP approach of solving Jump Game.
 *
 * This comes out as an optimisation of DYNAMIC PROGRAMMING TOP-DOWN approach.
 *
 * The observation to make here is that we only ever jump to the right.
 * This means that if we start from the right of the array, every time we
 * will query a position to our right, that position has already be
 * determined as being GOOD or BAD. This means we don't need to recurse
 * anymore, as we will always hit the memo table.
 *
 * We call a position in the array a "good" one if starting at that
 * position, we can reach the last index. Otherwise, that index
 * is called a "bad" one.
 *
 * @param {number[]} numbers - array of possible jump length.
 * @return {boolean}
 */
export default function dpBottomUpJumpGame(numbers) {
  // Init cells goodness table.
  const cellsGoodness = Array(numbers.length).fill(undefined);
  // Mark the last cell as "good" one since it is where we ultimately want to get.
  cellsGoodness[cellsGoodness.length - 1] = true;

  // Go throw all cells starting from the one before the last
  // one (since the last one is "good" already) and fill cellsGoodness table.
  for (let cellIndex = numbers.length - 2; cellIndex >= 0; cellIndex -= 1) {
    const maxJumpLength = Math.min(
      numbers[cellIndex],
      numbers.length - 1 - cellIndex,
    );

    for (let jumpLength = maxJumpLength; jumpLength > 0; jumpLength -= 1) {
      const nextIndex = cellIndex + jumpLength;
      if (cellsGoodness[nextIndex] === true) {
        cellsGoodness[cellIndex] = true;
        // Once we detected that current cell is good one we don't need to
        // do further cells checking.
        break;
      }
    }
  }

  // Now, if the zero's cell is good one then we can jump from it to the end of the array.
  return cellsGoodness[0] === true;
}

/**
 * DYNAMIC PROGRAMMING TOP-DOWN approach of solving Jump Game.
 *
 * This comes out as an optimisation of BACKTRACKING approach.
 *
 * It relies on the observation that once we determine that a certain
 * index is good / bad, this result will never change. This means that
 * we can store the result and not need to recompute it every time.
 *
 * We call a position in the array a "good" one if starting at that
 * position, we can reach the last index. Otherwise, that index
 * is called a "bad" one.
 *
 * @param {number[]} numbers - array of possible jump length.
 * @param {number} startIndex - index from where we start jumping.
 * @param {number[]} currentJumps - current jumps path.
 * @param {boolean[]} cellsGoodness - holds information about whether cell is "good" or "bad"
 * @return {boolean}
 */
export default function dpTopDownJumpGame(
  numbers,
  startIndex = 0,
  currentJumps = [],
  cellsGoodness = [],
) {
  if (startIndex === numbers.length - 1) {
    // We've jumped directly to last cell. This situation is a solution.
    return true;
  }

  // Init cell goodness table if it is empty.
  // This is DYNAMIC PROGRAMMING feature.
  const currentCellsGoodness = [...cellsGoodness];
  if (!currentCellsGoodness.length) {
    numbers.forEach(() => currentCellsGoodness.push(undefined));
    // Mark the last cell as "good" one since it is where we ultimately want to get.
    currentCellsGoodness[cellsGoodness.length - 1] = true;
  }

  // Check what the longest jump we could make from current position.
  // We don't need to jump beyond the array.
  const maxJumpLength = Math.min(
    numbers[startIndex], // Jump is within array.
    numbers.length - 1 - startIndex, // Jump goes beyond array.
  );

  // Let's start jumping from startIndex and see whether any
  // jump is successful and has reached the end of the array.
  for (let jumpLength = maxJumpLength; jumpLength > 0; jumpLength -= 1) {
    // Try next jump.
    const nextIndex = startIndex + jumpLength;

    // Jump only into "good" or "unknown" cells.
    // This is top-down dynamic programming optimisation of backtracking algorithm.
    if (currentCellsGoodness[nextIndex] !== false) {
      currentJumps.push(nextIndex);

      const isJumpSuccessful = dpTopDownJumpGame(
        numbers,
        nextIndex,
        currentJumps,
        currentCellsGoodness,
      );

      // Check if current jump was successful.
      if (isJumpSuccessful) {
        return true;
      }

      // BACKTRACKING.
      // If previous jump wasn't successful then retreat and try the next one.
      currentJumps.pop();

      // Mark current cell as "bad" to avoid its deep visiting later.
      currentCellsGoodness[nextIndex] = false;
    }
  }

  return false;
}

/**
 * GREEDY approach of solving Jump Game.
 *
 * This comes out as an optimisation of DYNAMIC PROGRAMMING BOTTOM_UP approach.
 *
 * Once we have our code in the bottom-up state, we can make one final,
 * important observation. From a given position, when we try to see if
 * we can jump to a GOOD position, we only ever use one - the first one.
 * In other words, the left-most one. If we keep track of this left-most
 * GOOD position as a separate variable, we can avoid searching for it
 * in the array. Not only that, but we can stop using the array altogether.
 *
 * We call a position in the array a "good" one if starting at that
 * position, we can reach the last index. Otherwise, that index
 * is called a "bad" one.
 *
 * @param {number[]} numbers - array of possible jump length.
 * @return {boolean}
 */
export default function greedyJumpGame(numbers) {
  // The "good" cell is a cell from which we may jump to the last cell of the numbers array.

  // The last cell in numbers array is for sure the "good" one since it is our goal to reach.
  let leftGoodPosition = numbers.length - 1;

  // Go through all numbers from right to left.
  for (let numberIndex = numbers.length - 2; numberIndex >= 0; numberIndex -= 1) {
    // If we can reach the "good" cell from the current one then for sure the current
    // one is also "good". Since after all we'll be able to reach the end of the array
    // from it.
    const maxCurrentJumpLength = numberIndex + numbers[numberIndex];
    if (maxCurrentJumpLength >= leftGoodPosition) {
      leftGoodPosition = numberIndex;
    }
  }

  // If the most left "good" position is the zero's one then we may say that it IS
  // possible jump to the end of the array from the first cell;
  return leftGoodPosition === 0;
}