MediumGreedy

Jump Game

Q: Why does isset work for a memo that stores false?

isset is only false for a missing key or a null value, so a stored false still counts as set and is returned. That gives the three states the memo needs: missing for unknown, true for good and false for stuck. array_key_exists would work too, but isset is faster.

Q: Why is the greedy loop correct without trying paths?

The reachable indices form one block from 0 to $reach, because a jump can always be shorter than its maximum: reaching index k means every earlier index is reachable too. Each step can only push the end of that block forward, so one integer describes everything.

You get an array of non-negative integers nums. You start on index 0, and the value at each index is the longest jump you can make from there: from index i you may move to any index from i + 1 up to i + nums[i]. A value of 0 means you cannot move on from that index. Return true if some sequence of jumps lands on the last index, and false otherwise.

You never have to use the full length of a jump, and a jump may not go past the end of the array, so a large value near the end simply covers the rest of it. An array with a single element is already on its last index, so the answer is true. The value at the last index never matters.

Examples

Input

nums = [2, 0, 3, 0, 1]

OutputtrueWhyJump 2 from index 0 to index 2, over the 0, then 2 more from index 2 (which allows up to 3) to the last index, 4.

Input

nums = [3, 1, 1, 0, 6]

OutputfalseWhyIndices 0, 1 and 2 can reach at most index 3, which holds a 0. Every route stops there, and the 6 behind it is never reached.

Constraints

Size: 1 ≤ nums.length ≤ 2,000
Values: 0 ≤ nums[i] ≤ 100,000
Jumps: From index i you may land on any index from i + 1 to i + nums[i] that exists.
Time limit: 10 s per run, all cases

Run your code 2 more times to open the solutions. The idea sticks better after an attempt.

3 reference approaches in Python, from brute force to the one to reach for. Compare them with yours.

1 · Top-down: recursion with a memo per index

O(n²) time · O(n) space

A nested good(i) answers whether index i can reach the end. It tries every landing spot from the furthest one down, and a dictionary remembers each index's answer so no index is solved twice. The furthest spot is capped with min so a huge value never walks past the array. A path of 2,000 single steps recurses 2,000 deep, past Python's default limit of 1,000, so the function raises the limit first.

import sys


def can_jump(nums: list[int]) -> bool:
    sys.setrecursionlimit(10_000)
    last = len(nums) - 1
    memo: dict[int, bool] = {}

    def good(i: int) -> bool:
        if i == last:
            return True
        if i in memo:
            return memo[i]
        furthest = min(i + nums[i], last)
        result = False
        for j in range(furthest, i, -1):
            if good(j):
                result = True
                break
        memo[i] = result
        return result

    return good(0)

2 · Bottom-up: mark good indices from the end

O(n²) time · O(n) space

The same idea without recursion. A list good starts with only the last index marked true; then, from the second-to-last index back to 0, an index becomes good if any index it can land on is already good. any() stops at the first hit. Every index to the right is final by the time it is read, so the answer is good[0].

def can_jump(nums: list[int]) -> bool:
    last = len(nums) - 1
    good = [False] * len(nums)
    good[last] = True
    for i in range(last - 1, -1, -1):
        furthest = min(i + nums[i], last)
        good[i] = any(good[j] for j in range(i + 1, furthest + 1))
    return good[0]

3 · Greedy: track the furthest reachable index

O(n) time · O(1) space

recommended

You never need to know which path you take, only how far the jumps seen so far can carry you. Keep reach, the furthest index reachable. Walking left to right, an index beyond reach means you are stuck; otherwise extend reach with i + n, and return as soon as it covers the last index. One pass, two integers.

def can_jump(nums: list[int]) -> bool:
    reach = 0
    for i, n in enumerate(nums):
        if i > reach:
            return False
        reach = max(reach, i + n)
        if reach >= len(nums) - 1:
            return True
    return True

3 reference approaches in JavaScript, from brute force to the one to reach for. Compare them with yours.

1 · Top-down: recursion with a memo per index

O(n²) time · O(n) space

An inner good(i) answers whether index i can reach the end, trying the furthest landing spot first. A Uint8Array memo stores 0 for unknown, 1 for good and 2 for stuck, so each index is solved once. Math.min caps the furthest spot at the last index, so a value of 100,000 never runs past the array.

function canJump(nums) {
  const last = nums.length - 1;
  const memo = new Uint8Array(nums.length); // 0 unknown, 1 good, 2 stuck

  function good(i) {
    if (i === last) return true;
    if (memo[i] !== 0) return memo[i] === 1;
    const furthest = Math.min(i + nums[i], last);
    for (let j = furthest; j > i; j--) {
      if (good(j)) {
        memo[i] = 1;
        return true;
      }
    }
    memo[i] = 2;
    return false;
  }

  return good(0);
}

