Implement the Greedy Solution

Introduction

By now, we've put all the functionalities for our frog game in place. We just need to implement the greedy solution to generate the result. We will generate the result in the form of an array, whose every element is another array of exactly 2 values: the first one denotes the maximum number of jumps to take from each island, and the second value denotes the minimum number of steps taken to reach the current island.

First, let's go over how our solution will work with an example array.

Greedy solution approach

Let's assume that we are given an array [2, 3, 1, 3, 1, 2, 2, 3, 1], which denotes the maximum number of jumps that can be taken from each index (island). We'll follow the steps mentioned below to solve the problem and get the required array:

1. To generate the final result, we need to first find an intermediate result (say res). To do this, generate an array whose every index contains two elements. At each index of the array, the first element denotes the number of steps taken to reach the current index (island) and the second element denotes the number of jumps taken to reach the current index (island).

2. For each array index, except the $0^{th}$ index, set the number of steps to 1000 and the number of jumps to -1.

3. For the $0^{th}$ index (island), initialize the first element to 0 (because we are already at the first index) and the second element to -1 (because no jump can be taken).

4. In our example, we can take a maximum jump of 2 islands from the first index (island). So res for the $1^{st}$ index will now be [1, 1], because we've taken one step to reach this island and a jump of 1 was required from the previous island. Similarly, for the $2^{nd}$ index, the res will be [1, 2] because we took one step to reach this island and a jump of 2 was required from the previous island. Update these two values for each index only if a minimum value (step) is found. Perform similar steps for every island.

5. Finally, our res will look similar to [ 0, -1 ], [ 1, 1 ], [ 1, 2 ], [ 2, 2 ], [ 2, 3 ], [ 3, 2 ], [ 3, 3 ], [ 4, 2 ], [ 4, 2 ].

6. Notice that when we pick the second element from each index in the res array, we can actually traverse the path from the last index (island) to the first index (island) in such a way that the minimum number of steps are taken.

7. Reverse the above-generated path to get the step to take from the first index (island) to reach the last index (island).

Here's the code: