Fruits Into Baskets

📋

Problem

Imagine you have two baskets and want to collect fruits from a row of trees, but you can only carry two types of fruits at a time. How do you pick the longest stretch of trees to maximize your haul?

You are given an integer array fruits where fruits[i] represents the type of fruit on the i-th tree. You have two baskets, and each basket can only hold one type of fruit. You want to pick fruits from a contiguous segment of trees such that you only have at most two different types of fruits in total. Return the length of the longest such segment.

1 ≤ fruits.length ≤ 10^50 ≤ fruits[i] < fruits.length

Edge cases: All fruits are the same type → output is length of entire arrayArray length is 1 → output is 1Array with all distinct fruits → output is 2 (since only two baskets)

</>

IDE

def totalFruit(fruits: list[int]) -> int:public int totalFruit(int[] fruits)int totalFruit(vector<int> &fruits)function totalFruit(fruits)

def totalFruit(fruits):
    # Write your solution here
    pass

class Solution {
    public int totalFruit(int[] fruits) {
        // Write your solution here
        return 0;
    }
}

#include <vector>
using namespace std;

int totalFruit(vector<int> &fruits) {
    // Write your solution here
    return 0;
}

function totalFruit(fruits) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: Length greater than 2 for all distinct fruits inputNot enforcing the 'at most two distinct fruit types' constraint properly.✅ Shrink the window from the left when distinct fruit count exceeds two by decrementing counts and moving left pointer.

Wrong: Incorrect length due to off-by-one errors in window size calculationIncorrectly updating left pointer or window size after shrinking.✅ Ensure window size is calculated as right - left + 1 and update pointers carefully after decrementing counts.

Wrong: TLE on large inputUsing brute force nested loops instead of sliding window.✅ Implement sliding window with frequency map for O(n) time complexity.

Wrong: Zero or crash on empty inputNot handling empty array input explicitly.✅ Add a check at start to return 0 if input array is empty.

Wrong: Length 1 for input with multiple fruits but only one typeIncorrectly resetting window or counts when only one fruit type exists.✅ Allow window to expand fully when only one fruit type is present.

✓

Test Cases

Think about edge cases like empty input or all fruits identical.

Consider tricky cases that break greedy or naive approaches.

Prepare for large inputs; optimize your solution to linear time.

t1_01basic

Input{"fruits":[1,2,1]}

Expected3

⏱ Performance - must finish in 2000ms

All fruits can be picked since there are only two types: 1 and 2.

💡 Think about maintaining a window with at most two distinct fruit types.

💡 Use a sliding window and a frequency map to track fruit counts.

💡 Expand the window until more than two types appear, then shrink from left.

Why it failed: Returned incorrect length; likely not maintaining at most two distinct fruits in window. Fix by tracking fruit counts and shrinking window when distinct count exceeds two.

✓ Correctly handles the canonical example with two fruit types.

t1_02basic

Input{"fruits":[0,1,2,2]}

Expected3

⏱ Performance - must finish in 2000ms

Longest segment with at most two fruit types is [1,2,2] with length 3.

💡 Check how the window adjusts when a third fruit type appears.

💡 Sliding window should shrink from the left to remove excess fruit types.

💡 Track counts carefully to know when to shrink the window.

Why it failed: Incorrect output due to not shrinking window properly when third fruit type appears. Fix by decrementing counts and moving left pointer until only two types remain.

✓ Correctly finds longest segment with at most two fruit types.

t2_01edge

Input{"fruits":[]}

Expected0

⏱ Performance - must finish in 2000ms

Empty array means no fruits to pick, so result is 0.

💡 Consider what happens when input array is empty.

💡 Your code should handle zero-length input gracefully.

💡 Return 0 immediately if no fruits are present.

Why it failed: Code crashes or returns non-zero for empty input. Fix by adding a check for empty array and returning 0.

✓ Handles empty input correctly by returning 0.

t2_02edge

Input{"fruits":[5]}

Expected1

⏱ Performance - must finish in 2000ms

Single fruit means longest segment is length 1.

💡 Check behavior when input has only one fruit.

