Fruit Into Baskets - Sliding Window - Visualization - Visualization

Sliding Window & Two Pointer Problems

Contents

ProblemExamplesSolutionAlgorithmCodeTimeSpace

Problem Statement❯

You are visiting a row of trees, where each tree produces a specific type of fruit represented by integers in an array fruits.

You only have two baskets, and each basket can only hold one type of fruit.

Your goal is to collect the maximum number of fruits by picking from a starting tree and moving to the right, collecting exactly one fruit from each tree — but only two types of fruit total across both baskets.

Return the length of the longest subarray containing at most two different types of fruits.

Input: fruits = [1,2,1,2,3] → Output: 4 (Pick fruits [1,2,1,2])

Examples❯

fruits Output Description
[1,2,1,2,3] 4 Max window with at most two types: [1,2,1,2]
[0,1,2,2] 3 Max window is [1,2,2] — contains at most 2 types
[1,2,3,2,2] 4 Max window is [2,3,2,2] — still only 2 types
[1,2,3,4,5] 2 Any two adjacent values form the longest valid window
[1,1,1,1] 4 Only one type of fruit, can take all of them
[1] 1 Single fruit type and only one fruit — window length is 1
[] 0 Empty array — no fruits to collect
[1,2,1,3,4,3,5,1,2] 3 Max window with 2 fruit types is [1,2,1] before hitting a 3
[3,3,3,1,2,1,1,2,3,3,4] 5 Longest valid window is [1,2,1,1,2] with 2 fruit types
[0,0,1,1,2,2,3,3] 4 Max valid subarray is [1,1,2,2] before third type enters

Solution❯

Understanding the Problem

Imagine you're walking along a row of fruit trees, and each tree gives exactly one fruit. These fruits are represented by numbers in an array — for example, [1, 2, 1, 2, 3].

You have only two baskets, and each basket can only hold one type of fruit. So, you can pick any number of fruits, but only two types in total.

Your goal is to start from any tree and go right, collecting fruits continuously — but never collecting more than two types. You need to find the maximum number of fruits you can collect under this rule.

In simpler terms, we’re looking for the length of the longest subarray that contains at most two different numbers.

Step-by-Step Solution with Example

Step 1: Start with an example

Let’s take the input fruits = [1, 2, 1, 2, 3].

This means:

  • Tree 0 gives fruit 1
  • Tree 1 gives fruit 2
  • Tree 2 gives fruit 1
  • Tree 3 gives fruit 2
  • Tree 4 gives fruit 3

Step 2: Use a sliding window

We use two pointers, start and end, to create a window of valid fruit collection. We also use a hashmap to keep track of how many fruits of each type we currently have.

Step 3: Expand the window

We start with start = 0 and iterate end over the array. Every time we move end to the right, we add that fruit type to our hashmap and increase its count.

Step 4: Shrink the window if needed

If the hashmap has more than two keys (fruit types), we shrink the window from the left by moving start forward and updating the counts. We stop shrinking once only two fruit types remain.

Step 5: Track the max

Each time the window is valid (i.e., has at most two fruit types), we check if the window length is the largest we’ve seen so far and update maxFruits.

Step 6: Apply to our example

Let’s walk through the array:

  • end = 0: [1] → types: {1} → valid → maxFruits = 1
  • end = 1: [1,2] → types: {1,2} → valid → maxFruits = 2
  • end = 2: [1,2,1] → types: {1,2} → valid → maxFruits = 3
  • end = 3: [1,2,1,2] → types: {1,2} → valid → maxFruits = 4
  • end = 4: [1,2,1,2,3] → types: {1,2,3} → invalid → shrink from left

Now shrink:

  • Remove 1 (from index 0), count of 1 becomes 1 → still 3 types
  • Remove 2 (from index 1), count of 2 becomes 1 → still 3 types
  • Remove 1 (from index 2), count of 1 becomes 0 → remove it → now we have only {2,3}

Window is now [2,3] → length = 2 → maxFruits stays at 4

Edge Cases

  • Empty array: No fruits to collect → return 0.
  • Only one type of fruit: e.g., [4,4,4] → all valid → return length of array.
  • Exactly two types but alternating: e.g., [1,2,1,2,1] → entire array is valid.
  • More than two types at start: e.g., [1,2,3] → shrink immediately.

Final Thoughts

This is a classic use of the sliding window pattern. We dynamically adjust our window to always respect the rule of having no more than two fruit types, and we keep track of the largest valid window we find.

By visualizing the problem as walking along trees and managing our baskets like a limited storage, beginners can easily relate and understand the approach.

Always ask: “Is my current window valid?” — If not, shrink it until it is. Then, check if it's the biggest valid window we've seen so far.

Algorithm Steps❯

  1. Initialize a hash map fruitCount to store the count of each fruit type in the current window.
  2. Set two pointers: start (window start) and end (current tree index).
  3. Initialize maxFruits = 0 to track the maximum number of fruits collected.
  4. Loop through the array using end from 0 to the end of the array:
  5. → Add fruits[end] to fruitCount (increase its count).
  6. → While the size of fruitCount is greater than 2 (more than two fruit types):
  7.    • Decrease count of fruits[start] and if it becomes 0, remove it from the map.
  8.    • Increment start to shrink the window.
  9. → Update maxFruits = max(maxFruits, end - start + 1).
  10. After processing all trees, return maxFruits as the result.

Code

C
C++
Python
Java
JS
Go
Rust
Kotlin
Swift
TS
#include <stdio.h>
#include <stdlib.h>

int maxFruitCount(int* fruits, int size) {
    int count[10000] = {0}; // Assuming fruit types are within 0-9999
    int start = 0, maxFruits = 0, distinct = 0;

    for (int end = 0; end < size; end++) {
        if (count[fruits[end]] == 0) distinct++;
        count[fruits[end]]++;

        while (distinct > 2) {
            count[fruits[start]]--;
            if (count[fruits[start]] == 0) distinct--;
            start++;
        }

        int currentLength = end - start + 1;
        if (currentLength > maxFruits) maxFruits = currentLength;
    }

    return maxFruits;
}

int main() {
    int fruits[] = {1, 2, 1, 2, 3};
    int size = sizeof(fruits) / sizeof(fruits[0]);
    int result = maxFruitCount(fruits, size);
    printf("Maximum fruits collected: %d\n", result); // Output: 4
    return 0;
}

Time Complexity❯

CaseTime ComplexityExplanation
Best CaseO(n)The algorithm uses a sliding window and visits each fruit in the array exactly once. Even in the best case, it still has to scan all elements to find the longest valid window.
Average CaseO(n)On average, each fruit is added and possibly removed once from the hash map. The window expands and contracts efficiently while maintaining at most two fruit types.
Worst CaseO(n)In the worst case, the algorithm still visits each element once. The window slides from left to right, and the map operations remain bounded due to the constraint of only two fruit types.

Space Complexity❯

O(1)

Explanation: At most, the hash map will store counts for two types of fruits, which is constant. Other variables (like pointers and counters) also consume constant space.


Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.

Loading comments...