Jump Game

Definition

Definition

The Jump Game Algorithm determines if it's possible to reach the last index of an array starting from the first index, given that each element in the array represents the maximum number of steps that can be taken from that position

Explanation

The algorithm iterates through each element in the array, keeping track of the maximum reachable index. If at any point the current index exceeds this maximum reachable index, it indicates that it's not possible to reach the end

Guidance

• Set a starting point at the beginning of the array
• Traverse each number in the array
  • for each number
  • determine if advancing by the number of steps it indicates would take you farther than before
  • update your furthest reachable position accordingly
  • if you can already reach the end from your current position return true
• If you've covered all numbers without reaching the end return false

Tips

• keep track of the maximum reachable index as you iterate through the array
• if at any point the current index exceeds the maximum reachable index, it's not possible to reach the end

Practice

Practice

canReachEnd(nums):
  max_reachable = 0
  for i from 0 to length(nums) - 1:
    if i > max_reachable:
      return false
    max_reachable = max(max_reachable, i + nums[i])
    if max_reachable >= length(nums) - 1:
      return true
  return false

Solution

package main

import (
	"math"
)

func backtrackingJumpGame(numbers []int, startIndex int, currentJumps []int) bool {
	if startIndex == len(numbers)-1 {
		return true
	}

	maxJumpLength := int(math.Min(float64(numbers[startIndex]), float64(len(numbers)-1-startIndex)))

	for jumpLength := maxJumpLength; jumpLength > 0; jumpLength-- {
		nextIndex := startIndex + jumpLength
		currentJumps = append(currentJumps, nextIndex)

		isJumpSuccessful := backtrackingJumpGame(numbers, nextIndex, currentJumps)

		if isJumpSuccessful {
			return true
		}

		currentJumps = currentJumps[:len(currentJumps)-1]
	}

	return false
}

func dpBottomUpJumpGame(numbers []int) bool {
	cellsGoodness := make([]bool, len(numbers))
	cellsGoodness[len(cellsGoodness)-1] = true

	for cellIndex := len(numbers) - 2; cellIndex >= 0; cellIndex-- {
		maxJumpLength := int(math.Min(float64(numbers[cellIndex]), float64(len(numbers)-1-cellIndex)))

		for jumpLength := maxJumpLength; jumpLength > 0; jumpLength-- {
			nextIndex := cellIndex + jumpLength
			if cellsGoodness[nextIndex] {
				cellsGoodness[cellIndex] = true
				break
			}
		}
	}

	return cellsGoodness[0]
}

func dpTopDownJumpGame(numbers []int, startIndex int, currentJumps []int, cellsGoodness []bool) bool {
	if startIndex == len(numbers)-1 {
		return true
	}

	currentCellsGoodness := make([]bool, len(cellsGoodness))
	copy(currentCellsGoodness, cellsGoodness)
	if len(currentCellsGoodness) == 0 {
		for range numbers {
			currentCellsGoodness = append(currentCellsGoodness, false)
		}
		currentCellsGoodness[len(cellsGoodness)-1] = true
	}

	maxJumpLength := int(math.Min(float64(numbers[startIndex]), float64(len(numbers)-1-startIndex)))

	for jumpLength := maxJumpLength; jumpLength > 0; jumpLength-- {
		nextIndex := startIndex + jumpLength

		if !currentCellsGoodness[nextIndex] {
			currentJumps = append(currentJumps, nextIndex)

			isJumpSuccessful := dpTopDownJumpGame(numbers, nextIndex, currentJumps, currentCellsGoodness)

			if isJumpSuccessful {
				return true
			}

			currentJumps = currentJumps[:len(currentJumps)-1]

			currentCellsGoodness[nextIndex] = true
		}
	}

	return false
}

func greedyJumpGame(numbers []int) bool {
	leftGoodPosition := len(numbers) - 1

	for numberIndex := len(numbers) - 2; numberIndex >= 0; numberIndex-- {
		maxCurrentJumpLength := numberIndex + numbers[numberIndex]
		if maxCurrentJumpLength >= leftGoodPosition {
			leftGoodPosition = numberIndex
		}
	}

	return leftGoodPosition == 0
}

import java.util.*;

public class JumpGame {

  public static boolean backtrackingJumpGame(int[] numbers, int startIndex, List<Integer> currentJumps) {
    if (startIndex == numbers.length - 1) {
      return true;
    }

    int maxJumpLength = Math.min(numbers[startIndex], numbers.length - 1 - startIndex);

    for (int jumpLength = maxJumpLength; jumpLength > 0; jumpLength--) {
      int nextIndex = startIndex + jumpLength;
      currentJumps.add(nextIndex);

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

      if (isJumpSuccessful) {
        return true;
      }

      currentJumps.remove(currentJumps.size() - 1);
    }

    return false;
  }

  public static boolean dpBottomUpJumpGame(int[] numbers) {
    Boolean[] cellsGoodness = new Boolean[numbers.length];
    Arrays.fill(cellsGoodness, null);
    cellsGoodness[cellsGoodness.length - 1] = true;

    for (int cellIndex = numbers.length - 2; cellIndex >= 0; cellIndex--) {
      int maxJumpLength = Math.min(numbers[cellIndex], numbers.length - 1 - cellIndex);

      for (int jumpLength = maxJumpLength; jumpLength > 0; jumpLength--) {
        int nextIndex = cellIndex + jumpLength;
        if (cellsGoodness[nextIndex] != null && cellsGoodness[nextIndex]) {
          cellsGoodness[cellIndex] = true;
          break;
        }
      }
    }

    return cellsGoodness[0] != null && cellsGoodness[0];
  }

  public static boolean dpTopDownJumpGame(int[] numbers, int startIndex, List<Integer> currentJumps, Boolean[] cellsGoodness) {
    if (startIndex == numbers.length - 1) {
      return true;
    }

    Boolean[] currentCellsGoodness = Arrays.copyOf(cellsGoodness, cellsGoodness.length);
    if (currentCellsGoodness.length == 0) {
      currentCellsGoodness = new Boolean[numbers.length];
      Arrays.fill(currentCellsGoodness, null);
      currentCellsGoodness[cellsGoodness.length - 1] = true;
    }

    int maxJumpLength = Math.min(numbers[startIndex], numbers.length - 1 - startIndex);

    for (int jumpLength = maxJumpLength; jumpLength > 0; jumpLength--) {
      int nextIndex = startIndex + jumpLength;

      if (currentCellsGoodness[nextIndex] != Boolean.FALSE) {
        currentJumps.add(nextIndex);

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

        if (isJumpSuccessful) {
          return true;
        }

        currentJumps.remove(currentJumps.size() - 1);

        currentCellsGoodness[nextIndex] = false;
      }
    }

    return false;
  }

  public static boolean greedyJumpGame(int[] numbers) {
    int leftGoodPosition = numbers.length - 1;

    for (int numberIndex = numbers.length - 2; numberIndex >= 0; numberIndex--) {
      int maxCurrentJumpLength = numberIndex + numbers[numberIndex];
      if (maxCurrentJumpLength >= leftGoodPosition) {
        leftGoodPosition = numberIndex;
      }
    }

    return leftGoodPosition == 0;
  }
}

function backtrackingJumpGame(numbers, startIndex = 0, currentJumps = []) {
  if (startIndex === numbers.length - 1) {
    return true;
  }

  const maxJumpLength = Math.min(
    numbers[startIndex],
    numbers.length - 1 - startIndex,
  );

  for (let jumpLength = maxJumpLength; jumpLength > 0; jumpLength -= 1) {
    const nextIndex = startIndex + jumpLength;
    currentJumps.push(nextIndex);

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

    if (isJumpSuccessful) {
      return true;
    }

    currentJumps.pop();
  }

  return false;
}

function dpBottomUpJumpGame(numbers) {
  const cellsGoodness = Array(numbers.length).fill(undefined);
  cellsGoodness[cellsGoodness.length - 1] = true;

  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;
        break;
      }
    }
  }

  return cellsGoodness[0] === true;
}

