Fruits Into Baskets

▶

Steps

setup

Initialize variables

Set up frequency array, pointers, distinct count, and max length before processing fruits.

💡 Initialization prepares all necessary variables to track fruit counts and window boundaries.

Line:

max_fruit = max(fruits) if fruits else 0
freq = [0] * (max_fruit + 1)
left = 0
distinct = 0
max_length = 0

💡 We start with an empty window and no fruits counted.

expand

Expand right pointer to 0

Move right pointer to index 0, include fruit 1, update frequency and distinct count.

💡 Adding the first fruit starts building the window and tracking fruit types.

Line:

if freq[fruits[right]] == 0:
    distinct += 1
freq[fruits[right]] += 1

💡 Including a new fruit type increases the distinct count.

record_answer

Update max_length after first expansion

Calculate window size (right - left + 1 = 1) and update max_length to 1.

💡 Tracking the longest valid window so far is essential to find the final answer.

Line:

max_length = max(max_length, right - left + 1)

💡 The window size is recorded as the best answer so far.

expand

Expand right pointer to 1

Move right pointer to index 1, include fruit 2, update frequency and distinct count.

💡 Adding a different fruit type increases distinct count but still valid since ≤ 2.

Line:

if freq[fruits[right]] == 0:
    distinct += 1
freq[fruits[right]] += 1

💡 Window now contains two distinct fruit types, still valid.

record_answer

Update max_length after second expansion

Calculate window size (2) and update max_length to 2.

💡 The window is larger and still valid, so update the answer.

Line:

max_length = max(max_length, right - left + 1)

💡 Answer grows as window expands with valid fruit types.

expand

Expand right pointer to 2

Move right pointer to index 2, include fruit 1, update frequency. Distinct count remains 2.

💡 Adding a fruit already in the window does not increase distinct count.

Line:

if freq[fruits[right]] == 0:
    distinct += 1
freq[fruits[right]] += 1

💡 Window still valid with two fruit types.

record_answer

Update max_length after third expansion

Calculate window size (3) and update max_length to 3.

💡 The window now covers the entire array with valid fruit types.

Line:

max_length = max(max_length, right - left + 1)

💡 Longest valid window found so far is the entire array.

expand

Attempt to expand right pointer beyond array length

Try to move right pointer beyond the last index, but array ends so no expansion occurs.

💡 No more fruits to add, so expansion stops here.

💡 Window expansion phase ends as array is fully processed.

shrink

Shrink window if distinct fruits exceed 2 (not needed here)

Check if distinct count exceeds 2 to shrink window from left. Here distinct count is 2, so no shrinking.

💡 Shrinking is triggered only when distinct count > 2.

Line:

while distinct > 2:
    freq[fruits[left]] -= 1
    if freq[fruits[left]] == 0:
        distinct -= 1
    left += 1

💡 Window remains valid, no need to shrink.

reconstruct

End of array reached, return answer

All fruits processed, return max_length which is 3.

💡 The final answer is the size of the longest window with at most two distinct fruits.

Line:

return max_length

💡 The algorithm successfully found the longest valid window.

def totalFruit(fruits):
    max_fruit = max(fruits) if fruits else 0  # STEP 1
    freq = [0] * (max_fruit + 1)              # STEP 1
    left = 0                                  # STEP 1
    distinct = 0                              # STEP 1
    max_length = 0                            # STEP 1
    for right in range(len(fruits)):
        if freq[fruits[right]] == 0:          # STEP 2,4,6
            distinct += 1
        freq[fruits[right]] += 1              # STEP 2,4,6
        while distinct > 2:                    # STEP 3
            freq[fruits[left]] -= 1           # STEP 3
            if freq[fruits[left]] == 0:
                distinct -= 1
            left += 1
        max_length = max(max_length, right - left + 1)  # STEP 3,5,7
    return max_length                          # STEP 8

if __name__ == '__main__':
    print(totalFruit([1,2,1]))  # Output: 3

📊

