[LeetCode] Jump Game II

Problem: You are given a 0-indexed array of integers nums of length n. You are initially positioned at nums[0].

Each element nums[i] represents the maximum length of a forward jump from index i. In other words, if you are at nums[i], you can jump to any nums[i + j] where:

• 0 <= j <= nums[i] and
• i + j < n

Return the minimum number of jumps to reach nums[n - 1]. The test cases are generated such that you can reach nums[n - 1].

Example:

Input: nums = [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2. Jump 1 step from index 0 to 1, then 3 steps to the last index.

Approach: My observation about the problem is if we can reach an index i and then we can definitely reach index i - 1. The proof is simple:

• If the length of jump is 1 then we are already at i - 1.
• Otherwise we can take length - 1 jump to reach i - 1.

In this way we can prove that we can reach any j where j = 0 to i - 1. Now we can maintain a table say jump where jump[i]  tells the farthest point it can reach. We can fill this table in following way:

• jump[0] = nums[0]
• jump[i] = MAX(jump[i - 1], i + jump[i]

Now we can simply use this table to get our answer. 

The above solution works and it works efficiently but it's taking extra space. Let's try to reduce the space and also let's see the problem in different way. We can be greedy here too. Idea is simple let's say the jump range at any index is (currStart, currEnd). We know we need to make a jump here at a particular index then being greedy we want to go till the currEnd and then take a jump. 

But now what's the jump we want to take is the maximum reachable point from currStart...currEnd and when we take a jump the next currEnd will become this maximum reachable point.

Implementation in C#:

Apporach 1: DP:

    public int Jump(int[] nums)

    {

        int length = nums?.Length ?? 0;

        if(length <= 1)

        {

            return 0;

        }

        int[] jumps = new int[length];

        jumps[0] = nums[0];

        for (int i = 1; i < length; ++i)

        {

            jumps[i] = Math.Max(jumps[i - 1], i + nums[i]);

        }

        int numOfJumps = 0;

        for (int i = 0; i < length - 1; i = jumps[i])

        {

            ++numOfJumps;

        }

        return numOfJumps;

    }

Apporach 2: Greedy:

    public int Jump(int[] nums)

    {

        int length = nums?.Length ?? 0;

        if (length <= 1)

        {

            return 0;

        }

        int jumps = 0, currEnd = 0, longestJumpIndex = 0;

        for (int i = 0; i < length; ++i)

        {

            longestJumpIndex = Math.Max(longestJumpIndex, i + nums[i]);

            if (i == currEnd)

            {

                ++jumps;

                currEnd = longestJumpIndex;

                if (currEnd == length - 1)

                {

                    break;

                }

            }

        }

        return jumps;

    }

Complexity: O(n)