Maximum Fruits Harvested After at Most K Steps

Maximum Fruits Harvested After at Most K Steps

What is this problem about?

The Maximum Fruits Harvested After at Most K Steps interview question places you on a number line where fruits are positioned at various integer coordinates. You start at a given position and can move at most K steps in total — either left, right, or a combination of both. The goal is to collect the maximum number of fruits possible within that movement budget. Each fruit position has a count associated with it, and you want to maximize the total count harvested.

This problem elegantly combines spatial reasoning with optimization, making it a compelling Maximum Fruits Harvested coding problem for competitive programmers and interview candidates alike.

Why is this asked in interviews?

Top companies like Microsoft, Amazon, and Deutsche Bank use this problem to test candidates' ability to think about range queries and movement constraints simultaneously. It evaluates whether you can bridge the gap between a physical intuition (moving on a line) and an algorithmic pattern (sliding window over sorted positions). Candidates who can translate movement constraints into window bounds demonstrate strong problem modeling skills.

Algorithmic pattern used

This problem uses a combination of sliding window and prefix sums over sorted fruit positions. The key insight is: if you move right by r steps and then backtrack left, or move left by l steps then right, the total movement is bounded by K. You enumerate over how far you go in one direction, then binary search or slide a window to find the farthest valid position in the other direction. A prefix sum array over sorted positions lets you calculate total fruits in any range in O(1), making the overall algorithm O(n log n) or O(n) depending on implementation.

Example explanation

Suppose fruits are at positions: [(2, 3), (5, 5), (7, 2), (9, 4)] (position, count), you start at position 4, and K = 5.

• Moving right only: you can reach up to position 9. But steps used = 9 - 4 = 5 = K. You'd collect fruits at 5, 7, 9 → total = 11.
• Moving left first to position 2 (2 steps), then right to 7 (5 steps), total steps = 2 + (7 - 2) = 7 > K. Too many.
• Moving right to 7 (3 steps), then left to 4 (3 steps), total = 6 > K. Too many.
• Moving right to 5 (1 step), left to 2 (3 steps), total steps = 1 + 3 = 4 ≤ 5. Collect 3 + 5 = 8.

Best option here is going purely right: 11 fruits. The sliding window helps you enumerate these cases systematically.

Common mistakes candidates make

• Forgetting the two movement directions: Candidates often only consider going purely left or purely right, missing the combined case.
• Off-by-one in step counting: When you go right then backtrack left, the formula for total steps is right_distance + 2 * left_distance or 2 * right_distance + left_distance, depending on direction. Getting this formula wrong leads to incorrect window bounds.
• Ignoring starting position in window: The sliding window must account for the starting position when computing reachable range.

Interview preparation tip

Practice this Array Sliding Window Binary Search Prefix Sum interview pattern by first solving simpler "reach all positions within K steps" problems. Then layer in the "collect items" aspect. When you see movement on a 1D line with a step budget, immediately think about the two-direction split formula: min(left, right) * 2 + max(left, right) ≤ K. This insight unlocks the window logic cleanly.