0% completed
Problem Statement
You are visiting a farm to collect fruits. The farm has a single row of fruit trees. You will be given two baskets, and your goal is to pick as many fruits as possible to be placed in the given baskets.
You will be given an array of characters where each character represents a fruit tree. The farm has following restrictions:
- Each basket can have only one type of fruit. There is no limit to how many fruit a basket can hold.
- You can start with any tree, but you can’t skip a tree once you have started.
- You will pick exactly one fruit from every tree until you cannot, i.e., you will stop when you have to pick from a third fruit type.
Write a function to return the maximum number of fruits in both baskets.
Example 1:
Input: arr=['A', 'B', 'C', 'A', 'C']
Output: 3
Explanation: We can put 2 'C' in one basket and one 'A' in the other from the subarray ['C', 'A', 'C']
Example 2:
Input: arr = ['A', 'B', 'C', 'B', 'B', 'C']
Output: 5
Explanation: We can put 3 'B' in one basket and two 'C' in the other basket. This can be done if we start with the second letter: ['B', 'C', 'B', 'B', 'C']
Constraints:
- 1 <= arr.length <= 10^5
0 <= arr[i] < arr.length
Solution
To solve this problem, we use a sliding window approach. This technique is effective for problems involving contiguous subarrays or sublists. The sliding window approach allows us to maintain a window of elements that meet a certain condition—in this case, having no more than two types of fruits. We expand the window by adding elements from the right and contract it from the left when the condition is violated. This approach ensures we check all possible subarrays without starting from each element repeatedly, making it efficient.
This method works well because it continuously adjusts the window size based on the elements it encounters. By using a dictionary to keep track of the fruit counts within the window, we can efficiently manage and adjust the window size to find the maximum length subarray that satisfies the condition. The efficiency comes from the fact that each element is processed at most twice, once when added and once when removed from the window.
Step-by-Step Algorithm
- Initialize two variables:
windowStart
to keep track of the starting index of the window andmaxLength
to store the maximum length of the subarray found. - Create a dictionary
fruitFrequencyMap
to count the frequency of each fruit in the current window. - Iterate over the array using a variable
windowEnd
which marks the end of the window.- Add the current fruit at
windowEnd
to the dictionary and update its count. - If the dictionary size exceeds two, it means there are more than two types of fruits in the window.
- Shrink the window from the start by removing the fruit at
windowStart
and updating the dictionary. - If the count of the fruit at
windowStart
becomes zero, remove it from the dictionary. - Move
windowStart
to the right to shrink the window.
- Shrink the window from the start by removing the fruit at
- Update
maxLength
to be the maximum of its current value and the size of the current window (windowEnd - windowStart + 1
).
- Add the current fruit at
- Return
maxLength
as the result.
Algorithm Walkthrough
Consider the input array ['A', 'B', 'C', 'A', 'C']
:
- Initialize
windowStart = 0
,maxLength = 0
,fruitFrequencyMap = {}
. windowEnd = 0
: Add 'A' tofruitFrequencyMap
, making it{'A': 1}
.windowEnd = 1
: Add 'B' tofruitFrequencyMap
, making it{'A': 1, 'B': 1}
.maxLength = 2
(subarray['A', 'B']
).
windowEnd = 2
: Add 'C' tofruitFrequencyMap
, making it{'A': 1, 'B': 1, 'C': 1}
.- More than two types of fruits, shrink window:
windowStart = 1
,fruitFrequencyMap = {'A': 0, 'B': 1, 'C': 1}
. - Remove 'A':
fruitFrequencyMap = {'B': 1, 'C': 1}
.
- More than two types of fruits, shrink window:
windowEnd = 3
: Add 'A' tofruitFrequencyMap
, making it{'B': 1, 'C': 1, 'A': 1}
.- More than two types of fruits, shrink window:
windowStart = 2
,fruitFrequencyMap = {'B': 0, 'C': 1, 'A': 1}
. - Remove 'B':
fruitFrequencyMap = {'C': 1, 'A': 1}
.
- More than two types of fruits, shrink window:
windowEnd = 4
: Add 'C' tofruitFrequencyMap
, making it{'C': 2, 'A': 1}
.maxLength = 3
(subarray['C', 'A', 'C']
).
Code
Here is what our algorithm will look like:
Complexity Analysis
Time Complexity:
-
Single pass: The algorithm uses a sliding window approach, making a single pass through the input array. The outer loop runs once for each character in the input array, so it runs O(N) times, where
N
is the length of the array. -
Sliding window adjustment: The inner loop ensures that the window contains no more than two distinct characters. For each character, adding or removing from the
fruitFrequencyMap
takes constant time, O(1), because hash map operations (insertion, update, and deletion) are O(1) on average. -
The overall time complexity is O(N) because both the outer and inner loops process each element at most once.
Overall time complexity: O(N).
Space Complexity
-
HashMap space: The
fruitFrequencyMap
stores the frequency of up to two distinct characters. The space complexity of the hash map is O(1), which is constant. -
Additional variables: The algorithm uses a few additional variables (
windowStart
,windowEnd
,maxLength
), which require constant space, O(1).
Overall space complexity: O(1).
Similar Problems
Problem 1: Longest Substring with at most 2 distinct characters
Given a string, find the length of the longest substring in it with at most two distinct characters.
Solution: This problem is exactly similar to our parent problem.
.....
.....
.....
Table of Contents
Contents are not accessible
Contents are not accessible
Contents are not accessible
Contents are not accessible
Contents are not accessible