Problem Description
You are visiting a farm that has a single row of fruit trees arranged from left to right. The trees are represented by an integer array fruits where fruits[i] is the type of fruit the ith tree produces. You want to collect as much fruit as possible with the following rules:
- You only have two baskets, and each basket can only hold a single type of fruit.
- Starting from any tree of your choice, you must pick exactly one fruit from every tree while moving to the right, until you reach a tree with fruit that cannot fit in your baskets.
Given the integer array fruits, return the maximum number of fruits you can pick.
Key Insights
- The problem can be solved using the sliding window technique, which allows us to efficiently find the longest subarray that contains at most two distinct types of fruits.
- We need to maintain the count of fruits in the current window and adjust the window size when more than two types of fruits are encountered.
- The algorithm should traverse the array only once, making it efficient.
Space and Time Complexity
Time Complexity: O(n) - where n is the number of trees (length of the fruits array).
Space Complexity: O(1) - since we are using a fixed number of variables for counting.
Solution
To solve this problem, we will use the sliding window approach. We will maintain a window defined by two pointers (start and end). As we iterate through the fruits array with the end pointer, we will keep track of the count of each fruit type in the current window using a dictionary. If the number of distinct fruit types exceeds two, we will move the start pointer to the right until we are back to two types. The maximum size of the window during this process will be our answer.