Greedy Algorithm to Reach the Last Index of the Array


Given an array of non-negative integers, you are initially positioned at the first index of the array. Each element in the array represents your maximum jump length at that position. Determine if you are able to reach the last index.

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

Example 2:
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.

Simulation

You can simulate the jumping using recursion easily, however, this approach does not give you a ACCEPTED code, in fact, it will give you a Time Limit Exceeded error when input test cases are complex.

The idea is to jump as far as you can. If you can reach the end, then immediately return true, otherwise, when all possibilities are tested, it returns false. The recursion is time consuming and not very efficient. But this is another way of looking at this problem.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    bool jump(int A[], int p, int n) {
        if (p == n - 1) return true; // reaching the end
        for (int i = p + 1; i <= p + A[p]; i ++) {
            if (jump(A, i, n)) return true; // we can jump to the end.
        }
        return false;
    }
 
    bool canJump(int A[], int n) {
        return jump(A, 0, n); // jump from the beginning
    }
};
class Solution {
public:
    bool jump(int A[], int p, int n) {
        if (p == n - 1) return true; // reaching the end
        for (int i = p + 1; i <= p + A[p]; i ++) {
            if (jump(A, i, n)) return true; // we can jump to the end.
        }
        return false;
    }

    bool canJump(int A[], int n) {
        return jump(A, 0, n); // jump from the beginning
    }
};

Greedy Algorithm

The O(n) solution is similar. We use a variable to record the maximum we can reach. And, we update the current position and this max-reach variable every time. At the end, we check if we are reaching the end.

1
2
3
4
5
6
7
8
9
class Solution {
public:
    bool canJump(int A[], int n) {
        int i = 0; // current position
        for (int reach = 0; i < n && i <= reach; ++i)
            reach = max(i + A[i], reach); // update max reach
        return i == n;  
    }
};
class Solution {
public:
    bool canJump(int A[], int n) {
        int i = 0; // current position
        for (int reach = 0; i < n && i <= reach; ++i)
            reach = max(i + A[i], reach); // update max reach
        return i == n;  
    }
};

The Greedy algorithm can also be written slightly differently:

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    bool canJump(vector<int>& nums) {
        int best = 0, cur = 0;
        for (int i = 0; i < nums.size(); ++ i) {
            best = max(best, i + nums[i]);
            if (cur == i) {
                cur = best;
            }
        }
        return cur >= nums.size() - 1;
    }
};
class Solution {
public:
    bool canJump(vector<int>& nums) {
        int best = 0, cur = 0;
        for (int i = 0; i < nums.size(); ++ i) {
            best = max(best, i + nums[i]);
            if (cur == i) {
                cur = best;
            }
        }
        return cur >= nums.size() - 1;
    }
};

You see, how simple this is. Less is more!

Featured Comments

Very nice excercise(took me like 10 minutes to solve using recursion xD) however i’m kinda confused because in recursive solution they used >= last index but in non recursive solution they used == last index so it’s kinda confusing if reaching the end is reaching exactly last index or also over last index.

See also other variants of jump game solutions/algorithms:

–EOF (The Ultimate Computing & Technology Blog) —

GD Star Rating
loading...
648 words
Last Post: How to Suppress Ads when WordPress Users are Logged in?
Next Post: Performance Testing the HDD/SSD/NVme Hard Disk speed on VPS/Dedicated Server

The Permanent URL is: Greedy Algorithm to Reach the Last Index of the Array

Leave a Reply