Fruit Into Baskets - Sliding Window Technique

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])

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.

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.

#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;
}

#include <iostream>
#include <unordered_map>
using namespace std;

int maxFruitCount(const vector<int>& fruits) {
    unordered_map<int, int> fruitCount;
    int start = 0, maxFruits = 0;

    for (int end = 0; end < (int)fruits.size(); ++end) {
        fruitCount[fruits[end]]++;

        while (fruitCount.size() > 2) {
            fruitCount[fruits[start]]--;
            if (fruitCount[fruits[start]] == 0) {
                fruitCount.erase(fruits[start]);
            }
            start++;
        }

        maxFruits = max(maxFruits, end - start + 1);
    }

    return maxFruits;
}

int main() {
    vector<int> fruits = {1, 2, 1, 2, 3};
    cout << "Maximum fruits collected: " << maxFruitCount(fruits) << endl; // 4
    return 0;
}

def max_fruit_count(fruits):
    fruit_count = {}
    start = 0
    max_fruits = 0

    for end in range(len(fruits)):
        fruit = fruits[end]
        fruit_count[fruit] = fruit_count.get(fruit, 0) + 1

        while len(fruit_count) > 2:
            start_fruit = fruits[start]
            fruit_count[start_fruit] -= 1
            if fruit_count[start_fruit] == 0:
                del fruit_count[start_fruit]
            start += 1

        max_fruits = max(max_fruits, end - start + 1)

    return max_fruits

fruits = [1, 2, 1, 2, 3]
result = max_fruit_count(fruits)
print(f"Maximum fruits collected: {result}")  # Output: 4

import java.util.HashMap;
import java.util.Map;

public class FruitIntoBaskets {
    public static int maxFruitCount(int[] fruits) {
        Map<Integer, Integer> fruitCount = new HashMap<>();
        int start = 0, maxFruits = 0;

        for (int end = 0; end < fruits.length; end++) {
            fruitCount.put(fruits[end], fruitCount.getOrDefault(fruits[end], 0) + 1);

            while (fruitCount.size() > 2) {
                int startFruit = fruits[start];
                fruitCount.put(startFruit, fruitCount.get(startFruit) - 1);
                if (fruitCount.get(startFruit) == 0) {
                    fruitCount.remove(startFruit);
                }
                start++;
            }

            maxFruits = Math.max(maxFruits, end - start + 1);
        }

        return maxFruits;
    }

    public static void main(String[] args) {
        int[] fruits = {1, 2, 1, 2, 3};
        int result = maxFruitCount(fruits);
        System.out.println("Maximum fruits collected: " + result); // Output: 4
    }
}

function maxFruitCount(fruits) {
  const fruitCount = new Map();
  let start = 0;
  let maxFruits = 0;

  for (let end = 0; end < fruits.length; end++) {
    const fruit = fruits[end];
    fruitCount.set(fruit, (fruitCount.get(fruit) || 0) + 1);

    while (fruitCount.size > 2) {
      const startFruit = fruits[start];
      fruitCount.set(startFruit, fruitCount.get(startFruit) - 1);
      if (fruitCount.get(startFruit) === 0) {
        fruitCount.delete(startFruit);
      }
      start++;
    }

    maxFruits = Math.max(maxFruits, end - start + 1);
  }

  return maxFruits;
}

const fruits = [1, 2, 1, 2, 3];
console.log("Maximum fruits collected:", maxFruitCount(fruits)); // Output: 4

package main

import "fmt"

func maxFruitCount(fruits []int) int {
    fruitCount := make(map[int]int)
    start, maxFruits := 0, 0

    for end := 0; end < len(fruits); end++ {
        fruitCount[fruits[end]]++

        for len(fruitCount) > 2 {
            fruitCount[fruits[start]]--
            if fruitCount[fruits[start]] == 0 {
                delete(fruitCount, fruits[start])
            }
            start++
        }

        if currentLength := end - start + 1; currentLength > maxFruits {
            maxFruits = currentLength
        }
    }
    return maxFruits
}

func main() {
    fruits := []int{1, 2, 1, 2, 3}
    result := maxFruitCount(fruits)
    fmt.Println("Maximum fruits collected:", result) // Output: 4
}

use std::collections::HashMap;

fn max_fruit_count(fruits: &[i32]) -> usize {
    let mut fruit_count = HashMap::new();
    let mut start = 0;
    let mut max_fruits = 0;

    for end in 0..fruits.len() {
        *fruit_count.entry(fruits[end]).or_insert(0) += 1;

        while fruit_count.len() > 2 {
            let start_fruit = fruits[start];
            if let Some(count) = fruit_count.get_mut(&start_fruit) {
                *count -= 1;
                if *count == 0 {
                    fruit_count.remove(&start_fruit);
                }
            }
            start += 1;
        }

        max_fruits = max_fruits.max(end - start + 1);
    }

    max_fruits
}

fn main() {
    let fruits = vec![1, 2, 1, 2, 3];
    let result = max_fruit_count(&fruits);
    println!("Maximum fruits collected: {}", result); // Output: 4
}

fun maxFruitCount(fruits: IntArray): Int {
    val fruitCount = mutableMapOf<Int, Int>()
    var start = 0
    var maxFruits = 0

    for (end in fruits.indices) {
        fruitCount[fruits[end]] = fruitCount.getOrDefault(fruits[end], 0) + 1

        while (fruitCount.size > 2) {
            val startFruit = fruits[start]
            fruitCount[startFruit] = fruitCount[startFruit]!! - 1
            if (fruitCount[startFruit] == 0) {
                fruitCount.remove(startFruit)
            }
            start++
        }

        maxFruits = maxOf(maxFruits, end - start + 1)
    }

    return maxFruits
}

fun main() {
    val fruits = intArrayOf(1, 2, 1, 2, 3)
    val result = maxFruitCount(fruits)
    println("Maximum fruits collected: $result") // Output: 4
}

func maxFruitCount(_ fruits: [Int]) -> Int {
    var fruitCount = [Int: Int]()
    var start = 0
    var maxFruits = 0

    for end in 0 ..< fruits.count {
        fruitCount[fruits[end], default: 0] += 1

        while fruitCount.count > 2 {
            fruitCount[fruits[start]]! -= 1
            if fruitCount[fruits[start]] == 0 {
                fruitCount.removeValue(forKey: fruits[start])
            }
            start += 1
        }

        maxFruits = max(maxFruits, end - start + 1)
    }

    return maxFruits
}

let fruits = [1, 2, 1, 2, 3]
let result = maxFruitCount(fruits)
print("Maximum fruits collected: \(result)") // Output: 4

function maxFruitCount(fruits: number[]): number {
  const fruitCount: { [key: number]: number } = {};
  let start = 0;
  let maxFruits = 0;

  for (let end = 0; end < fruits.length; end++) {
    const fruit = fruits[end];
    fruitCount[fruit] = (fruitCount[fruit] || 0) + 1;

    while (Object.keys(fruitCount).length > 2) {
      const startFruit = fruits[start];
      fruitCount[startFruit]--;
      if (fruitCount[startFruit] === 0) {
        delete fruitCount[startFruit];
      }
      start++;
    }

    maxFruits = Math.max(maxFruits, end - start + 1);
  }

  return maxFruits;
}

const fruits = [1, 2, 1, 2, 3];
const result = maxFruitCount(fruits);
console.log(`Maximum fruits collected: ${result}`); // Output: 4

Time complexity

Space complexity

O(1)

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.