2 · Bottom-up: mark good indices from the end

O(n²) time · O(n) space

The same recurrence filled from the right with no recursion. good starts all false except the last index; each earlier index looks at the indices it can land on and becomes good at the first good one. By the time index i is filled, everything to its right is final, so the answer is good[0].

function canJump(nums) {
  const last = nums.length - 1;
  const good = new Array(nums.length).fill(false);
  good[last] = true;
  for (let i = last - 1; i >= 0; i--) {
    const furthest = Math.min(i + nums[i], last);
    for (let j = i + 1; j <= furthest; j++) {
      if (good[j]) {
        good[i] = true;
        break;
      }
    }
  }
  return good[0];
}

3 · Greedy: track the furthest reachable index

O(n) time · O(1) space

recommended

Keep reach, the furthest index any jump so far can land on. Walking left to right, an index past reach means you are stuck; otherwise stretch reach to i + nums[i] and stop as soon as it covers the last index. One loop, two numbers.

function canJump(nums) {
  let reach = 0;
  for (let i = 0; i < nums.length; i++) {
    if (i > reach) return false;
    reach = Math.max(reach, i + nums[i]);
    if (reach >= nums.length - 1) return true;
  }
  return true;
}

3 reference approaches in TypeScript, from brute force to the one to reach for. Compare them with yours.

1 · Top-down: recursion with a memo per index

O(n²) time · O(n) space

An inner good(i: number): boolean answers whether index i can reach the end, trying the furthest landing spot first. A Map<number, boolean> remembers each answer, so no index is solved twice, and Math.min keeps the furthest spot inside the array.

function canJump(nums: number[]): boolean {
  const last = nums.length - 1;
  const memo = new Map<number, boolean>();

  function good(i: number): boolean {
    if (i === last) return true;
    const known = memo.get(i);
    if (known !== undefined) return known;
    const furthest = Math.min(i + nums[i], last);
    let result = false;
    for (let j = furthest; j > i; j--) {
      if (good(j)) {
        result = true;
        break;
      }
    }
    memo.set(i, result);
    return result;
  }

  return good(0);
}

2 · Bottom-up: mark good indices from the end

O(n²) time · O(n) space

The same recurrence filled from the right. A boolean[] starts with only the last index marked; each earlier index becomes good at the first good index it can land on. Every index to the right is final when it is read, so the answer is good[0].

function canJump(nums: number[]): boolean {
  const last = nums.length - 1;
  const good: boolean[] = new Array(nums.length).fill(false);
  good[last] = true;
  for (let i = last - 1; i >= 0; i--) {
    const furthest = Math.min(i + nums[i], last);
    for (let j = i + 1; j <= furthest; j++) {
      if (good[j]) {
        good[i] = true;
        break;
      }
    }
  }
  return good[0];
}

3 · Greedy: track the furthest reachable index

O(n) time · O(1) space

recommended

Track reach, the furthest index the jumps so far can land on. An index beyond it means you are stuck; otherwise stretch it to i + nums[i] and return true once it covers the last index. Linear time, constant space.

function canJump(nums: number[]): boolean {
  let reach = 0;
  for (let i = 0; i < nums.length; i++) {
    if (i > reach) return false;
    reach = Math.max(reach, i + nums[i]);
    if (reach >= nums.length - 1) return true;
  }
  return true;
}

3 reference approaches in Java, from brute force to the one to reach for. Compare them with yours.

1 · Top-down: recursion with a memo per index

O(n²) time · O(n) space

A helper good(nums, i, memo) answers whether index i can reach the end, trying the furthest landing spot first. The memo is a byte[] with 0 for unknown, 1 for good and 2 for stuck, so there is no boxing and each index is solved once. Math.min caps the furthest spot at the last index.

import java.util.*;

public class Main {
    static boolean canJump(int[] nums) {
        byte[] memo = new byte[nums.length]; // 0 unknown, 1 good, 2 stuck
        return good(nums, 0, memo);
    }

    static boolean good(int[] nums, int i, byte[] memo) {
        int last = nums.length - 1;
        if (i == last) return true;
        if (memo[i] != 0) return memo[i] == 1;
        int furthest = Math.min(i + nums[i], last);
        for (int j = furthest; j > i; j--) {
            if (good(nums, j, memo)) {
                memo[i] = 1;
                return true;
            }
        }
        memo[i] = 2;
        return false;
    }
}

2 · Bottom-up: mark good indices from the end

O(n²) time · O(n) space

The same recurrence without recursion. A boolean[] starts all false, which Java guarantees for a new array; the last index is set to true, and from right to left each index becomes good at the first good index it can land on. The answer is good[0].