function dpTopDownJumpGame(
  numbers,
  startIndex = 0,
  currentJumps = [],
  cellsGoodness = [],
) {
  if (startIndex === numbers.length - 1) {
    return true;
  }

  const currentCellsGoodness = [...cellsGoodness];
  if (!currentCellsGoodness.length) {
    numbers.forEach(() => currentCellsGoodness.push(undefined));
    currentCellsGoodness[cellsGoodness.length - 1] = true;
  }

  const maxJumpLength = Math.min(
    numbers[startIndex],
    numbers.length - 1 - startIndex,
  );

  for (let jumpLength = maxJumpLength; jumpLength > 0; jumpLength -= 1) {
    const nextIndex = startIndex + jumpLength;

    if (currentCellsGoodness[nextIndex] !== false) {
      currentJumps.push(nextIndex);

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

      if (isJumpSuccessful) {
        return true;
      }

      currentJumps.pop();

      currentCellsGoodness[nextIndex] = false;
    }
  }

  return false;
}

function greedyJumpGame(numbers) {
  let leftGoodPosition = numbers.length - 1;

  for (
    let numberIndex = numbers.length - 2;
    numberIndex >= 0;
    numberIndex -= 1
  ) {
    const maxCurrentJumpLength = numberIndex + numbers[numberIndex];
    if (maxCurrentJumpLength >= leftGoodPosition) {
      leftGoodPosition = numberIndex;
    }
  }

  return leftGoodPosition === 0;
}

fun backtrackingJumpGame(numbers: IntArray, startIndex: Int = 0, currentJumps: MutableList<Int> = mutableListOf()): Boolean {
    if (startIndex == numbers.size - 1) {
        return true
    }

    val maxJumpLength = Math.min(numbers[startIndex], numbers.size - 1 - startIndex)

    for (jumpLength in maxJumpLength downTo 1) {
        val nextIndex = startIndex + jumpLength
        currentJumps.add(nextIndex)

        val isJumpSuccessful = backtrackingJumpGame(numbers, nextIndex, currentJumps)

        if (isJumpSuccessful) {
            return true
        }

        currentJumps.removeAt(currentJumps.size - 1)
    }

    return false
}

fun dpBottomUpJumpGame(numbers: IntArray): Boolean {
    val cellsGoodness = Array(numbers.size) { _ -> null }
    cellsGoodness[cellsGoodness.size - 1] = true

    for (cellIndex in numbers.size - 2 downTo 0) {
        val maxJumpLength = Math.min(numbers[cellIndex], numbers.size - 1 - cellIndex)

        for (jumpLength in maxJumpLength downTo 1) {
            val nextIndex = cellIndex + jumpLength
            if (cellsGoodness[nextIndex] == true) {
                cellsGoodness[cellIndex] = true
                break
            }
        }
    }

    return cellsGoodness[0] == true
}

fun dpTopDownJumpGame(numbers: IntArray, startIndex: Int = 0, currentJumps: MutableList<Int> = mutableListOf(), cellsGoodness: MutableList<Boolean?> = mutableListOf()): Boolean {
    if (startIndex == numbers.size - 1) {
        return true
    }

    val currentCellsGoodness = cellsGoodness.toMutableList()
    if (currentCellsGoodness.isEmpty()) {
        repeat(numbers.size) { _ -> currentCellsGoodness.add(null) }
        currentCellsGoodness[currentCellsGoodness.size - 1] = true
    }

    val maxJumpLength = Math.min(numbers[startIndex], numbers.size - 1 - startIndex)

    for (jumpLength in maxJumpLength downTo 1) {
        val nextIndex = startIndex + jumpLength

        if (currentCellsGoodness[nextIndex] != false) {
            currentJumps.add(nextIndex)

            val isJumpSuccessful = dpTopDownJumpGame(numbers, nextIndex, currentJumps, currentCellsGoodness)

            if (isJumpSuccessful) {
                return true
            }

            currentJumps.removeAt(currentJumps.size - 1)

            currentCellsGoodness[nextIndex] = false
        }
    }

    return false
}

