Finding maximum number of fruits that can be kept in one basket
Problem Statement
Given an array of characters where each character represents a fruit tree, you are given two baskets and your goal is to put maximum number of fruits in each basket. The only restriction is that each basket can have only one type of fruit.
You can start with any tree, but once you have started you can’t skip a tree. You will pick one fruit from each 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 the baskets.
Example 1:
Input: Fruit=['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: Fruit=['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']
Solution
This problem follows the Sliding Window pattern and is quite similar to Longest Substring with K Distinct Characters. In this problem, we need to find the length of the longest subarray with no more than two distinct characters (or fruit types!). This transforms the current problem into Longest Substring with K Distinct Characters where K=2.
Javascript code below:-
function fruits_into_baskets(fruits) {
let windowStart = 0,
maxLength = 0,
fruitFrequency = {};
// try to extend the range [windowStart, windowEnd]
for (let windowEnd = 0; windowEnd < fruits.length; windowEnd++) {
const rightFruit = fruits[windowEnd]; // collect fruits/character
// prepare a frequency map of characters by initializing the values for the character/fruit as key
if (typeof fruitFrequency[rightFruit] === 'undefined') {
fruitFrequency[rightFruit] = 0;
}
fruitFrequency[rightFruit] += 1;
// shrink the sliding window, until we are left with '2' fruits in the fruit frequency dictionary
while (Object.keys(fruitFrequency).length > 2) {
const leftFruit = fruits[windowStart];
fruitFrequency[leftFruit] -= 1;
if (fruitFrequency[leftFruit] === 0) {
delete fruitFrequency[leftFruit];
}
windowStart += 1; // shrink the window
}
maxLength = Math.max(maxLength, windowEnd - windowStart + 1);
}
return maxLength;
}
document.write(Maximum number of fruits: ${fruits_into_baskets(['A', 'B', 'C', 'A', 'C'])}<br/>);
document.write(Maximum number of fruits: ${fruits_into_baskets(['A', 'B', 'C', 'B', 'B', 'C'])}<br/>);
Steps
- Loop through the array of fruits (character array) and prepare a frequency map of characters with their respective occurrence count in the array.
- Assort the fruits with maximum number of one type of fruit in one basket and maximum number of another type of fruit in another basket.
- To do this, use the fruit frequency map and check which character frequency is at least 2 (or more) and with each iteration keep shrinking the sliding window and store the maximum window length in maxLength.
- Return maxLength.
Time Complexity
The time complexity of the above algorithm will be O(N) where ‘N’ is the number of characters in the input array. The outer for loop runs for all characters and the inner while loop processes each character only once, therefore the time complexity of the algorithm will be O(N+N) which is asymptotically equivalent to O(N).
Space Complexity
The algorithm runs in constant space O(1) as there can be a maximum of three types of fruits stored in the frequency map.
Posted from my blog with SteemPress : https://www.golibrary.co/finding-maximum-number-of-fruits-that-can-be-kept-in-one-basket/
Join the community in our migration to Hive, a community built blockchain for the community. All Steem account holders will receive equivalent stake on the new Hive blockchain.
Please follow @innerhive on twitter for more information.