💡 Window should at least include that single fruit.

💡 Return 1 for single-element arrays.

Why it failed: Returns 0 or incorrect length for single-element input. Fix by ensuring window initialization includes single element.

✓ Correctly returns 1 for single fruit input.

t2_03edge

Input{"fruits":[1,2,3,4,5]}

Expected2

⏱ Performance - must finish in 2000ms

All fruits distinct; max segment with at most two types is length 2.

💡 When all fruits are distinct, max window size is 2.

💡 Sliding window must shrink immediately when third distinct fruit appears.

💡 Check that window size never exceeds 2 in such cases.

Why it failed: Returns length greater than 2 for all distinct fruits. Fix by enforcing window size limit to at most two distinct fruit types.

✓ Correctly limits window size to 2 when all fruits are distinct.

t3_01corner

Input{"fruits":[1,2,1,3,4,3,5,1,2]}

Expected3

⏱ Performance - must finish in 2000ms

Greedy approach picking first two types fails; longest valid segment is [1,2,1] length 3.

💡 Beware of greedy approaches that fix first two fruit types and ignore others.

💡 Sliding window must dynamically adjust fruit types as window moves.

💡 Use a frequency map and two pointers to track current window fruit types.

Why it failed: Greedy approach fails by fixing first two fruit types and missing longer segments. Fix by implementing sliding window that adjusts fruit types dynamically.

✓ Correctly handles dynamic fruit types and finds longest valid segment.

t3_02corner

Input{"fruits":[1,2,2,2,3,3,3,2,2]}

Expected8

⏱ Performance - must finish in 2000ms

Tests confusion between 0/1 and unbounded picking; longest segment is [2,2,2,3,3] length 5.

💡 Remember you can pick unlimited fruits of each type within the window.

💡 Do not limit count of each fruit type to one.

💡 Track counts and shrink window only when more than two types appear.

Why it failed: Mistakenly limits count of each fruit type to one. Fix by allowing multiple fruits of same type and only limiting distinct types to two.

✓ Correctly counts multiple fruits of same type within window.

t3_03corner

Input{"fruits":[1,1,2,3,2,2,1,1]}

Expected4

⏱ Performance - must finish in 2000ms

Off-by-one errors in shrinking window cause incorrect max length; longest segment is [2,3,2,2,1] length 5.

💡 Check carefully how you move left pointer when shrinking window.

💡 Ensure you update counts and distinct types correctly after shrinking.

💡 Verify window size calculation matches indices after adjustments.

Why it failed: Off-by-one error in window size calculation or pointer movement. Fix by carefully updating left pointer and counts when shrinking window.

✓ Correctly manages window boundaries and counts for max length.

t4_01performance

Input{"fruits":[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99]}

Expectednull

⏱ Performance - must finish in 2000ms

Input size n=100 with all distinct fruits; O(n) solution must complete within 2 seconds.

💡 Brute force O(n^2) will time out on large input.

💡 Use sliding window with frequency map for O(n) time complexity.

💡 Maintain two pointers and update counts efficiently.

Why it failed: Brute force or nested loops cause TLE on large input. Fix by implementing O(n) sliding window approach.

✓ Algorithm runs in O(n) time and passes performance test.

Practice

1. Consider the following code snippet implementing the optimal sliding window approach to check if s2 contains a permutation of s1. Given s1 = "ab" and s2 = "eidbaooo", what is the return value of the function?

easy

A. True

B. Raises an IndexError

C. False

D. Returns None

Solution

1. Step 1: Trace window expansion and counts

   For s1 = "ab", count array has counts for 'a' and 'b'. Sliding window moves over s2 = "eidbaooo". When window covers substring "ba" starting at index 3, window_count matches count, so formed == required.

2. Step 2: Confirm return value

   At this point, function returns True because a permutation of s1 is found in s2.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Substring "ba" is a permutation of "ab" [OK]

Hint: Check substring "ba" matches "ab" permutation [OK]

Common Mistakes:

• Off-by-one errors in window size
• Forgetting to return True when formed == required

2. You are given an array of positive integers and a positive integer k. The task is to count the number of contiguous subarrays where the product of all elements is less than k. Which algorithmic approach guarantees an optimal solution with linear time complexity?

easy

A. Use a sliding window with two pointers to dynamically adjust the window size while maintaining the product less than k.

B. Use a brute force nested loop to check all subarrays and count those with product less than k.

C. Use dynamic programming to store products of subarrays and count valid ones.

D. Use a greedy approach to pick elements until the product exceeds k, then restart.

Solution

1. Step 1: Understand problem constraints

   The problem requires counting subarrays with product less than k efficiently.

2. Step 2: Identify optimal approach

   Sliding window with two pointers maintains a variable-size window and updates product in O(1) per step, achieving O(n) time.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sliding window adjusts window size dynamically -> O(n) time [OK]

Hint: Sliding window handles variable-size subarrays efficiently [OK]

Common Mistakes:

• Thinking brute force is optimal
• Confusing DP with product constraints

3. The following code attempts to find the length of the longest substring with at most k distinct characters. Identify the bug that causes incorrect results on some inputs.

from collections import OrderedDict

def length_of_longest_substring_k_distinct(s: str, k: int) -> int:
    if k == 0 or not s:
        return 0
    left = 0
    max_length = 0
    last_seen = OrderedDict()
    for right, char in enumerate(s):
        if char in last_seen:
            del last_seen[char]
        last_seen[char] = right
        max_length = max(max_length, right - left + 1)
        if len(last_seen) > k:
            _, idx = last_seen.popitem(last=False)
            left = idx + 1
    return max_length

medium

A. Not handling the case when k is zero or string is empty

B. Deleting the character from last_seen before re-inserting it

C. Updating max_length before shrinking the window when distinct chars exceed k

D. Using OrderedDict instead of a frequency map

Solution

1. Step 1: Locate max_length update position

   max_length is updated before shrinking the window when distinct chars exceed k, so invalid windows are counted.

2. Step 2: Understand impact

   This causes max_length to include substrings with more than k distinct characters, violating constraints.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Moving max_length update after shrinking fixes correctness [OK]

Hint: Update max_length only after ensuring window is valid [OK]

Common Mistakes:

• Updating max_length too early before shrinking window
• Confusing order of operations in sliding window

4. Identify the bug in the following code snippet for the Maximum Points You Can Obtain from Cards problem:

medium

A. Line 7: Loop range should start from k instead of window_size.

B. Line 4: Incorrect initial sum calculation; should sum last k elements instead of first window_size.

C. Line 9: The condition should be current_sum > min_subarray_sum instead of <.

D. Line 3: Incorrect calculation of window_size; should be n - k instead of k.

Solution

1. Step 1: Understand window size meaning

   The window represents the subarray to exclude, which must be length n - k, not k.

2. Step 2: Identify impact of wrong window size

   Using k as window size causes the algorithm to exclude wrong subarray length, leading to incorrect results.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Correct window size is n - k for the sliding window [OK]

Hint: Window size must be n - k, not k [OK]

Common Mistakes:

• Confusing window size with k instead of n-k
• Incorrect loop boundaries
• Wrong comparison operator in min update

5. What is the time complexity of the optimal sliding window algorithm that uses a last seen map to find the minimum length subarray containing duplicates in an array of length n?

medium

A. O(n) for iteration plus O(n) for auxiliary space, total O(n)

B. O(n log n) due to map lookups and updates

C. O(n) because each element is visited at most twice by left and right pointers

D. O(n²) due to nested loops scanning subarrays

Solution

1. Step 1: Identify iteration cost

   The algorithm iterates over the array once with right pointer, and left pointer only moves forward, so each element is visited at most twice, resulting in O(n) time.

2. Step 2: Consider map operations and space

   Map lookups and updates are O(1) average. Space used is O(n) for last_seen map storing indices.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Each element visited at most twice by pointers -> O(n) time [OK]

Hint: Sliding window with hashmap -> linear time and space [OK]

Common Mistakes:

• Confusing map operations as O(log n)
• Assuming nested loops cause O(n²)