SimuVedaAlgorithms Lab Open in the lab

Greedy / Intermediate

Jump Game Visualizer

Walk left to right and keep far, the furthest index reachable so far. If you ever stand on an index beyond far, you are stuck. If far reaches the end, you win.

Start the Jump Game simulation → Step forward and back, change the input, follow the code line by line in Java, Python, C++, C or JavaScript. Free, no sign-up.

Time and space complexity

Best timeO(n)
Average timeO(n)
Worst timeO(n)
Extra spaceO(1)

Worked example, step by step

The same steps the simulator shows, on a small input.

  1. Start at index 0. far = 0: only index 0 is reachable so far. [2, 3, 1, 1, 4]
  2. From index 0 you can jump 2, up to index 2. far grows to 2.
  3. From index 1 you can jump 3, up to index 4. far grows to 4.
  4. far = 4 reaches the last index 4. The answer is true.

Try it with your own input →

Jump game in Java, Python, C++, C and JavaScript

boolean canJump(int[] a) {
  int far = 0;
  for (int i = 0; i < a.length; i++) {
    if (i > far) return false;
    far = Math.max(far, i + a[i]);
    if (far >= a.length - 1) return true;
  }
  return true;
}
def can_jump(a):
    far = 0
    for i in range(len(a)):
        if i > far:
            return False
        far = max(far, i + a[i])
        if far >= len(a) - 1:
            return True
    return True
bool canJump(const vector<int>& a) {
  int far = 0, n = a.size();
  for (int i = 0; i < n; i++) {
    if (i > far) return false;
    far = max(far, i + a[i]);
    if (far >= n - 1) return true;
  }
  return true;
}
int canJump(int a[], int n) {
  int far = 0;
  for (int i = 0; i < n; i++) {
    if (i > far) return 0;
    if (i + a[i] > far) far = i + a[i];
    if (far >= n - 1) return 1;
  }
  return 1;
}
function canJump(a) {
  let far = 0;
  for (let i = 0; i < a.length; i++) {
    if (i > far) return false;
    far = Math.max(far, i + a[i]);
    if (far >= a.length - 1) return true;
  }
  return true;
}

In an interview

LeetCode 55, Jump Game: each value is the longest jump from that index. Can you reach the last index? Try 3, 2, 1, 0, 4 for a "no". Follow-up: 45 Jump Game II.

The DP answer (can I reach i?) is O(n²). The greedy insight is that reachable indexes always form one unbroken range [0..far], so a single number is enough.

More greedy