Solution: Fruit Into Baskets

Statement

While visiting a farm of fruits, you have been given a row of fruits represented by an integer array, fruits, where fruits[i] is the type of fruit the $i^{th}$ tree produces. You have to collect fruits, but there are some rules that you must follow while collecting fruits:

• You are given only two baskets, each capable of holding an unlimited quantity of a single type of fruit.

• You can start collecting from any tree but must collect exactly one fruit from each tree (including the starting tree) while moving to the right.

• You must stop while encountering a tree with a fruit type that cannot fit into any of your baskets.

Return the maximum number of fruits you can collect following the above rules for the given array of fruits.

Constraints:

• $1\leq$ fruits.length $\leq10^3$

• $0\leq$ fruits[i] $\lt$ fruits.length

Solution

The challenge is to collect as many fruits as possible from a row of trees, each producing a specific type of fruit. We only have two baskets available; each can hold exactly one type of fruit, but there is no limit to the quantity of fruit(single type) a basket can hold. This means we can only collect at most two distinct types of fruits.

The solution uses the sliding window pattern because it helps to manage the range of trees being considered. It starts from a small window and expands the window as more trees are added, allowing maximum fruit collection. However, if the number of fruit types exceeds two, the window reduces its size from the left until it becomes valid again (with only two fruit types). The solution keeps sliding the window and keeping track of the largest valid window size that represents the maximum number of fruits that can be collected.

Here’s the step-by-step explanation of the solution:

1. We initialize a hash map, baskets, to track the count of each fruit type available in the current window and a variable left to mark the start of the current window.

2. We also create a variable, collected, to store the number of fruits we can collect.

3. We then iterate through the fruits array, starting from the leftmost tree and moving toward the end of the array. We do the following for each tree while iterating:

   1. Add the fruit type as a key in baskets and increment the count against it by $1$.

   2. If the length of baskets exceeds $2$, the number of distinct fruit types is more than $2$ in the current window.

      1. We remove the fruit from the left of the current window until the window has at most $2$ types of fruit.

      2. If the count of a fruit becomes zero:

         1. We remove it from the baskets.

      3. Next, we increment the left by $1$ to move the window forward.

   3. After adjusting the window, we compute the maximum number of fruits that can be collected from the current window using the formula: $\text{maximum(collected, right ~-~ left ~+~ 1)}$. We store this value in collected.

4. After iterating through fruits, we return collected, representing the maximum number of collected fruits.

Let’s look at the following illustration to get a better understanding of the solution: