He is greedy?

Question

I solve a question from LeetCode.com :

Given an array of non-negative integers, you are initially located in the first index of the array. Each element of the array represents your maximum jump length at this position. Determine if you can reach the last index. For example: A = [2,3,1,1,4], return true. A = [3,2,1,0,4], return false.

One of the most voted solutions ( here ) says the following takes a greedy approach:

bool canJump(int A[], int n) { int last=n-1,i,j; for(i=n-2;i>=0;i--){ if(i+A[i]>=last)last=i; } return last<=0; } 

I have two questions:

• What is the intuition of using a greedy algorithm for this?
• How is this solution a greedy algorithm?

I thought this could be solved using dynamic programming. I understand that the issues resolved by DP can be solved by the greedy method, but what was the intuition behind this particular one, which made sense to solve the greedy way?

This SO question emphasizes this difference to some extent. I understand that this may be a little more, but if possible, can someone answer this question in this context? I would be very grateful.

Thanks.

Change I think one of the reasons for my confusion is the input [3,3,1,0,4] . According to the greedy paradigm, when i=0 would we not take a jump of size 3 ( A[0] ) to greedily reach the exit? But to do this would actually be wrong.

Answer 1

According to Wikipedia:

A greedy algorithm is an algorithmic paradigm that follows the solution of the heuristic problem, which allows making a locally optimal choice at each stage with the hope of finding a global optimum.

Here I want to draw your attention to the key phrase locally optimal choice at each stage , which makes the algorithmic paradigm greedy.

---

 Q1. What is the intuition behind using a greedy algorithm for this? 

Since in this question we only care about whether the last index of the array can be reached, we can use the greedy algorithm. The greedy algorithm will choose the optimal choice (take the maximum jump) at each step and at the end check if the maximum index reaches.

Say, if we need to find out the size of the transition for each index in order to achieve the goal or if we need to optimize the number of jumps to reach the end, then the direct use of the greedy algorithm will not serve our purpose.

 Q2. How is the above solution a greedy algorithm? 

The if condition in the above code is if(i+A[i]>=last)last=i; makes the algorithm greedy because we take the maximum jump if possible ( i+A[i]>=last ).

The analysis provided here may help you.

---

Edit

Tell us about what you indicated - [3,3,1,0,4] .

• When i=0 , the algorithm checks which maximum index we can reach from i=0 .
• Then we move on to the next index and check what maximum index we can reach from i=1 . Since we moved to i=1 , we guarantee that we can go to index 1 from index 0 (no matter what the size of the transition).

Please note that in this problem we don’t care whether we should jump in size 3 at i=0 , although we know that this will not help us achieve our goal. We care about whether we can reach the end or beyond this end by jumping.