import java.util.*;

public class Main {
    static boolean canJump(int[] nums) {
        int last = nums.length - 1;
        boolean[] good = new boolean[nums.length];
        good[last] = true;
        for (int i = last - 1; i >= 0; i--) {
            int furthest = Math.min(i + nums[i], last);
            for (int j = i + 1; j <= furthest; j++) {
                if (good[j]) {
                    good[i] = true;
                    break;
                }
            }
        }
        return good[0];
    }
}

3 · Greedy: track the furthest reachable index

O(n) time · O(1) space

recommended

Keep reach, the furthest index the jumps so far can land on. An index beyond it means you are stuck; otherwise Math.max stretches it to i + nums[i], and the method returns as soon as it covers the last index. One loop, two ints.

import java.util.*;

public class Main {
    static boolean canJump(int[] nums) {
        int reach = 0;
        for (int i = 0; i < nums.length; i++) {
            if (i > reach) return false;
            reach = Math.max(reach, i + nums[i]);
            if (reach >= nums.length - 1) return true;
        }
        return true;
    }
}

3 reference approaches in Go, from brute force to the one to reach for. Compare them with yours.

1 · Top-down: recursion with a memo per index

O(n²) time · O(n) space

A closure good answers whether index i can reach the end, trying the furthest landing spot first. Go needs the var good func(int) bool declaration before the assignment so the closure can call itself. The memo is a []int8 with 0 for unknown, 1 for good and 2 for stuck, and the built-in min (Go 1.21) keeps the furthest spot inside the slice.

package main

func canJump(nums []int) bool {
	last := len(nums) - 1
	memo := make([]int8, len(nums)) // 0 unknown, 1 good, 2 stuck

	var good func(i int) bool
	good = func(i int) bool {
		if i == last {
			return true
		}
		if memo[i] != 0 {
			return memo[i] == 1
		}
		furthest := min(i+nums[i], last)
		for j := furthest; j > i; j-- {
			if good(j) {
				memo[i] = 1
				return true
			}
		}
		memo[i] = 2
		return false
	}

	return good(0)
}

2 · Bottom-up: mark good indices from the end

O(n²) time · O(n) space

The same recurrence filled from the right. make([]bool, n) starts every entry false; the last index is set to true, and each earlier index becomes good at the first good index it can land on. The answer is good[0].

package main

func canJump(nums []int) bool {
	last := len(nums) - 1
	good := make([]bool, len(nums))
	good[last] = true
	for i := last - 1; i >= 0; i-- {
		furthest := min(i+nums[i], last)
		for j := i + 1; j <= furthest; j++ {
			if good[j] {
				good[i] = true
				break
			}
		}
	}
	return good[0]
}

3 · Greedy: track the furthest reachable index

O(n) time · O(1) space

recommended

for i, n := range nums walks the slice once while reach holds the furthest index the jumps so far can land on. An index beyond it means you are stuck; otherwise max stretches it to i+n, and the function returns as soon as it covers the last index.

package main

func canJump(nums []int) bool {
	reach := 0
	for i, n := range nums {
		if i > reach {
			return false
		}
		reach = max(reach, i+n)
		if reach >= len(nums)-1 {
			return true
		}
	}
	return true
}

3 reference approaches in C#, from brute force to the one to reach for. Compare them with yours.

1 · Top-down: recursion with a memo per index

O(n²) time · O(n) space

A helper Good answers whether index i can reach the end, trying the furthest landing spot first. The memo is a bool?[]: null means not computed yet, so a stored false is a real answer. Math.Min caps the furthest spot at the last index.

using System;
using System.Collections.Generic;
using System.Linq;

public class Solution
{
    public static bool CanJump(int[] nums)
    {
        var memo = new bool?[nums.Length];
        return Good(nums, 0, memo);
    }

    private static bool Good(int[] nums, int i, bool?[] memo)
    {
        int last = nums.Length - 1;
        if (i == last) return true;
        if (memo[i].HasValue) return memo[i].Value;
        int furthest = Math.Min(i + nums[i], last);
        bool result = false;
        for (int j = furthest; j > i; j--)
        {
            if (Good(nums, j, memo))
            {
                result = true;
                break;
            }
        }
        memo[i] = result;
        return result;
    }
}

2 · Bottom-up: mark good indices from the end

O(n²) time · O(n) space

The same recurrence without recursion. A new bool[] is all false; the last index is set to true, and from right to left each index becomes good at the first good index it can land on. The answer is good[0].

using System;
using System.Collections.Generic;
using System.Linq;

