Is he being greedy?

Question

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:

What is the intuition behind using a greedy algorithm for this?
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.

The first couple of sentences in the linked solution fully explain everything you are asking. What's tripping you up exactly? — Mad Physicist, Nov 08 '17 at 00:30
"Greedy" usually means an algorithm that always uses the first available move from the current state, and never backtracks. — Igor Tandetnik, Nov 08 '17 at 00:32
I guess you are talking about (this) [https://discuss.leetcode.com/topic/3443/simplest-o-n-solution-with-constant-space/9] in particular. The grammar maybe? :) I am finding it difficult to follow what he says. — , Nov 08 '17 at 00:33
@IgorTandetnik, wow, that is a pretty useful trick. I never thought about it like this. In retrospect, it seems obvious to me though. — , Nov 08 '17 at 00:34
@IgorTandetnik, one qq - you say "uses the first available move from the current state". However, if the input is `[3,3,1,0,4]`, then when `i=0`, shouldn't we take a jump of just `1` in order to reach the end? If we take a jump of `3` (`A[i]`) then we won't reach. — , Nov 08 '17 at 01:05
See: [Greedy algorithm on Wikipedia](https://en.wikipedia.org/wiki/Greedy_algorithm), [How to spot a "greedy" algorithm?](https://stackoverflow.com/q/7887487), [Please explain a greedy algorithm in a naive manner](https://cs.stackexchange.com/q/44710). Understanding why it is (or is not) a greedy algorithm largely comes down to fully understanding what a greedy algorithm is. Intuition comes with practice and experience more than anything else. — Bernhard Barker, Nov 08 '17 at 02:07
This algorithm searches from back to front. Searching from front to back can't be implemented in a greedy way - whatever order you enumerate the moves in, the first move may lead to a dead end and require backtracking. For backward search, the move is "find the rightmost preceding position from which I can jump to current position". Note that a "greedy" algorithm doesn't necessarily find the shortest solution. — Igor Tandetnik, Nov 08 '17 at 02:08
I would not directly approach this problem with a `greedy solution` at first attempt. I would go down the route of `recursion -> memoization` and then `greedy` which would help you with any variants of this problem. As stated above `greedy` does not find you the shortest solution. — Samer Tufail, Nov 08 '17 at 10:08
I disagree that this is a greedy algorithm. The problem is a decision problem, and this just does a linear search of the problem space. You might try a greedy algorithm to solve the related problem of "Return a sequence of moves that goes from index `0` to `N`, or if none exists" — Caleth, Nov 08 '17 at 12:23
I do not think that particular answer is greedy, either. Beyond that, it's way too broad of a question/topic. A DP algorithm may or may not also be greedy. A greedy algorithm may or may not be DP. A greedy algorithm may or may not "always find the right answer". But nobody's going to use DP instead of an easily iterated O(N) loop. — Kenny Ostrom, Nov 08 '17 at 13:34

Wasi Ahmad · Accepted Answer · 2017-11-08T01:20:00.793

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.

Suppose the input is: `[3,3,1,0,4]`. Doesn't your statement, "A greedy algorithm will select the optimal choice (_take the maximum jump_) and see at the end whether we can reach the end." Doesn't your statement belie the input? Because, assuming we start from the left, when `i=0`, we need to take the maximum jump (`3`), which is in fact, incorrect? As per my understanding, we need to take a jump of only `1` and then continue. — , Nov 08 '17 at 01:01
You are absolutely correct but you need to think in a different way because we are not trying to find the exact jump size at each step. The greedy algorithm will see, selecting 3 when `i=0` will take us to `i=1`. And then we will keep going to check whether we can reach or surpass the end index. You can check the link I attached to my answer. — Wasi Ahmad, Nov 08 '17 at 01:11

Is he being greedy?

1 Answers1