Jump Game
====

This post will cover this [leetcode problem](https://leetcode.com/problems/jump-game/)

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.

# Brainstorming

My first initial thought was to try all possible combinations and take the maximum, but I didn't bother pursuing that solution because I thought it would be too expensive.

Because the problem is jumping from left to right, it seems likely that there would be a solution where I could iterate from left to right until I hit the end of the list. It make senses to keep track of the biggest possible jump I could make at any space. In other words, as I iterate I should compare the current number with the biggest possible jump I can make and only take the greater of the two to the next iteration. I would also need to subtract the greater of the two numbers by one when I go to the next number because I would have effectively made a jump over one space. This solution seemed promising, so my next step was to try to disprove my hypothesis with the given examples.

## Example 1:

[2 3 1 1 4]

Index 0: Nothing to compare, so take 2 to index 1
Index 1: (from index 0) 2 - 1 = 1 < 3 (index 1). 
3 is greater so take 3 to index 2
Index 2: (from index 1) 3 - 1 = 2 > 1 (index 2). 
2 is greater so take 2 to index 3
Index 3: (from index 2) 1 - 1 = 0 < 1 (index 3). 
1 is greater so take 1 to index 4
Index 4: (from index 3) 1 - 1 = 0 < 4 (index 4). 
4 is at the end of the list and positive. Return True.

Since the value at the end of the list is positive, it must be the case that we "had enough jumps" to make it to the end. An example that returns False should illustrate this point.

## Example 2:

[3 2 1 0 4]

Index 0: Nothing to compare so take 3 to index 1
Index 1: (from index 0) 3 - 1 = 2 == 2 (index 1).
Equal so take 2 to index 2.
Index 2: (from index 1) 2 - 1 = 1 == 1 (index 2).
Equal so take 1 to index 3.
Index 3: (from index 2) 1 - 1 = 0 == 0 (index 3).
Greatest value is 0. Return False.
Index 4:

We return false above because at the third index the greatest value is 0, meaning we've run out of jumps! We can't jump from our current location, and we haven't reached the end of our list, so it must be False.

This solution seems promising.

Let's pseudocode (In retrospect, I should have come up with more test cases here. My logic up to this point seems correct, but lacks rigor as we will see. Can you spot what's incomplete about my logic?)

# Solution 1 Pseudocode

We know we need to iterate through the list, so we need a for loop. We also need to keep track of the biggest possible jump at each index.

In each iteration, we:
1. Subtract one from the biggest possible jump of the previous index because we've made a single jump since then.
2. Compare the subtracted value with the value of the current index.
- If the greater of the two is 0, return False

If we make it through the iterations, then we've made it to the last index without running out of jumps. In other words it is possible to jump to the last index, so we return True.

# Solution 1 Code

def canJump(self, nums):
    """
    :type nums: List[int]
    :rtype: bool
    """
    curMax = nums[0]
    for i in range(1, len(nums)):
        curMax = curMax - 1
        curMax = max(nums[i], curMax)
        if curMax <= 0:
            return False
    return True

At this point if you haven't found my errors, I want to encourage you once more to see if you can. (*Hint*: Run the first example through the code.)

# My Mistake:

## Cases to Consider
The first mistake was that I didn't consider extreme cases of the problem. A couple questions I should have considered as a standard approach, but didn't:
1. What if there were negative values? That's not possible because we are given an array of non-negative integers.
2. What if the list was empty? That's not possible because the statement "you are initially positioned at the first index of the array" implies that the list won't be. In a real interview I'd ask a clarifying question here.
3. What if the list had a length of one? This is possible... If the length is one, we want to return True because we're already at the last index.
- Our solution already accounts for this.
4. What if the list started with a 0? This is possible. Expected behavior would be to return False.
- Our solution would return True if the remaining list had enough jumps.

Let's consider Example 1 and replace the first value with a 0 to see the problem.

## Example 3 Modified:

[0 3 1 1 4]

Index 0: Nothing to compare, so take 0 to index 1
Index 1: (from index 0) 0 - 1 = -1 < 3 (index 1). <---- Problem
3 is greater so take 3 to index 2 
Index 2: (from index 1) 3 - 1 = 2 > 1 (index 2). 
2 is greater so take 2 to index 3
Index 3: (from index 2) 1 - 1 = 0 < 1 (index 3). 
1 is greater so take 1 to index 4
Index 4: (from index 3) 1 - 1 = 0 < 4 (index 4). 
4 is at the end of the list and positive. Return True.