public class Solution
{
    public static bool CanJump(int[] nums)
    {
        int last = nums.Length - 1;
        var good = new bool[nums.Length];
        good[last] = true;
        for (int i = last - 1; i >= 0; i--)
        {
            int furthest = Math.Min(i + nums[i], last);
            for (int j = i + 1; j <= furthest; j++)
            {
                if (good[j])
                {
                    good[i] = true;
                    break;
                }
            }
        }
        return good[0];
    }
}

3 · Greedy: track the furthest reachable index

O(n) time · O(1) space

recommended

Keep reach, the furthest index the jumps so far can land on. An index beyond it means you are stuck; otherwise Math.Max stretches it to i + nums[i], and the method returns once it covers the last index. Linear time, constant space.

using System;
using System.Collections.Generic;
using System.Linq;

public class Solution
{
    public static bool CanJump(int[] nums)
    {
        int reach = 0;
        for (int i = 0; i < nums.Length; i++)
        {
            if (i > reach) return false;
            reach = Math.Max(reach, i + nums[i]);
            if (reach >= nums.Length - 1) return true;
        }
        return true;
    }
}

3 reference approaches in C++, from brute force to the one to reach for. Compare them with yours.

1 · Top-down: recursion with a memo per index

O(n²) time · O(n) space

A private member good answers whether index i can reach the end, trying the furthest landing spot first. The memo is a vector<signed char> with 0 for unknown, 1 for good and 2 for stuck, passed by reference so every call shares it. min keeps the furthest spot inside the vector.

#include <algorithm>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;

class Solution {
public:
    bool canJump(vector<int>& nums) {
        vector<signed char> memo(nums.size(), 0); // 0 unknown, 1 good, 2 stuck
        return good(nums, 0, memo);
    }

private:
    bool good(const vector<int>& nums, int i, vector<signed char>& memo) {
        int last = (int)nums.size() - 1;
        if (i == last) return true;
        if (memo[i] != 0) return memo[i] == 1;
        int furthest = min(i + nums[i], last);
        for (int j = furthest; j > i; j--) {
            if (good(nums, j, memo)) {
                memo[i] = 1;
                return true;
            }
        }
        memo[i] = 2;
        return false;
    }
};

2 · Bottom-up: mark good indices from the end

O(n²) time · O(n) space

The same recurrence without recursion. good starts all false except the last index; from right to left each index becomes good at the first good index it can land on, and the answer is good[0].

#include <algorithm>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int last = (int)nums.size() - 1;
        vector<bool> good(nums.size(), false);
        good[last] = true;
        for (int i = last - 1; i >= 0; i--) {
            int furthest = min(i + nums[i], last);
            for (int j = i + 1; j <= furthest; j++) {
                if (good[j]) {
                    good[i] = true;
                    break;
                }
            }
        }
        return good[0];
    }
};

3 · Greedy: track the furthest reachable index

O(n) time · O(1) space

recommended

Keep reach, the furthest index the jumps so far can land on. An index beyond it means you are stuck; otherwise max stretches it to i + nums[i], and the method returns once it covers the last index. One pass, no extra memory.

#include <algorithm>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int n = (int)nums.size();
        int reach = 0;
        for (int i = 0; i < n; i++) {
            if (i > reach) return false;
            reach = max(reach, i + nums[i]);
            if (reach >= n - 1) return true;
        }
        return true;
    }
};

3 reference approaches in C, from brute force to the one to reach for. Compare them with yours.

1 · Top-down: recursion with a memo per index

O(n²) time · O(n) space

A static helper good answers whether index i can reach the end, trying the furthest landing spot first. The memo is a calloc'ed char array, so every entry starts at 0 for unknown; 1 means good and 2 means stuck, so a dead end is never explored twice. The furthest spot is capped at the last index, and the memo is freed before returning.

#include <stdbool.h>
#include <stdlib.h>
#include <string.h>

static bool good(int* nums, int last, int i, char* memo) {
    if (i == last) return true;
    if (memo[i]) return memo[i] == 1;
    int furthest = i + nums[i] < last ? i + nums[i] : last;
    for (int j = furthest; j > i; j--) {
        if (good(nums, last, j, memo)) {
            memo[i] = 1;
            return true;
        }
    }
    memo[i] = 2;
    return false;
}

bool canJump(int* nums, int numsSize) {
    char* memo = calloc(numsSize, 1); // 0 unknown, 1 good, 2 stuck
    bool result = good(nums, numsSize - 1, 0, memo);
    free(memo);
    return result;
}

2 · Bottom-up: mark good indices from the end

O(n²) time · O(n) space

The same recurrence without recursion. A bool table from calloc starts all false; the last index is set to true, and from right to left each index becomes good at the first good index it can land on. The answer is read from good[0] before the table is freed.

#include <stdbool.h>
#include <stdlib.h>
#include <string.h>