fun greedyJumpGame(numbers: IntArray): Boolean {
    var leftGoodPosition = numbers.size - 1

    for (numberIndex in numbers.size - 2 downTo 0) {
        val maxCurrentJumpLength = numberIndex + numbers[numberIndex]
        if (maxCurrentJumpLength >= leftGoodPosition) {
            leftGoodPosition = numberIndex
        }
    }

    return leftGoodPosition == 0
}

def backtracking_jump_game(numbers, start_index=0, current_jumps=None):
    if current_jumps is None:
        current_jumps = []

    if start_index == len(numbers) - 1:
        return True

    max_jump_length = min(numbers[start_index], len(numbers) - 1 - start_index)

    for jump_length in range(max_jump_length, 0, -1):
        next_index = start_index + jump_length
        current_jumps.append(next_index)

        is_jump_successful = backtracking_jump_game(numbers, next_index, current_jumps)

        if is_jump_successful:
            return True

        current_jumps.pop()

    return False


def dp_bottom_up_jump_game(numbers):
    cells_goodness = [None] * len(numbers)
    cells_goodness[-1] = True

    for cell_index in range(len(numbers) - 2, -1, -1):
        max_jump_length = min(numbers[cell_index], len(numbers) - 1 - cell_index)

        for jump_length in range(max_jump_length, 0, -1):
            next_index = cell_index + jump_length
            if cells_goodness[next_index] is True:
                cells_goodness[cell_index] = True
                break

    return cells_goodness[0] is True


def dp_top_down_jump_game(numbers, start_index=0, current_jumps=None, cells_goodness=None):
    if current_jumps is None:
        current_jumps = []
    if cells_goodness is None:
        cells_goodness = []

    if start_index == len(numbers) - 1:
        return True

    current_cells_goodness = cells_goodness.copy()
    if not current_cells_goodness:
        current_cells_goodness.extend([None] * len(numbers))
        current_cells_goodness[-1] = True

    max_jump_length = min(numbers[start_index], len(numbers) - 1 - start_index)

    for jump_length in range(max_jump_length, 0, -1):
        next_index = start_index + jump_length

        if current_cells_goodness[next_index] is not False:
            current_jumps.append(next_index)

            is_jump_successful = dp_top_down_jump_game(numbers, next_index, current_jumps, current_cells_goodness)

            if is_jump_successful:
                return True

            current_jumps.pop()

            current_cells_goodness[next_index] = False

    return False


def greedy_jump_game(numbers):
    left_good_position = len(numbers) - 1

    for number_index in range(len(numbers) - 2, -1, -1):
        max_current_jump_length = number_index + numbers[number_index]
        if max_current_jump_length >= left_good_position:
            left_good_position = number_index

    return left_good_position == 0

fn backtracking_jump_game(numbers: &[i32], start_index: usize, current_jumps: &mut Vec<usize>) -> bool {
    if start_index == numbers.len() - 1 {
        return true;
    }

    let max_jump_length = numbers[start_index].min(numbers.len() as i32 - 1 - start_index);

    for jump_length in (1..=max_jump_length).rev() {
        let next_index = start_index + jump_length as usize;
        current_jumps.push(next_index);

        let is_jump_successful = backtracking_jump_game(numbers, next_index, current_jumps);

        if is_jump_successful {
            return true;
        }

        current_jumps.pop();
    }

    false
}

fn dp_bottom_up_jump_game(numbers: &[i32]) -> bool {
    let mut cells_goodness = vec![None; numbers.len()];
    cells_goodness[cells_goodness.len() - 1] = Some(true);

    for cell_index in (0..numbers.len() - 1).rev() {
        let max_jump_length = numbers[cell_index].min(numbers.len() as i32 - 1 - cell_index as i32);

        for jump_length in (1..=max_jump_length).rev() {
            let next_index = cell_index + jump_length as usize;
            if cells_goodness[next_index] == Some(true) {
                cells_goodness[cell_index] = Some(true);
                break;
            }
        }
    }

    cells_goodness[0] == Some(true)
}

