We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Frog Jump II

Difficulty: Medium

Problem Description

You are given a 0-indexed integer array stones sorted in strictly increasing order representing the positions of stones in a river. A frog, initially on the first stone, wants to travel to the last stone and then return to the first stone. However, it can jump to any stone at most once. The cost of a path is the maximum length of a jump among all jumps in the path. Return the minimum cost of a path for the frog.

Key Insights

  • The frog can jump to any stone only once, meaning it has to plan its jumps carefully to minimize the maximum jump length.
  • The goal is to minimize the maximum jump length when traveling from the first to the last stone and back.
  • The maximum jump length will be determined by the largest gap between consecutive stones, either in the forward or return trip.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

To solve the problem, we can use a greedy approach. We compute the maximum jump length required for the frog to travel from the first stone to the last stone and then back to the first stone. The key steps are:

  1. Calculate the maximum jump length required for the direct jump from the first stone to the last stone.
  2. Calculate the maximum jump length required for the return journey.
  3. The minimum cost will be the larger of these two lengths since we want to minimize the maximum jump across the entire journey.

The data structure used is a simple array to store the stone positions, and we iterate through the array to find the maximum gap between consecutive stones.

Code Solutions

def minCost(stones):
    max_jump = 0
    n = len(stones)
    
    # Calculate maximum jump length between consecutive stones
    for i in range(1, n):
        max_jump = max(max_jump, stones[i] - stones[i - 1])
    
    # The minimum cost is the maximum jump found
    return max_jump

# Example usage
print(minCost([0, 2, 5, 6, 7]))  # Output: 5
← Back to All Questions