bool canJump(int* nums, int numsSize) {
    int last = numsSize - 1;
    bool* good = calloc(numsSize, sizeof *good);
    good[last] = true;
    for (int i = last - 1; i >= 0; i--) {
        int furthest = i + nums[i] < last ? i + nums[i] : last;
        for (int j = i + 1; j <= furthest; j++) {
            if (good[j]) {
                good[i] = true;
                break;
            }
        }
    }
    bool result = good[0];
    free(good);
    return result;
}

3 · Greedy: track the furthest reachable index

O(n) time · O(1) space

recommended

Keep reach, the furthest index the jumps so far can land on. An index beyond it means you are stuck; otherwise it grows to i + nums[i], and the function returns as soon as it covers the last index. One loop, two ints and no allocation.

#include <stdbool.h>
#include <stdlib.h>
#include <string.h>

bool canJump(int* nums, int numsSize) {
    int reach = 0;
    for (int i = 0; i < numsSize; i++) {
        if (i > reach) return false;
        if (i + nums[i] > reach) reach = i + nums[i];
        if (reach >= numsSize - 1) return true;
    }
    return true;
}

3 reference approaches in Kotlin, from brute force to the one to reach for. Compare them with yours.

1 · Top-down: recursion with a memo per index

O(n²) time · O(n) space

A local function good(i) answers whether index i can reach the end. It walks furthest downTo i + 1 with any, which stops at the first good landing spot. The memo is arrayOfNulls<Boolean>: null is unknown and false remembers a dead end, so no index is solved twice.

class Solution {
    fun canJump(nums: IntArray): Boolean {
        val last = nums.lastIndex
        val memo = arrayOfNulls<Boolean>(nums.size)

        fun good(i: Int): Boolean {
            if (i == last) return true
            memo[i]?.let { return it }
            val furthest = minOf(i + nums[i], last)
            val result = (furthest downTo i + 1).any { good(it) }
            memo[i] = result
            return result
        }

        return good(0)
    }
}

2 · Bottom-up: mark good indices from the end

O(n²) time · O(n) space

The same recurrence without recursion. A BooleanArray starts all false; the last index is set to true, and from right to left an index is good if any index in i + 1..furthest is. The answer is good[0].

class Solution {
    fun canJump(nums: IntArray): Boolean {
        val last = nums.lastIndex
        val good = BooleanArray(nums.size)
        good[last] = true
        for (i in last - 1 downTo 0) {
            val furthest = minOf(i + nums[i], last)
            good[i] = (i + 1..furthest).any { good[it] }
        }
        return good[0]
    }
}

3 · Greedy: track the furthest reachable index

O(n) time · O(1) space

recommended

Keep reach, the furthest index the jumps so far can land on. Looping with withIndex(), an index beyond it means you are stuck; otherwise maxOf stretches it, and the function returns as soon as it covers the last index.

class Solution {
    fun canJump(nums: IntArray): Boolean {
        var reach = 0
        for ((i, n) in nums.withIndex()) {
            if (i > reach) return false
            reach = maxOf(reach, i + n)
            if (reach >= nums.lastIndex) return true
        }
        return true
    }
}

3 reference approaches in Rust, from brute force to the one to reach for. Compare them with yours.

1 · Top-down: recursion with a memo per index

O(n²) time · O(n) space

An associated function good answers whether index i can reach the end. The memo is a Vec<Option<bool>>: None is unknown and Some(false) remembers a dead end, so no index is solved twice. It tries the landing spots from the furthest down with .rev().any(…), which stops at the first good one; the furthest spot is capped with .min(last).

impl Solution {
    pub fn can_jump(nums: Vec<i32>) -> bool {
        let mut memo = vec![None; nums.len()];
        Self::good(&nums, 0, &mut memo)
    }

    fn good(nums: &[i32], i: usize, memo: &mut [Option<bool>]) -> bool {
        let last = nums.len() - 1;
        if i == last {
            return true;
        }
        if let Some(known) = memo[i] {
            return known;
        }
        let furthest = (i + nums[i] as usize).min(last);
        let result = (i + 1..=furthest).rev().any(|j| Self::good(nums, j, memo));
        memo[i] = Some(result);
        result
    }
}

2 · Bottom-up: mark good indices from the end

O(n²) time · O(n) space

The same recurrence without recursion. A vec![false; n] table gets true at the last index; then, right to left, an index is good if the slice of indices it can land on contains a true. Slicing with i + 1..=furthest keeps the inner loop free of bounds checks per element.

impl Solution {
    pub fn can_jump(nums: Vec<i32>) -> bool {
        let last = nums.len() - 1;
        let mut good = vec![false; nums.len()];
        good[last] = true;
        for i in (0..last).rev() {
            let furthest = (i + nums[i] as usize).min(last);
            good[i] = good[i + 1..=furthest].contains(&true);
        }
        good[0]
    }
}

3 · Greedy: track the furthest reachable index

O(n) time · O(1) space

recommended

Keep reach, the furthest index the jumps so far can land on, as a usize. Walking with enumerate(), an index beyond it means you are stuck; otherwise reach.max(i + n as usize) stretches it, and the function returns as soon as it covers the last index.

impl Solution {
    pub fn can_jump(nums: Vec<i32>) -> bool {
        let last = nums.len() - 1;
        let mut reach = 0usize;
        for (i, &n) in nums.iter().enumerate() {
            if i > reach {
                return false;
            }
            reach = reach.max(i + n as usize);
            if reach >= last {
                return true;
            }
        }
        true
    }
}

3 reference approaches in Swift, from brute force to the one to reach for. Compare them with yours.

1 · Top-down: recursion with a memo per index

O(n²) time · O(n) space

A nested function good(_:) answers whether index i can reach the end, trying landing spots from the furthest down with stride(from:to:by: -1). The memo is a [Bool?]: nil is unknown and false remembers a dead end, so no index is solved twice. The furthest spot is capped with min.

class Solution {
    func canJump(_ nums: [Int]) -> Bool {
        let last = nums.count - 1
        var memo = [Bool?](repeating: nil, count: nums.count)

        func good(_ i: Int) -> Bool {
            if i == last { return true }
            if let known = memo[i] { return known }
            let furthest = min(i + nums[i], last)
            var result = false
            for j in stride(from: furthest, to: i, by: -1) {
                if good(j) {
                    result = true
                    break
                }
            }
            memo[i] = result
            return result
        }

        return good(0)
    }
}

2 · Bottom-up: mark good indices from the end

O(n²) time · O(n) space

The same recurrence without recursion. A [Bool] table starts all false with true at the last index; from right to left an index is good if the slice good[(i + 1)..<(furthest + 1)] contains a true. The half-open range is simply empty at an index holding 0, where a closed range would trap, and a slice is a view, so nothing is copied.

class Solution {
    func canJump(_ nums: [Int]) -> Bool {
        let last = nums.count - 1
        var good = [Bool](repeating: false, count: nums.count)
        good[last] = true
        for i in stride(from: last - 1, through: 0, by: -1) {
            let furthest = min(i + nums[i], last)
            good[i] = good[(i + 1)..<(furthest + 1)].contains(true)
        }
        return good[0]
    }
}

3 · Greedy: track the furthest reachable index

O(n) time · O(1) space

recommended

Keep reach, the furthest index the jumps so far can land on. Looping over nums.enumerated(), an index beyond it means you are stuck; otherwise max stretches it, and the method returns as soon as it covers the last index.

class Solution {
    func canJump(_ nums: [Int]) -> Bool {
        var reach = 0
        for (i, n) in nums.enumerated() {
            if i > reach { return false }
            reach = max(reach, i + n)
            if reach >= nums.count - 1 { return true }
        }
        return true
    }
}

3 reference approaches in PHP, from brute force to the one to reach for. Compare them with yours.

1 · Top-down: recursion with a memo per index

O(n²) time · O(n) space

A helper method good() answers whether index $i can reach the end, trying the furthest landing spot first. The memo is passed by reference as array &$memo, so every call shares one array; an index missing from it is unknown, and a stored false remembers a dead end so it is never explored twice.

<?php

class Solution {
    /**
     * @param int[] $nums
     * @return bool
     */
    function canJump(array $nums): bool {
        $memo = [];
        return $this->good($nums, 0, count($nums) - 1, $memo);
    }

    private function good(array $nums, int $i, int $last, array &$memo): bool {
        if ($i === $last) {
            return true;
        }
        if (isset($memo[$i])) {
            return $memo[$i];
        }
        $furthest = min($i + $nums[$i], $last);
        for ($j = $furthest; $j > $i; $j--) {
            if ($this->good($nums, $j, $last, $memo)) {
                return $memo[$i] = true;
            }
        }
        return $memo[$i] = false;
    }
}

2 · Bottom-up: mark good indices from the end

O(n²) time · O(n) space

The same recurrence without recursion. array_fill builds a table of false with true at the last index; from right to left an index becomes good at the first good index it can land on, and the inner loop breaks there. The answer is $good[0].

<?php

class Solution {
    /**
     * @param int[] $nums
     * @return bool
     */
    function canJump(array $nums): bool {
        $last = count($nums) - 1;
        $good = array_fill(0, $last + 1, false);
        $good[$last] = true;
        for ($i = $last - 1; $i >= 0; $i--) {
            $furthest = min($i + $nums[$i], $last);
            for ($j = $i + 1; $j <= $furthest; $j++) {
                if ($good[$j]) {
                    $good[$i] = true;
                    break;
                }
            }
        }
        return $good[0];
    }
}