Fruits Into Baskets - Watch the Algorithm Execute, Step by Step

Watching the algorithm step-by-step reveals how the window boundaries move and how the frequency counts and distinct fruit count change, making the logic behind the sliding window approach crystal clear.

expand

L ▼

1

0

2

1

1

2

Metric: 0

Answer: 0

expand

L=R

1

0

2

1

1

2

Window: [1]

Metric: 1

Answer: 0

record_answer

L=R

1

0

2

1

1

2

Window: [1]

Metric: 1

Answer: 1

expand

L ▼

1

0

R ▼

2

1

1

2

Window: [1, 2]

Metric: 2

Answer: 1

record_answer

L ▼

1

0

R ▼

2

1

1

2

Window: [1, 2]

Metric: 2

Answer: 2

expand

L ▼

1

0

2

1

R ▼

1

2

Window: [1, 2, 1]

Metric: 3

Answer: 2

record_answer

L ▼

1

0

2

1

R ▼

1

2

Window: [1, 2, 1]

Metric: 3

Answer: 3

expand

L ▼

1

0

2

1

R ▼

1

2

Window: [1, 2, 1]

Metric: 3

Answer: 3

shrink

L ▼

1

0

2

1

R ▼

1

2

Window: [1, 2, 1]

Metric: 3

Answer: 3

record_answer

L ▼

1

0

2

1

R ▼

1

2

Window: [1, 2, 1]

Metric: 3

Answer: 3

Key Takeaways

✓ The sliding window expands greedily until the distinct fruit count exceeds two, then shrinks from the left to restore validity.

This dynamic adjustment is hard to grasp from code alone but is clear when watching the window boundaries move.

✓ Tracking frequency counts allows efficient detection of when a fruit type leaves the window, reducing distinct count.

Understanding frequency updates clarifies why and when the window shrinks.

✓ The maximum window size is updated only when the window is valid, ensuring the final answer is the longest subarray with at most two fruit types.

Seeing the answer update visually helps connect the window size to the problem goal.

Practice

1. You are given an array of integers and a fixed window size k. The task is to find the contiguous subarray of size k that has the maximum sum. Which of the following algorithmic approaches guarantees an optimal solution with linear time complexity?

easy

A. Brute force approach that computes the sum of every subarray of size k using nested loops.

B. Sliding window technique that maintains a running sum by adding the next element and removing the first element of the previous window.

C. Dynamic programming approach that stores maximum sums for all subproblems of varying sizes.

D. Greedy approach that picks the largest element in each window without considering previous sums.

Solution

1. Step 1: Understand the problem constraints

   The problem requires finding the maximum sum of any contiguous subarray of fixed size k, which suggests a need for efficient window-based processing.

2. Step 2: Evaluate algorithmic approaches

   Brute force (A) is correct but inefficient (O(n*k)). Dynamic programming (C) is unnecessary overhead since subproblems overlap trivially. Greedy (D) fails because local max elements do not guarantee global max sum. Sliding window (B) efficiently updates the sum in O(n) time by adding the new element and removing the old one.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Sliding window updates sum in O(1) per step [OK]

Hint: Sliding window updates sum in O(1) per step [OK]

Common Mistakes:

• Confusing greedy picking of max elements with max sum subarray
• Thinking DP is needed for fixed-size window sums
• Assuming brute force is optimal

2. Consider the following Python function implementing the optimal sliding window approach to find the minimum length of a subarray containing duplicate cards. What is the returned value when calling minimumCardPickup([1, 2, 3, 2])?

def minimumCardPickup(cards):
    last_seen = {}
    left = 0
    min_len = float('inf')
    for right, card in enumerate(cards):
        if card in last_seen and last_seen[card] >= left:
            left = last_seen[card] + 1
        last_seen[card] = right
        if right - left + 1 > 1:
            min_len = min(min_len, right - left + 1)
    return min_len if min_len != float('inf') else -1

easy

A. 2

B. 4

C. -1

D. 3

Solution

