Learn AI Create the Future — with Pranay
Main site

LeetCode solutions

2229. Maximum Fruits Harvested After at Most K Steps

My accepted Python solution to LeetCode problem 2229, Maximum Fruits Harvested After at Most K Steps, running in 109ms.

  • Difficulty: Hard
  • Python
  • Runtime 109ms
  • Memory 52.1MB

Read the problem on LeetCode View on GitHub

The problem statement is LeetCode’s and stays on their site. What follows is my accepted solution.

Python

Accepted on LeetCode — runtime 109ms, memory 52.1MB, accepted 2025-12-29.

python
class Solution:
    def maxTotalFruits(self, fruits: List[List[int]], startPos: int, k: int) -> int:
        # Use sliding window approach
        # For each right endpoint, find the leftmost position we can reach
        # and calculate fruits in that window
        
        n = len(fruits)
        if n == 0:
            return 0
        
        # Calculate prefix sum of fruits
        prefix = [0] * (n + 1)
        for i in range(n):
            prefix[i + 1] = prefix[i] + fruits[i][1]
        
        def get_fruits(left_idx, right_idx):
            if left_idx > right_idx or left_idx >= n or right_idx < 0:
                return 0
            left_idx = max(0, left_idx)
            right_idx = min(n - 1, right_idx)
            return prefix[right_idx + 1] - prefix[left_idx]
        
        result = 0
        
        # Two pointer / sliding window
        # For each right position, find the best left position
        left = 0
        for right in range(n):
            right_pos = fruits[right][0]
            
            # Check if we can reach this right position at all
            # If right is beyond startPos + k, we can't reach it
            if right_pos > startPos + k:
                break
            
            # Find the leftmost position we can include in our harvest
            # while still being able to reach both left and right within k steps
            
            while left <= right:
                left_pos = fruits[left][0]
                
                # Calculate minimum steps needed to cover both left_pos and right_pos starting from startPos
                # Option 1: go left first then right
                # Option 2: go right first then left
                
                if left_pos >= startPos:
                    # Both are to the right of startPos
                    steps_needed = right_pos - startPos
                elif right_pos <= startPos:
                    # Both are to the left of startPos
                    steps_needed = startPos - left_pos
                else:
                    # startPos is between left_pos and right_pos
                    # Option 1: go left first, then right
                    steps1 = (startPos - left_pos) * 2 + (right_pos - startPos)
                    # Option 2: go right first, then left  
                    steps2 = (right_pos - startPos) * 2 + (startPos - left_pos)
                    steps_needed = min(steps1, steps2)
                
                if steps_needed <= k:
                    break
                left += 1
            
            if left <= right:
                result = max(result, prefix[right + 1] - prefix[left])
        
        return result

Source