2106. Maximum Fruits Harvested After at Most K Steps
Approach
Sliding window — try all windows anchored left or right of startPos within reach k.
Key Techniques
Array problems involve manipulating elements stored in a contiguous block of memory. Key techniques include two-pointer traversal, prefix sums, sliding windows, and in-place partitioning. In C#, arrays are zero-indexed and fixed in size — use List<T> when you need dynamic resizing.
Binary search reduces search space by half each step, giving O(log n) time. Beyond sorted arrays, apply it on the answer space ("binary search on result") when you can define a monotonic predicate — e.g., "can we achieve X with k resources?"
The sliding window technique maintains a dynamic sub-array (or substring) of interest, expanding the right boundary and shrinking the left boundary based on a constraint. It reduces O(n²) substring enumeration to O(n). Track state (frequency map, sum, distinct count) incrementally.
// Approach: Sliding window — try all windows anchored left or right of startPos within reach k.
// Time: O(n) Space: O(1)
public class Solution
{
public int MaxTotalFruits(int[][] fruits, int startPos, int k)
{
int maxFruits = 0; // Stores the maximum number of fruits we can collect
int currentSum = 0; // Stores the current sum of fruits between two points
// Two pointers approach: i is for the start point and j is for the end point
for (int i = 0, j = 0; j < fruits.Length; ++j)
{
int positionJ = fruits[j][0]; // The position of the j-th tree
int fruitsAtJ = fruits[j][1]; // The number of fruits at the j-th tree
currentSum += fruitsAtJ; // Add fruits at the j-th tree to the current sum
// Adjust the starting point i to not exceed the maximum distance k
while (i <= j &&
positionJ - fruits[i][0] +
Math.Min(Math.Abs(startPos - fruits[i][0]), Math.Abs(startPos - positionJ))
> k)
{
// Subtract the number of fruits at the i-th tree as we move the start point forward
currentSum -= fruits[i][1];
i++; // Increment the start point
}
// Update maxFruits with the maximum of current sum and previously calculated maxFruits
maxFruits = Math.Max(maxFruits, currentSum);
}
return maxFruits; // Return the maximum number of fruits that can be collected
}
}