3 · Greedy: track the furthest reachable index

O(n) time · O(1) space

recommended

Keep $reach, the furthest index the jumps so far can land on. In a foreach ($nums as $i => $n), an index beyond it means you are stuck; otherwise max stretches it, and the method returns as soon as it covers the last index.

<?php

class Solution {
    /**
     * @param int[] $nums
     * @return bool
     */
    function canJump(array $nums): bool {
        $last = count($nums) - 1;
        $reach = 0;
        foreach ($nums as $i => $n) {
            if ($i > $reach) {
                return false;
            }
            $reach = max($reach, $i + $n);
            if ($reach >= $last) {
                return true;
            }
        }
        return true;
    }
}

3 reference approaches in Ruby, from brute force to the one to reach for. Compare them with yours.

1 · Top-down: recursion with a memo per index

O(n²) time · O(n) space

A helper good? answers whether index i can reach the end, trying the landing spots from the furthest down and stopping at the first good one. The memo is an Array of nils: nil is unknown and false remembers a dead end, so no index is solved twice. The inner loop is a plain while: a downto(…).any? block would add several stack frames per level, and a path of 2,000 single steps then overflows Ruby's stack.

# @param {Integer[]} nums
# @return {Boolean}
def can_jump(nums)
  good?(nums, 0, nums.length - 1, Array.new(nums.length))
end

def good?(nums, i, last, memo)
  return true if i == last
  return memo[i] unless memo[i].nil?

  j = [i + nums[i], last].min
  while j > i
    return memo[i] = true if good?(nums, j, last, memo)

    j -= 1
  end
  memo[i] = false
end

2 · Bottom-up: mark good indices from the end

O(n²) time · O(n) space

The same recurrence without recursion. Array.new(n, false) gets true at the last index; from right to left an index is good if any? index in (i + 1)..furthest already is. The answer is good[0].

# @param {Integer[]} nums
# @return {Boolean}
def can_jump(nums)
  last = nums.length - 1
  good = Array.new(nums.length, false)
  good[last] = true
  (last - 1).downto(0) do |i|
    furthest = [i + nums[i], last].min
    good[i] = ((i + 1)..furthest).any? { |j| good[j] }
  end
  good[0]
end

3 · Greedy: track the furthest reachable index

O(n) time · O(1) space

recommended

Keep reach, the furthest index the jumps so far can land on. In each_with_index, an index beyond it means you are stuck; otherwise it grows to i + n, and the method returns as soon as it covers the last index. A return inside the block returns from can_jump itself.

# @param {Integer[]} nums
# @return {Boolean}
def can_jump(nums)
  reach = 0
  nums.each_with_index do |n, i|
    return false if i > reach

    reach = [reach, i + n].max
    return true if reach >= nums.length - 1
  end
  true
end

3 reference approaches in Dart, from brute force to the one to reach for. Compare them with yours.

1 · Top-down: recursion with a memo per index

O(n²) time · O(n) space

A private method _good answers whether index i can reach the end, trying the furthest landing spot first. The memo is a List<bool?>: null is unknown and false remembers a dead end, so no index is solved twice. The furthest spot is capped with min from dart:math.

import 'dart:math';

class Solution {
  bool canJump(List<int> nums) {
    final memo = List<bool?>.filled(nums.length, null);
    return _good(nums, 0, memo);
  }

  bool _good(List<int> nums, int i, List<bool?> memo) {
    final last = nums.length - 1;
    if (i == last) return true;
    final known = memo[i];
    if (known != null) return known;
    final furthest = min(i + nums[i], last);
    for (var j = furthest; j > i; j--) {
      if (_good(nums, j, memo)) return memo[i] = true;
    }
    return memo[i] = false;
  }
}

2 · Bottom-up: mark good indices from the end

O(n²) time · O(n) space

The same recurrence without recursion. List.filled(n, false) gets true at the last index; from right to left an index is good if getRange(i + 1, furthest + 1) contains a true. getRange is a lazy view, so no sublist is copied.

import 'dart:math';

class Solution {
  bool canJump(List<int> nums) {
    final last = nums.length - 1;
    final good = List<bool>.filled(nums.length, false);
    good[last] = true;
    for (var i = last - 1; i >= 0; i--) {
      final furthest = min(i + nums[i], last);
      good[i] = good.getRange(i + 1, furthest + 1).contains(true);
    }
    return good[0];
  }
}

3 · Greedy: track the furthest reachable index

O(n) time · O(1) space

recommended

