Leetcode 904: Fruit Into Baskets
You are visiting a farm where fruit trees are planted in a single row from left to right. Each tree produces one type of fruit, represented by an integer array
fruits, where fruits[i] is the type of fruit the ith tree produces. You have two baskets, and each basket can hold an unlimited amount of one type of fruit. Starting from any tree, you must pick exactly one fruit from each tree while moving to the right until the fruits cannot fit into your baskets. Determine the maximum number of fruits you can collect.Problem
Approach
Steps
Complexity
Input: An integer array `fruits` representing the types of fruits on trees in a row.
Example: Input: fruits = [3, 3, 1, 2, 3]
Constraints:
• 1 <= fruits.length <= 10^5
• 0 <= fruits[i] < fruits.length
Output: An integer representing the maximum number of fruits you can collect.
Example: Output: 4
Constraints:
Goal: Calculate the longest subarray containing at most two unique numbers, representing the fruit types that fit into two baskets.
Steps:
• Use a sliding window to maintain the current subarray of fruit types.
• Keep track of the frequency of each fruit type in the window.
• If the number of unique fruit types exceeds two, adjust the window size by incrementing the starting index.
• Update the maximum length of the window whenever it contains at most two unique fruit types.
Goal: Limitations and rules to follow for the solution.
Steps:
• The input array can have up to 100,000 elements.
• Each tree produces only one type of fruit.
• You can only use two baskets, each capable of holding only one type of fruit.
Assumptions:
• The fruit array is non-empty.
• Each fruit type is represented by a non-negative integer.
• Input: Input: fruits = [3, 3, 1, 2, 3]
• Explanation: Start picking fruits at index 0. Collect fruits from trees [3, 3, 1, 2] before encountering the third type of fruit. Maximum fruits collected: 4.
• Input: Input: fruits = [1, 2, 2, 3]
• Explanation: Start picking fruits at index 1. Collect fruits from trees [2, 2, 3]. Maximum fruits collected: 3.
Approach: Use a sliding window and hash map to track fruit types and their frequencies. Adjust the window to maintain at most two types of fruits while maximizing the collected count.
Observations:
• This problem can be solved using the sliding window technique.
• We need to track the fruit types and their counts in the current window.
• The key is to maintain a window of at most two unique fruit types.
Steps:
• Initialize two pointers (start and end) to represent the sliding window.
• Use a hash map to store the count of each fruit type in the current window.
• Iterate through the array, adding fruits to the hash map and expanding the window.
• When the hash map contains more than two types of fruits, shrink the window by incrementing the start pointer and removing fruits from the hash map as necessary.
• Keep track of the maximum window size during this process.
Empty Inputs:
• Input array has only one tree.
Large Inputs:
• Input array is of length 100,000 with alternating fruit types.
Special Values:
• All trees produce the same type of fruit.
Constraints:
• Large arrays with more than two unique fruit types repeated frequently.
int totalFruit(vector<int>& fruits) {
// longest len of sub arr with at most two elements
map<int, int> mp;
int j = 0, res = 0, dst = 0;
for(int i = 0; i < fruits.size(); i++) {
mp[fruits[i]]++;
if(mp[fruits[i]] == 1) dst++;
if(dst <= 2) res = max(res, i - j + 1);
while(dst > 2 && j < i) {
mp[fruits[j]]--;
if(mp[fruits[j]] == 0) dst--;
j++;
}
}
return res;
}
1 : Function Definition
int totalFruit(vector<int>& fruits) {
Define the function 'totalFruit' which takes a vector of integers representing fruits as input and returns an integer representing the longest subarray with at most two distinct elements.
2 : Variable Declaration
map<int, int> mp;
A map 'mp' is used to store the count of each fruit in the current sliding window.
3 : Variable Initialization
int j = 0, res = 0, dst = 0;
Initialize variables: 'j' for the left boundary of the window, 'res' for storing the maximum length of the subarray, and 'dst' for tracking the number of distinct fruits in the window.
4 : Loop
for(int i = 0; i < fruits.size(); i++) {
Iterate through the 'fruits' array using 'i' as the right boundary of the sliding window.
5 : Map Update
mp[fruits[i]]++;
Increment the count of the current fruit in the map.
6 : Distinct Count Update
if(mp[fruits[i]] == 1) dst++;
If the count of the current fruit becomes 1 (i.e., it is newly added to the window), increment the distinct fruit count ('dst').
7 : Subarray Update
if(dst <= 2) res = max(res, i - j + 1);
If the window contains at most two distinct fruits, update the result with the maximum length of the subarray (i - j + 1).
8 : Inner While Loop
while(dst > 2 && j < i) {
If the window contains more than two distinct fruits, move the left boundary 'j' to shrink the window until it contains at most two distinct fruits.
9 : Map Update
mp[fruits[j]]--;
Decrement the count of the fruit at the left boundary 'j' to reduce its frequency in the window.
10 : Distinct Count Update
if(mp[fruits[j]] == 0) dst--;
If the count of the fruit at 'j' becomes 0, decrement the distinct fruit count ('dst').
11 : Left Boundary Update
j++;
Increment 'j' to shrink the left boundary of the window.
12 : Return Statement
return res;
Return the result, which is the length of the longest subarray with at most two distinct elements.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: Each fruit is processed at most twice—once when added to the window and once when removed.
Best Case: O(1)
Worst Case: O(1)
Description: The hash map stores at most two unique keys at any time.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus