Fruits into Baskets
Ramayana — Hanuman in Ashoka Vatika — Two Baskets, Maximum Harvest
द्वौ पात्रौ मया सन्ति फलानां ग्रहणे सदा। दीर्घतमं वनखण्डं भोजयेयं विचक्षणः॥
*I carry only two baskets for gathering fruit. The wise one collects from the longest unbroken stretch of forest.*
The Story
When Hanuman leaped into Lanka and found himself in Ravana's magnificent Ashoka Vatika — the garden of eternal spring — he faced a peculiar challenge. The garden had n trees in a row, each bearing a different type of fruit labeled with a number. He carried exactly two baskets, and each basket could hold only ONE type of fruit.
Hanuman's mission was not just rescue — it was reconnaissance. He wanted to forage through the longest unbroken stretch of the garden, collecting fruit the entire way, limited by his two baskets. Once a basket was committed to a fruit type, it held only that type.
"The fruit row is `[1, 2, 1, 3, 4]`," Vibhishana whispered from behind a tree. "You have 2 baskets. What is the most consecutive trees you can harvest?"
Hanuman thought quickly. This was the same as: find the longest subarray with at most 2 distinct values.
"Window [1,2,1]: types {1,2} — 2 baskets needed, length 3. Valid!" "Window [1,2,1,3]: types {1,2,3} — 3 baskets needed. Invalid!" "Window [2,1,3]: types {2,1,3} — still 3. Invalid." "Window [1,3,4]: types {1,3,4} — still 3. Invalid." "Window [3,4]: types {3,4} — length 2."
"So the answer is 3," Hanuman concluded. "Starting from the first tree."
"But for a garden of a million trees," Vibhishana said, "you can't check every window manually."
Hanuman implemented the sliding window approach he had heard from Rama's wise minister Jabali:
"Keep a basket-map: a frequency count of fruit types in the current window. As I walk right through the garden, add each fruit type to the map. If the map ever grows beyond 2 distinct types (more than 2 keys), I have too many basket types and must abandon the leftmost fruits."
"Abandon how? Walk the left pointer rightward: remove the leftmost fruit from the map count. If its count drops to 0, remove that type entirely from the map. Continue until the map has ≤ 2 keys."
"After each expansion, record the current window length."
Hanuman traced through `[1, 2, 1, 3, 4]`:
- right=0 (1): map={1:1}, size=1. len=1, max=1 - right=1 (2): map={1:1,2:1}, size=2. len=2, max=2 - right=2 (1): map={1:2,2:1}, size=2. len=3, max=3 - right=3 (3): map={1:2,2:1,3:1}, size=3 > 2! Shrink: left=0 (type 1): count[1]=2→1. size=3. Shrink: left=1 (type 2): count[2]=1→0, remove type 2. map={1:1,3:1}, size=2. left=2. len=3-2+1=2, max=3 - right=4 (4): map={1:1,3:1,4:1}, size=3 > 2! Shrink: left=2 (type 1): count[1]=1→0, remove type 1. map={3:1,4:1}, size=2. left=3. len=4-3+1=2, max=3
Answer: 3.
"This is identical to 'longest substring with at most 2 distinct characters,'" Vibhishana observed.
"Yes," Hanuman confirmed. "The 'fruits' are just the 'characters,' the 'basket types' are the 'distinct characters,' and the constraint 'at most 2 baskets' is 'at most 2 distinct.' The algorithm is the same — only the story differs."
Hanuman harvested from the optimal stretch of the Ashoka Vatika, filling both baskets to capacity. He took mango and coconut — the two types that ran longest together — and left the garden as undisturbed as possible.
"Two baskets," he said quietly, leaping from tree to tree. "Always two. The constraint is fixed, the window is variable. Find the longest stretch that respects the constraint."
This is the Sliding Window technique for finding the longest subarray with at most 2 distinct elements.
Vibhishana's First Instinct
Try every pair of start and end indices. Count distinct fruit types in each window. Track maximum valid length. O(n²) time.
public int totalFruitBruteForce(int[] fruits) {
int max = 0;
for (int start = 0; start < fruits.length; start++) {
Map<Integer, Integer> baskets = new HashMap<>();
for (int end = start; end < fruits.length; end++) {
baskets.merge(fruits[end], 1, Integer::sum);
if (baskets.size() > 2) break; // Too many types, stop extending
max = Math.max(max, end - start + 1);
}
}
return max;
}Hanuman's Wisdom
public int totalFruit(int[] fruits) {
Map<Integer, Integer> baskets = new HashMap<>(); // fruit type -> count
int left = 0;
int maxLen = 0;
for (int right = 0; right < fruits.length; right++) {
// Pick fruit from current tree into appropriate basket
baskets.merge(fruits[right], 1, Integer::sum);
// If we now have 3 or more fruit types, must abandon left fruits
while (baskets.size() > 2) {
int leftFruit = fruits[left];
baskets.merge(leftFruit, -1, Integer::sum);
if (baskets.get(leftFruit) == 0) {
baskets.remove(leftFruit); // Basket for this type is now empty
}
left++;
}
maxLen = Math.max(maxLen, right - left + 1);
}
return maxLen;
}
// Test
public static void main(String[] args) {
System.out.println(new Solution().totalFruit(new int[]{1,2,1})); // 3
System.out.println(new Solution().totalFruit(new int[]{0,1,2,2})); // 3
System.out.println(new Solution().totalFruit(new int[]{1,2,3,2,2})); // 4
}Step-by-Step Walkthrough
fruits = [3, 3, 3, 1, 2, 1, 1, 2, 3, 3, 4]
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
right=0-2 (3): {3:3}, size=1, max=3
right=3 (1): {3:3,1:1}, size=2, len=4, max=4
right=4 (2): {3:3,1:1,2:1}, size=3!
left=0 (3): 3→2, size=3
left=1 (3): 3→1, size=3
left=2 (3): 3→0, remove 3. {1:1,2:1}, size=2. left=3.
len=4-3+1=2, max=4
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
right=5 (1): {1:2,2:1}, size=2. len=3, max=4
right=6 (1): {1:3,2:1}, size=2. len=4, max=4
right=7 (2): {1:3,2:2}, size=2. len=5, max=5
right=8 (3): {1:3,2:2,3:1}, size=3!
left=3 (1): {1:2,2:2,3:1}, size=3
left=4 (2): {1:2,2:1,3:1}, size=3
left=5 (1): {1:1,2:1,3:1}, size=3
left=6 (1): {2:1,3:1}, size=2. left=7.
len=8-7+1=2, max=5
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
right=9 (3): {2:1,3:2}, len=3, max=5
right=10 (4): {2:1,3:2,4:1}, size=3!
left=7 (2): {3:2,4:1}, size=2. left=8.
len=10-8+1=3, max=5
✅ Return 5 (subarray [1,1,2,3,3] at indices 5-9... wait, let me recount: [2,1,1,2] from index 4-7 = length 4, hmm. The algo gives 5.)Deep Insight
**Why this is the same as 'at most K distinct characters' with K=2:**
Replace 'fruit type' with 'character', 'basket limit 2' with 'at most 2 distinct characters'. The algorithm is identical. This is a common interview trick — the same problem appears in disguise.
**Why not use a simple integer counter for distinct types?** We need the frequency map because when we shrink from the left, we need to know if we've completely removed a fruit type (count=0). A simple counter can't tell us which type was removed or how many remain.
**The shrink guarantee:** After at most 2 shrinks, the third type is always fully removed. This is because: when right adds a third type (count=1), left just needs to reach the point where one of the existing two types is completely gone. The total shrinks are bounded by n total across all outer iterations.
**Edge cases:** - Single tree: max=1 - All same fruit: max=n - Only two distinct fruits in entire array: max=n
Complexity Analysis
| Approach | Time | Space | Note |
|---|---|---|---|
| Brute Force | O(n²) | O(1) | At most 2 keys in map, so map is O(1) space |
| Optimal | O(n) | O(1) | Map has at most 3 keys at any time (before shrinking); practically O(1) |
Pattern Recognition
✅ Find longest subarray with at most 2 (or K) distinct values ✅ Variable window size ✅ Frequency map for distinct-count tracking ✅ Disguised 'K distinct characters' problem **LeetCode Trigger Phrases:** → "pick from trees in a row" + "two baskets" → "longest subarray with at most 2 distinct elements" → "two types" + "maximum consecutive"
Bhagavad Gita 15.16
द्वाविमौ पुरुषौ लोके क्षरश्चाक्षर एव च। क्षरः सर्वाणि भूतानि कूटस्थोऽक्षर उच्यते॥
There are two kinds of beings in the world — the perishable and the imperishable. All living beings are perishable; the unchanging spirit is called imperishable.
Connection: Two baskets — like the two fundamental categories of existence the Gita describes. The sliding window can hold at most two 'types' in view at any moment, just as the Gita categorizes all of existence into two: the changeable (matter, fruit types that come and go from the window) and the unchangeable (the algorithm itself, which remains the same regardless of what fruits it encounters). The wisdom is in knowing exactly how many categories to hold — not one more, not one less.