Is he being greedy?

Admin 1
Viewed 399

I am solving a question from LeetCode.com:

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. 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 that the following is using 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:

  1. What is the intuition behind using a greedy algorithm for this?
  2. How is the above solution a greedy algorithm?

I thought this to be solvable by Dynamic Programming. I understand that questions solvable by DP can be solved by greedy method, but what was the intuition behind this particular one that made it more sense to solve by the greedy approach?

This SO question highlights this difference to some extent. I understand this might be a bit more, but if possible, could some one please answer this question in this context? I would highly appreciate that.

Thank you.

Edit: I think one of the reasons of my confusion is over the input [3,3,1,0,4]. As per the greedy paradigm, when i=0 wouldn't we take a jump of size 3 (A[0]) in order to greedily reach the output? But doing this would in fact be incorrect.

greedy dynamic-programming algorithm c++
1 Answers

According to Wikipedia:

A greedy algorithm is an algorithmic paradigm that follows the problem solving heuristic of making the 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 algorithm paradigm greedy.

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

Since in this question, we only care about whether it is possible to reach the last index of the array, we can use a greedy algorithm. A greedy algorithm will select the optimal choice (take the maximum jump) at every step and check at the end whether the maximum index can reach the end.

Say, if we need to find out the jump size at each index to reach the end or need to optimize the number of jumps to reach the end, then the direct use of greedy algorithm won't serve our purpose.

Q2. How is the above solution a greedy algorithm?

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

The analysis provided here may help you.

Edit

Let's talk about the input you mentioned - [3,3,1,0,4].

  • When i=0, algorithm checks what is the maximum index that we can reach from i=0.
  • Then we will move to the next index and check what is the max index we can reach from i=1. Since we moved to i=1, it is guranteed that we can come to index 1 from index 0 (doesn't matter what is the jump size).

Please note, in this problem, we don't care whether we should take a jump of size 3 at i=0 though we know this will not help us to reach the end. What we care about is whether we can reach the end or beyond that end index by taking jumps.

user_53523990
Related