fn dp_top_down_jump_game(numbers: &[i32], start_index: usize, current_jumps: &mut Vec<usize>, cells_goodness: &mut Vec<Option<bool>>) -> bool {
    if start_index == numbers.len() - 1 {
        return true;
    }

    let mut current_cells_goodness = cells_goodness.clone();
    if current_cells_goodness.is_empty() {
        current_cells_goodness.extend(vec![None; numbers.len()]);
        current_cells_goodness[cells_goodness.len() - 1] = Some(true);
    }

    let max_jump_length = numbers[start_index].min(numbers.len() as i32 - 1 - start_index as i32);

    for jump_length in (1..=max_jump_length).rev() {
        let next_index = start_index + jump_length as usize;

        if current_cells_goodness[next_index] != Some(false) {
            current_jumps.push(next_index);

            let is_jump_successful = dp_top_down_jump_game(numbers, next_index, current_jumps, &mut current_cells_goodness);

            if is_jump_successful {
                return true;
            }

            current_jumps.pop();

            current_cells_goodness[next_index] = Some(false);
        }
    }

    false
}

fn greedy_jump_game(numbers: &[i32]) -> bool {
    let mut left_good_position = numbers.len() - 1;

    for number_index in (0..numbers.len() - 1).rev() {
        let max_current_jump_length = number_index + numbers[number_index] as usize;
        if max_current_jump_length >= left_good_position {
            left_good_position = number_index;
        }
    }

    left_good_position == 0
}

function backtrackingJumpGame(
  numbers: number[],
  startIndex: number = 0,
  currentJumps: number[] = [],
): boolean {
  if (startIndex === numbers.length - 1) {
    return true;
  }

  const maxJumpLength = Math.min(
    numbers[startIndex],
    numbers.length - 1 - startIndex,
  );

  for (let jumpLength = maxJumpLength; jumpLength > 0; jumpLength -= 1) {
    const nextIndex = startIndex + jumpLength;
    currentJumps.push(nextIndex);

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

    if (isJumpSuccessful) {
      return true;
    }

    currentJumps.pop();
  }

  return false;
}

function dpBottomUpJumpGame(numbers: number[]): boolean {
  const cellsGoodness: (boolean | undefined)[] = Array(numbers.length).fill(
    undefined,
  );
  cellsGoodness[cellsGoodness.length - 1] = true;

  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;
        break;
      }
    }
  }

  return cellsGoodness[0] === true;
}

function dpTopDownJumpGame(
  numbers: number[],
  startIndex: number = 0,
  currentJumps: number[] = [],
  cellsGoodness: (boolean | undefined)[] = [],
): boolean {
  if (startIndex === numbers.length - 1) {
    return true;
  }

  const currentCellsGoodness = [...cellsGoodness];
  if (!currentCellsGoodness.length) {
    numbers.forEach(() => currentCellsGoodness.push(undefined));
    currentCellsGoodness[cellsGoodness.length - 1] = true;
  }

  const maxJumpLength = Math.min(
    numbers[startIndex],
    numbers.length - 1 - startIndex,
  );

  for (let jumpLength = maxJumpLength; jumpLength > 0; jumpLength -= 1) {
    const nextIndex = startIndex + jumpLength;

    if (currentCellsGoodness[nextIndex] !== false) {
      currentJumps.push(nextIndex);

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

      if (isJumpSuccessful) {
        return true;
      }

      currentJumps.pop();

      currentCellsGoodness[nextIndex] = false;
    }
  }

  return false;
}

function greedyJumpGame(numbers: number[]): boolean {
  let leftGoodPosition = numbers.length - 1;

  for (
    let numberIndex = numbers.length - 2;
    numberIndex >= 0;
    numberIndex -= 1
  ) {
    const maxCurrentJumpLength = numberIndex + numbers[numberIndex];
    if (maxCurrentJumpLength >= leftGoodPosition) {
      leftGoodPosition = numberIndex;
    }
  }

  return leftGoodPosition === 0;
}