1. Step 1: Trace iterations for input [1, 2, 3, 2]

   Indices: 0->1, 1->2, 2->3, 3->2. At right=3, card=2 is duplicate with last_seen[2]=1 ≥ left=0, so left moves to 2.

2. Step 2: Calculate min_len updates

   Subarray lengths considered: from indices 1 to 3 is length 3, but after left update, window is from 2 to 3 length 2, min_len updated to 2.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Minimum subarray with duplicate '2' is [3,2] length 2 [OK]

Hint: Update left pointer on duplicate to shrink window [OK]

Common Mistakes:

• Off-by-one error in window length
• Not updating left pointer correctly

3. Consider the following Python function that counts the number of contiguous subarrays where the product of all elements is less than k. What is the returned value when calling numSubarrayProductLessThanK([10, 5, 2, 6], 100)?

def numSubarrayProductLessThanK(nums, k):
    if k <= 1:
        return 0
    product = 1.0
    count = 0
    left = 0
    for right in range(len(nums)):
        product *= nums[right]
        while product >= k and left <= right:
            product /= nums[left]
            left += 1
        count += right - left + 1
    return count

easy

A. 8

B. 7

C. 9

D. 10

Solution

1. Step 1: Trace product and window boundaries

   Iterate right pointer: - right=0: product=10 <100, count=1 - right=1: product=50 <100, count=1+2=3 - right=2: product=100 ≥100, shrink window: product/=10=10, left=1, count=3+(2-1+1)=5 - right=3: product=10*6=60 <100, count=5+(3-1+1)=8

2. Step 2: Final count

   Total count is 8 valid subarrays.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Count matches expected output 8 [OK]

Hint: Count increments by window size each iteration [OK]

Common Mistakes:

• Off-by-one in count increment
• Not shrinking window correctly

4. What is the time complexity of the optimal sliding window solution for the Maximum Points You Can Obtain from Cards problem, and why?

medium

A. O(n) because it computes the total sum once and slides a window of size n-k across the array once.

B. O(k^2) because it tries all combinations of picking cards from ends.

C. O(n*k) because it sums subarrays of size n-k repeatedly inside a loop of size k.

D. O(n log n) because it sorts the array before applying the sliding window.

Solution

1. Step 1: Analyze the operations

   The algorithm sums all elements once (O(n)) and then slides a window of size n-k across the array once, updating sums in O(1) per step.

2. Step 2: Confirm no nested loops or sorting

   There is no nested iteration or sorting, so total time is linear in n.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Single pass sliding window and sum -> O(n) time [OK]

Hint: Sliding window updates in O(1) per step yield O(n) total [OK]

Common Mistakes:

• Confusing repeated sum computations as O(n*k)
• Assuming sorting is needed
• Thinking brute force complexity applies

5. The following code attempts to count the number of contiguous subarrays where the product of all elements is less than k. Identify the line containing the subtle bug that causes incorrect results or infinite loops.

def numSubarrayProductLessThanK(nums, k):
    if k <= 1:
        return 0
    product = 1
    count = 0
    left = 0
    for right in range(len(nums)):
        product *= nums[right]
        while product >= k and left <= right:
            product = product // nums[left]
            left += 1
        count += right - left + 1
    return count

medium

A. Line 3: Using integer 1 instead of floating point 1.0 for product initialization.

B. Line 11: Incrementing count by 'right - left + 1' instead of 1.

C. Line 2: Returning 0 when k <= 1.

D. Line 9: Using integer division '//' instead of floating point division '/' when updating product.

Solution

1. Step 1: Identify division operation

   Line 9 uses integer division '//' which truncates product, causing incorrect product updates.

2. Step 2: Consequences of integer division

   Integer division can cause product to never reach below k properly, leading to infinite loops or wrong counts.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Replacing '//' with '/' fixes product update and loop termination [OK]

Hint: Integer division breaks product update -> infinite loop [OK]

Common Mistakes:

• Using integer division instead of float
• Incorrect count increment