Question

You are given an array of integers fruits where each element represents the type of a fruit. You are also given two integers k and m.

Your task is to collect m fruits using two baskets while respecting the following rules:

1. You can pick any fruit from the array, but once you have started picking a fruit from a basket, you cannot pick any other fruit from that basket until you put it back.
2. Once you have picked m fruits, you cannot pick any more fruits from the array.
3. Each basket can only hold one type of fruit at a time.

Write a function totalFruit(fruits: List[int], m: int, k: int) -> int to calculate the maximum number of fruits you can collect.

Example

Input: fruits = [1, 2, 3, 4, 5, 6, 3, 4, 5], m = 2, k = 1

Output: 6

Note

In the given example, we can pick fruits 1 to 6, which makes a total of 6 fruits. We start by picking fruit 1 into the first basket and then pick fruits 2, 3, 4, 5, 6 into the second basket. The remaining fruits cannot be picked because we already have m = 2 fruits.

Answer

To solve this problem, we can use the sliding window technique. We will iterate through the array and keep track of the types of fruits in the current window using a dictionary. We will also keep track of the maximum number of fruits we can collect.

Here are the step-by-step details of the solution:

1. Initialize variables: max_fruits = 0, window_start = 0, and fruit_counts = {}.
2. Iterate through the array using the variable window_end as the end index of the window.
3. For each fruit at index window_end, add it to the fruit_counts dictionary with its count.
4. Check if the fruit_counts dictionary has more than k distinct fruits. If it does, we need to shrink the window from the window_start to exclude the leftmost fruit.
   • Decrement the count of the fruit at window_start in the fruit_counts dictionary.
   • If the count becomes zero, remove the fruit from the fruit_counts dictionary.
   • Increment window_start to move the window rightwards.
5. Calculate the number of fruits in the current window by subtracting window_start from window_end and add 1 to the count.
6. Update max_fruits with the maximum value between max_fruits and the number of fruits in the current window.
7. If the number of collected fruits (max_fruits) is greater than or equal to m, stop the iteration as we cannot collect more than m fruits.
8. Return max_fruits as the maximum number of fruits collected.

Let's implement this solution in Python: