Fruit Into Baskets

In a row of trees, the i-th tree produces fruit with type A[i]. We start at any tree of our choice, then repeatedly perform the following steps:

Add one piece of fruit from this tree to your baskets.
Move to the next tree to the right of the current tree. If there is no tree to the right, stop.

Note that we do not have any choice after the initial choice of starting tree: we must perform step 1, then step 2, then back to step 1, then step 2, and so on until we stop. we have two baskets, and each basket can carry any quantity of fruit, but we want each basket to only carry one type of fruit each. What is the Maximum amount of fruit we can collect with this procedure?

Examples:

Input: A[] = {1, 2, 3, 2, 2}
Output: 4
Explanation: We can collect {2, 3, 2, 2}. If we started at the first tree.
Input: A[] = {1, 2, 1}
Output: 3
Explanation: We can collect {1,2,1}

Table of Content

[Naive Approach] - O(n*n) Time and O(1) Space
[Better Approach] Using Sliding Window - O(n) Time and O(1) Space

[Naive Approach] - O(n*n) Time and O(1) Space

The idea is to start at each tree one by one and try to collect fruits until you cannot put a fruit in either of your two baskets. For every starting position, we keep track of the types of fruits collected using a map or set. If a new fruit type appears and you already have two types in the baskets, you stop collecting. We calculate the total number of fruits collected for that starting tree, and repeat the process for all trees. Finally, we take the maximum among all starting positions.

C++

//Driver Code Starts
#include <bits/stdc++.h>
using namespace std;

//Driver Code Ends

int maxFruits(vector<int>& A) {
    int n = A.size();
    int maxFruitsCollected = 0;

    for (int start = 0; start < n; start++) {
        unordered_map<int, int> basket; // track types of fruits
        int count = 0;

        for (int i = start; i < n; i++) {
            basket[A[i]]++;

            // Stop if more than 2 types
            if (basket.size() > 2) break;

            count++;
        }

        maxFruitsCollected = max(maxFruitsCollected, count);
    }

    return maxFruitsCollected;
}

//Driver Code Starts

int main() {
    vector<int> A = {1, 2, 3, 2, 2};
    cout << maxFruits(A) << endl; 
    return 0;
}

//Driver Code Ends

Java

//Driver Code Starts
import java.util.*;

public class GFG {

//Driver Code Ends

    static int maxFruits(int[] A) {
        int n = A.length;
        int maxFruitsCollected = 0;

        for (int start = 0; start < n; start++) {
            Map<Integer, Integer> basket = new HashMap<>(); // track types of fruits
            int count = 0;

            for (int i = start; i < n; i++) {
                basket.put(A[i], basket.getOrDefault(A[i], 0) + 1);

                // Stop if more than 2 types
                if (basket.size() > 2) break;

                count++;
            }

            maxFruitsCollected = Math.max(maxFruitsCollected, count);
        }

        return maxFruitsCollected;
    }

//Driver Code Starts

    public static void main(String[] args) {
        int[] A = {1, 2, 3, 2, 2};
        System.out.println(maxFruits(A)); 
    }
}

//Driver Code Ends

Python

def maxFruits(A):
    n = len(A)
    maxFruitsCollected = 0

    for start in range(n):
        basket = {}  # track types of fruits
        count = 0

        for i in range(start, n):
            basket[A[i]] = basket.get(A[i], 0) + 1

            # Stop if more than 2 types
            if len(basket) > 2:
                break

            count += 1

        maxFruitsCollected = max(maxFruitsCollected, count)

    return maxFruitsCollected


#Driver Code Starts


A = [1, 2, 3, 2, 2]
print(maxFruits(A))  # Output: 4

#Driver Code Ends

//Driver Code Starts
using System;
using System.Collections.Generic;

class GFG {
//Driver Code Ends

    static int maxFruits(int[] A) {
        int n = A.Length;
        int maxFruitsCollected = 0;

        for (int start = 0; start < n; start++) {
            Dictionary<int, int> basket = new Dictionary<int, int>(); // track types of fruits
            int count = 0;

            for (int i = start; i < n; i++) {
                if (basket.ContainsKey(A[i]))
                    basket[A[i]]++;
                else
                    basket[A[i]] = 1;

                // Stop if more than 2 types
                if (basket.Count > 2) break;

                count++;
            }

            maxFruitsCollected = Math.Max(maxFruitsCollected, count);
        }

        return maxFruitsCollected;
    }

//Driver Code Starts

    static void Main() {
        int[] A = {1, 2, 3, 2, 2};
        Console.WriteLine(maxFruits(A)); 
    }
}

//Driver Code Ends

JavaScript

function maxFruits(A) {
    let n = A.length;
    let maxFruitsCollected = 0;

    for (let start = 0; start < n; start++) {
        let basket = {}; // track types of fruits
        let count = 0;

        for (let i = start; i < n; i++) {
            basket[A[i]] = (basket[A[i]] || 0) + 1;

            // Stop if more than 2 types
            if (Object.keys(basket).length > 2) break;

            count++;
        }

        maxFruitsCollected = Math.max(maxFruitsCollected, count);
    }

    return maxFruitsCollected;
}


//Driver Code Starts
let A = [1, 2, 3, 2, 2];
console.log(maxFruits(A)); 

//Driver Code Ends

Output

[Better Approach] Using Sliding Window - O(n) Time and O(1) Space

The idea is to use a sliding window to keep track of the current sequence of trees containing at most two types of fruits.

Start with two pointers start and end to represent the current window of trees.
Use a hash map to count the fruits in the window (basket[fruit_type] = count).
Expand the end pointer (move right) and add the fruit to the basket.
If the basket contains more than 2 types, shrink the window from the start until we are back to at most 2 types.
Keep updating the maximum window length while sliding.

This way, we scan the array only once, achieving a much more efficient solution than the naive approach.ll trees. Finally, we take the maximum among all starting positions.

C++

//Driver Code Starts
#include <bits/stdc++.h>
using namespace std;

//Driver Code Ends

int maxFruits(vector<int>& A) {
    unordered_map<int, int> basket; // count of fruits in current window
    int start = 0, maxCount = 0;

    for (int end = 0; end < A.size(); end++) {
        basket[A[end]]++;

        // Shrink window if more than 2 types
        while (basket.size() > 2) {
            basket[A[start]]--;
            if (basket[A[start]] == 0)
                basket.erase(A[start]);
            start++;
        }

        // Update maximum fruits collected
        maxCount = max(maxCount, end - start + 1);
    }

    return maxCount;
}

//Driver Code Starts

int main() {
    vector<int> A = {1, 2, 3, 2, 2};
    cout << maxFruits(A) << endl; 
    return 0;
}

//Driver Code Ends