Notice: This page requires JavaScript to function properly.
Please enable JavaScript in your browser settings or update your browser.
Jumping Frog | Greedy on Arrays
Greedy Algorithms using Python
course content

Course Content

Greedy Algorithms using Python

Greedy Algorithms using Python

1. Greedy Algorithms: Overview and Examples
2. Greedy on Arrays
3. Greedy on Graphs

bookJumping Frog

Each element in array nums represents the maximum jump length that can be done from this position. The frog's start position is the array’s first index, and each time at the position i it moves forward on 1, 2, … , or nums[i] steps. Return true if the frog can reach the last index, and false if not.

Example 1:

Input: nums = [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: nums = [3,2,1,0,4]

Output: false

Explanation: frog will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.

At first sight, there are too many possible ways to reach it, and you can simply check them all until you find any. But this approach is not optimal enough. Let’s take a look at a greedy approach: let pos be the biggest index that a frog can reach in the current situation. Then, let’s try to make this value as much as possible, i. e. either jump to the i+nums[i] position or stay at the position pos (sometimes there is no sense to jump because you won’t come closer to the last index). We’ll update pos for each i from 0 to n, since the frog can jump to any position from i to a[i]+i. Note that some positions may be non-accessible, and when it happens, pos index becomes less than i.

Overall, there is an algorithm:

12345
pos = 0 for i in range(n): if pos < i: return false # i is not accessible pos = max(pos, i+nums[i]) return pos >= i
copy

Task

Put this algorithm inside jumping() function. Call the function.

Switch to desktopSwitch to desktop for real-world practiceContinue from where you are using one of the options below
Everything was clear?

How can we improve it?

Thanks for your feedback!

Section 2. Chapter 3
toggle bottom row

bookJumping Frog

Each element in array nums represents the maximum jump length that can be done from this position. The frog's start position is the array’s first index, and each time at the position i it moves forward on 1, 2, … , or nums[i] steps. Return true if the frog can reach the last index, and false if not.

Example 1:

Input: nums = [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: nums = [3,2,1,0,4]

Output: false

Explanation: frog will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.

At first sight, there are too many possible ways to reach it, and you can simply check them all until you find any. But this approach is not optimal enough. Let’s take a look at a greedy approach: let pos be the biggest index that a frog can reach in the current situation. Then, let’s try to make this value as much as possible, i. e. either jump to the i+nums[i] position or stay at the position pos (sometimes there is no sense to jump because you won’t come closer to the last index). We’ll update pos for each i from 0 to n, since the frog can jump to any position from i to a[i]+i. Note that some positions may be non-accessible, and when it happens, pos index becomes less than i.

Overall, there is an algorithm:

12345
pos = 0 for i in range(n): if pos < i: return false # i is not accessible pos = max(pos, i+nums[i]) return pos >= i
copy

Task

Put this algorithm inside jumping() function. Call the function.

Switch to desktopSwitch to desktop for real-world practiceContinue from where you are using one of the options below
Everything was clear?

How can we improve it?

Thanks for your feedback!

Section 2. Chapter 3
toggle bottom row

bookJumping Frog

Each element in array nums represents the maximum jump length that can be done from this position. The frog's start position is the array’s first index, and each time at the position i it moves forward on 1, 2, … , or nums[i] steps. Return true if the frog can reach the last index, and false if not.

Example 1:

Input: nums = [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: nums = [3,2,1,0,4]

Output: false

Explanation: frog will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.

At first sight, there are too many possible ways to reach it, and you can simply check them all until you find any. But this approach is not optimal enough. Let’s take a look at a greedy approach: let pos be the biggest index that a frog can reach in the current situation. Then, let’s try to make this value as much as possible, i. e. either jump to the i+nums[i] position or stay at the position pos (sometimes there is no sense to jump because you won’t come closer to the last index). We’ll update pos for each i from 0 to n, since the frog can jump to any position from i to a[i]+i. Note that some positions may be non-accessible, and when it happens, pos index becomes less than i.

Overall, there is an algorithm:

12345
pos = 0 for i in range(n): if pos < i: return false # i is not accessible pos = max(pos, i+nums[i]) return pos >= i
copy

Task

Put this algorithm inside jumping() function. Call the function.

Switch to desktopSwitch to desktop for real-world practiceContinue from where you are using one of the options below
Everything was clear?

How can we improve it?

Thanks for your feedback!

Each element in array nums represents the maximum jump length that can be done from this position. The frog's start position is the array’s first index, and each time at the position i it moves forward on 1, 2, … , or nums[i] steps. Return true if the frog can reach the last index, and false if not.

Example 1:

Input: nums = [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: nums = [3,2,1,0,4]

Output: false

Explanation: frog will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.

At first sight, there are too many possible ways to reach it, and you can simply check them all until you find any. But this approach is not optimal enough. Let’s take a look at a greedy approach: let pos be the biggest index that a frog can reach in the current situation. Then, let’s try to make this value as much as possible, i. e. either jump to the i+nums[i] position or stay at the position pos (sometimes there is no sense to jump because you won’t come closer to the last index). We’ll update pos for each i from 0 to n, since the frog can jump to any position from i to a[i]+i. Note that some positions may be non-accessible, and when it happens, pos index becomes less than i.

Overall, there is an algorithm:

12345
pos = 0 for i in range(n): if pos < i: return false # i is not accessible pos = max(pos, i+nums[i]) return pos >= i
copy

Task

Put this algorithm inside jumping() function. Call the function.

Switch to desktopSwitch to desktop for real-world practiceContinue from where you are using one of the options below
Section 2. Chapter 3
Switch to desktopSwitch to desktop for real-world practiceContinue from where you are using one of the options below
some-alt