Keep reach, the furthest index the jumps so far can land on. An index beyond it means you are stuck; otherwise max stretches it to i + nums[i], and the method returns as soon as it covers the last index.

import 'dart:math';

class Solution {
  bool canJump(List<int> nums) {
    var reach = 0;
    for (var i = 0; i < nums.length; i++) {
      if (i > reach) return false;
      reach = max(reach, i + nums[i]);
      if (reach >= nums.length - 1) return true;
    }
    return true;
  }
}

3 reference approaches in Scala, from brute force to the one to reach for. Compare them with yours.

1 · Top-down: recursion with a memo per index

O(n²) time · O(n) space

A local def good(i) answers whether index i can reach the end. The memo is an Array[Option[Boolean]] matched with Some / None, so a remembered dead end is never explored twice. The landing spots are tried from the furthest down in a while loop that stops at the first good one, with no return inside a closure.

object Solution {
  def canJump(nums: Array[Int]): Boolean = {
    val last = nums.length - 1
    val memo = Array.fill[Option[Boolean]](nums.length)(None)

    def good(i: Int): Boolean =
      if (i == last) true
      else
        memo(i) match {
          case Some(known) => known
          case None =>
            var j = math.min(i + nums(i), last)
            var found = false
            while (!found && j > i) {
              found = good(j)
              j -= 1
            }
            memo(i) = Some(found)
            found
        }

    good(0)
  }
}

2 · Bottom-up: mark good indices from the end

O(n²) time · O(n) space

The same recurrence without recursion. A new Array[Boolean](n) starts all false; the last index is set to true, and from right to left an index is good if any index in i + 1 to furthest already is. exists stops at the first hit.

object Solution {
  def canJump(nums: Array[Int]): Boolean = {
    val last = nums.length - 1
    val good = new Array[Boolean](nums.length)
    good(last) = true
    for (i <- last - 1 to 0 by -1) {
      val furthest = math.min(i + nums(i), last)
      good(i) = (i + 1 to furthest).exists(j => good(j))
    }
    good(0)
  }
}

3 · Greedy: track the furthest reachable index

O(n) time · O(1) space

recommended

Keep reach, the furthest index the jumps so far can land on. The method body is a boundary, so break(false) leaves the loop when an index lies beyond reach and break(true) as soon as it covers the last index.

import scala.util.boundary, boundary.break

object Solution {
  def canJump(nums: Array[Int]): Boolean = boundary {
    var reach = 0
    for (i <- nums.indices) {
      if (i > reach) break(false)
      reach = math.max(reach, i + nums(i))
      if (reach >= nums.length - 1) break(true)
    }
    true
  }
}

FAQ for PHP

Why is the memo passed by reference?

PHP arrays are passed by value (copy on write), so without the & each recursive call would write into its own copy and the answers would never reach the caller. array &$memo makes every call share one array. Passing $nums by value is fine because it is never written, so it is never copied.

Why does isset work for a memo that stores false?

isset is only false for a missing key or a null value, so a stored false still counts as set and is returned. That gives the three states the memo needs: missing for unknown, true for good and false for stuck. array_key_exists would work too, but isset is faster.

Can PHP recurse 2,000 levels deep?

Yes: PHP has no recursion limit of its own, and 2,000 frames of good use little memory. A debugger extension such as Xdebug can impose a max_nesting_level, and very deep chains could exhaust memory_limit. The bottom-up and greedy versions avoid recursion.

What does return $memo[$i] = true mean?

An assignment in PHP is an expression whose value is the assigned value, so return $memo[$i] = true; stores the answer and returns it in one statement. It is the same as writing $memo[$i] = true; followed by return true;.

Why is the greedy loop correct without trying paths?

The reachable indices form one block from 0 to $reach, because a jump can always be shorter than its maximum: reaching index k means every earlier index is reachable too. Each step can only push the end of that block forward, so one integer describes everything.

Keep going

Rotate a Matrix32 / 40 · Matrix · Medium

Try Jump Game in Python (Jump Game in Python), JavaScript (Jump Game in JavaScript), TypeScript (Jump Game in TypeScript), Java (Jump Game in Java), Go (Jump Game in Go), C# (Jump Game in C#), C++ (Jump Game in C++), C (Jump Game in C), Kotlin (Jump Game in Kotlin), Rust (Jump Game in Rust), Swift (Jump Game in Swift), Ruby (Jump Game in Ruby), Dart (Jump Game in Dart) or Scala (Jump Game in Scala) instead.

can_jump.php

PHP 8.5

Not run yet

+ 8 hidden

Input

nums = [2, 0, 3, 0, 1]

Expected

true

Jump 2 from index 0 to index 2, over the 0, then 2 more from index 2 (which allows up to 3) to the last index, 4.