We got -1 along the way! This should never happen because it means that we've used more jumps then we have!

Why did this happen? What was wrong with our initial logic?

## Example 4 - The Logical Flaw
The flaw becomes apparent when we consider the following example:

[2 0 0]
Input: [2,0,0]
Output: True
Explanation:
The first index allows you to get to the last index.
Since we got to the last index, we've accomplished the goal.

If we run example 4, through our code, what happens?

Index 0: Nothing to compare, so take 2 to index 1
Index 1: (from index 0) 2 - 1 = 1 > 0 (index 1).
2 is greater so take 2 to index 2 
Index 2: (from index 1) 1 - 1 = 0 == 0
0 is not positive, so we've run out of jumps. Return False

See how even though we're at the end, we've checked if we still have more jumps? We do this by checking if the greater of the two numbers is positive. That shouldn't happen.

# Two Possible Fixes

## Fix One
At this point the naive way to fix it would be to set the range from 1 to `len(nums) - 1`. We can reason, as long as we've make it to the last iteration with only positive hops, then we're good. So we adjust `range(1, len(nums))` to `range(1, len(nums) - 1)`

We just need to fix problem from *Example 3 Modified*. The problem with *Example 3 Modified* is that the value at index 0 is exempt from the logical flow. We just pass it along to the index 1. To fix this, my first thought would be, "let's just check if the first index is 0. I fit is return False". That would be a mistake because of one of the cases we outlined in *Cases to Consider*. Can you figure out which one it is?

As a result, we'll need to check if the length of the list is greater than 1.

Our resulting solution would look like this:

def canJump(self, nums):
    """
    :type nums: List[int]
    :rtype: bool
    """
    curMax = nums[0]
    if curMax == 0 and len(nums) > 1:
        return False
    for i in range(1, len(nums) - 1):
        curMax = curMax - 1
        curMax = max(nums[i], curMax)
        if curMax <= 0:
            return False
    return True

## Fix Two - A Cleaner Approach
The solution above seems like we are just slapping on band-aids for holes in our logic. Let's see if we can come up with a more cleaner solution.

Let's consider *Example 4* again.

[2 0 0]
Input: [2,0,0]
Output: True
Explanation:
The first index allows you to get to the last index.
Since we got to the last index, we've accomplished the goal.

The result is true because we've got to the last index.

One implication is that we don't need to check the last index if we still have jumps. In other words, if `curMax` is positive before the last index, then we don't need to need to check the last index. This resulted in Fix One.

### Implication One
Another implication is that it's ok to get zero during our iterations. You might ask as I did, "Doesn't that mean we've run out of jumps?!" Exactly, the perspective we are considering the problem is "when we can no longer jump, return `False`."

### Implication Two
But what if our perspective is, "if it's impossible to get to the current location, return False"? This perspective would allow us to have 0 because it is possible to get to the current location, we just can't jump anymore. How would this work?

Well, we know it's impossible to get to the current location if we are at negative one jumps because this means that we've jumped when we didn't have any more jumps left. This means we want check if the previous maximum was negative. Then if it is possible for us to be here, regardless of whether or not we have enough jumps.

#### Code
So we keep our conditional check *before* we've found the `max(current_value, previous_value - 1` because we just want to check the previous value.

def canJump(nums):
    curMax = nums[0]
    for i in range(1, len(nums)):
        curMax = curMax - 1
        if curMax < 0:
            return False
        curMax = max(nums[i], curMax)
    return True

#### Note
- We no longer worry about the first index because the first index is no longer an exception to our logic. It is implicit because when we start the loop we are checking to see whether or not it is possible for us to be here.
- Our condition does not include zero because it's ok if we've arrived at our current jump and have zero jumps left

Personally I struggled to grasp this perspective until I thought about it like a game. I had stumbled without really understanding it at first.

Imagine you're making a game where the player will get some energy or no energy at each position. The player then must make a decision taking into account various factors of the game. If the player gets to negative energy one, the player dies. This means one of the ways the player loses is to use too much energy. So we can't just prevent the player from making the decision, we need to implement the ability to make that decision.