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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Fruits Harvested After At Most K Steps

Number: 2229

Difficulty: Hard

Paid? No

Companies: Deutsche Bank, MishiPay

Problem Description

Given a sorted list of positions with fruits available and their corresponding amounts, starting at a given position, determine the maximum number of fruits that can be collected while taking at most k steps. You may move left or right and you harvest all fruits at every reached point. The challenge is to determine the optimal path that maximizes the total fruits harvested under the step constraint.

Key Insights

  • The positions are sorted which allows the use of a sliding window or two-pointer approach.
  • A valid window between indices i and j (corresponding to positions) is one where the cost to cover the endpoints (using the formula: (rightmost - leftmost) + min(|startPos - leftmost|, |startPos - rightmost|)) is within k steps.
  • Precomputing a prefix sum array helps quickly compute the total fruits in any valid window.
  • The algorithm cleverly scans through potential windows (or intervals) to update the maximum harvested fruits when the cost condition is met.

Space and Time Complexity

Time Complexity: O(n), where n is the number of fruit positions (each element is processed at most twice in the sliding window). Space Complexity: O(n), mainly due to the prefix sum array used to quickly get sums over intervals.

Solution

We solve the problem using a sliding window approach by leveraging the sorted order of the fruit positions. We first compute a prefix sum array on the fruit amounts for O(1) range sum queries. For any given window [i, j] (with corresponding positions left and right), the minimum step cost required is calculated by: cost = (right - left) + min(|startPos - left|, |startPos - right|) If this cost is within k, the fruits in that window can be harvested. We slide the window over the array and use two pointers to adjust the window so that the condition holds. Throughout, we update the maximum fruits collected using the prefix sum.

Code Solutions

# Python Code Solution
class Solution:
    def maxTotalFruits(self, fruits, startPos, k):
        n = len(fruits)
        # Create prefix sum of fruits amounts for O(1) range queries.
        prefix = [0] * (n + 1)
        for i in range(n):
            prefix[i+1] = prefix[i] + fruits[i][1]
        
        maxFruits = 0
        i = 0
        
        # Sliding window: j iterates over window end
        for j in range(n):
            # Move the left pointer (i) until the cost condition is satisfied.
            while i <= j:
                # Compute cost required to cover the window [i, j]
                left = fruits[i][0]
                right = fruits[j][0]
                # Cost: travel from start to one end then to the other.
                cost = (right - left) + min(abs(startPos - left), abs(startPos - right))
                if cost <= k:
                    break
                i += 1
            # If valid window, update maxFruits using prefix sum difference.
            if i <= j:
                maxFruits = max(maxFruits, prefix[j+1] - prefix[i])
        return maxFruits

# Example usage:
# sol = Solution()
# print(sol.maxTotalFruits([[2,8],[6,3],[8,6]], 5, 4))
← Back to All Questions