55. Jump Game

Problem Description

You are given an array nums, where each element represents the maximum number of steps you can jump forward from that position. Your goal is to determine if you can reach the last element of the array starting from the first element. You start at the first index of the array, and at each step, you can jump forward to any position within your current element's range. If you can make it to any index that has enough range to reach the end, or if the end is within your reach from where you are, the answer is true. Otherwise, it's false.

Intuition

The key intuition behind the solution is to take a greedy approach. This means we want to make the locally optimal choice at each step in the hope that this will lead to the globally optimal solution. In this case, as we traverse the array, we continuously keep track of the furthest we can reach (mx).

We start at the first index and iterate through the array. For each index, we update mx to be the maximum of its current value or the furthest we can get from this index (which is the current index i plus the jump length nums[i]). As we do this, if we find mx is ever less than i, we cannot reach position i or beyond, which means we cannot reach the last index, and return false. If we can always reach the position we're iterating over, by the end of the iteration, we can reach the end, and we return true.

Learn more about Greedy and Dynamic Programming patterns.

Solution Approach

The solution uses a simple but effective greedy algorithm. The implementation of this solution does not require any complex data structures, relying only on a single integer variable mx which keeps track of the maximum index that can be reached at each step.

The following steps summarize the implementation of the solution:

We initialize a variable mx to 0. mx represents the maximum index that can be reached so far.
We iterate through each index i of the nums array using a for loop. The enumerate function is handy here as it gives us both the index i and the value x at that index.
During each iteration, we first check if mx is less than i. If this is the case, we return false because it indicates that we can't reach the current index (or any index beyond it).
If mx is not less than i, it means we can reach this position, and therefore we update mx to be the maximum of its current value and i + x, where x is the maximum jump length from the current position. The expression max(mx, i + x) efficiently accomplishes this.
After the loop, if we never encountered a situation where mx < i, we have been able to reach or surpass each index, including the last index. Thus, we return true.

The code or mathematical formulas are encapsulated using backticks, for example, mx = max(mx, i + nums[i]).

By always keeping track of the furthest reachable index and bailing out early if we find an unreachable index (mx < i), we ensure an efficient solution with a time complexity that is linear with respect to the length of the nums array.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a small example using the greedy solution approach outlined above. Suppose we are given the following array nums:

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

Our task is to determine if we can reach the last element, which in this case is 4. We will use the steps of the solution to illustrate how we can arrive at the answer:

Initialize mx to 0. This means before we start, the furthest index we can reach is 0.
Start iterating:
- At index 0, the value is 2. We can jump to index 1 or 2. Update mx to max(0, 0 + 2) which is 2.
- Move to index 1, with a value of 3. Now we can reach as far as 1 + 3 = 4, which is the end of the array. Update mx to max(2, 1 + 3) which is 4.
- At this point, we can already reach the last element, so we could stop and return true. Nonetheless, for completeness:
- At index 2, the value is 1. From here, max(4, 2 + 1) is still 4.
- At index 3, the value is 1. From here, max(4, 3 + 1) is still 4.
Throughout the iteration, mx was always greater than or equal to i, so we never returned false.
After the loop, since there were no indices that we could not reach, and we were always able to update mx to reach or go beyond the next index, we can return true.

So, in our example, it is indeed possible to reach the last element starting from the first element following the greedy approach.

Solution Implementation

1from typing import List
2
3class Solution:
4    def canJump(self, nums: List[int]) -> bool:
5        # Initialize the variable `max_reach` which represents the maximum 
6        # index we can reach so far.
7        max_reach = 0
8      
9        # Enumerate through the list, with `index` representing the current
10        # position and `jump_length` the maximum jump length from that position.
11        for index, jump_length in enumerate(nums):
12            # If our current `max_reach` is less than the `index`, we can't
13            # jump to `index` or beyond, hence we return False.
14            if max_reach < index:
15                return False
16          
17            # Update `max_reach` by the farthest we can get from here, which
18            # is either the current `max_reach` or `index + jump_length`.
19            max_reach = max(max_reach, index + jump_length)
20      
21        # If we've gone through all elements without returning False, it means
22        # we can reach the end of the list, so we return True.
23        return True
24

1class Solution {
2    public boolean canJump(int[] nums) {
3        int maxReachable = 0; // Initialize the maximum reachable index to 0
4
5        // Iterate over each index in the array
6        for (int i = 0; i < nums.length; ++i) {
7            // If the current index is greater than the maximum reachable index,
8            // it means we cannot proceed further, so return false.
9            if (maxReachable < i) {
10                return false;
11            }
12
13            // Update the maximum reachable index if the reachable index
14            // from the current position is greater than the previous max.
15            maxReachable = Math.max(maxReachable, i + nums[i]);
16        }
17      
18        // If the loop completes without returning false, it means we can
19        // reach the last index, so return true.
20        return true;
21    }
22}
23

1#include <vector> // Include the necessary header for vector
2using namespace std;
3
4class Solution {
5public:
6    // Function to check if we can jump to the last index of the vector 'nums'
7    bool canJump(vector<int>& nums) {
8        int maxReachable = 0; // Variable to keep track of the maximum reachable index so far
9
10        // Iterate through each element of the vector
11        for (int i = 0; i < nums.size(); ++i) {
12            // If the current index is greater than the maximum reachable index, we can't proceed, return false
13            if (maxReachable < i) {
14                return false;
15            }
16
17            // Update maxReachable to the maximum of the current maxReachable and the current index plus its jump length
18            maxReachable = max(maxReachable, i + nums[i]);
19        }
20      
21        // If we are able to iterate through the entire vector, return true
22        return true;
23    }
24};
25

1// Determines if it is possible to reach the last index of the array
2// nums[i] represents the maximum jump length from that position.
3function canJump(nums: number[]): boolean {
4    let maxReach: number = 0; // Variable to keep track of the maximum reachable index
5    for (let currentIndex = 0; currentIndex < nums.length; ++currentIndex) {
6        // Check if the current index is beyond the maximum reachable index
7        if (maxReach < currentIndex) {
8            // If we cannot reach this index, return false
9            return false;
10        }
11        // Update the maximum reachable index
12        maxReach = Math.max(maxReach, currentIndex + nums[currentIndex]);
13    }
14    // If we can reach beyond the last index, return true
15    return true;
16}
17

Time and Space Complexity

The given Python code aims to determine whether it is possible to jump to the last index of the given list nums. The function canJump works by iterating through each element in the list, calculating the maximum distance that can be reached from the current position, and checking whether that distance is sufficient to continue progressing through the array.

Time Complexity: The time complexity of the code is O(n), where n is the length of the array nums. This is because the function involves a single loop that goes through the array once, making a constant-time check and update at each step.
Space Complexity: The space complexity of the code is O(1). The algorithm uses a fixed amount of additional space (the variable mx), regardless of the input size, so the space used does not grow with the size of the input array.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8

1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12

1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

[30, 20, 10]

[100, 33, 30]

[10, 12, 20]

I don’t know