Fruit Into Baskets - Practice Coding Problems

Fruit Into Baskets - Problem

You are visiting a farm that has a single row of fruit trees arranged from left to right. The trees are represented by an integer array fruits where fruits[i] is the type of fruit the i-th tree produces.

You want to collect as much fruit as possible. However, the owner has some strict rules that you must follow:

You only have two baskets, and each basket can only hold a single type of fruit. There is no limit on the amount of fruit each basket can hold.
Starting from any tree of your choice, you must pick exactly one fruit from every tree (including the start tree) while moving to the right.
The picked fruits must fit in one of your baskets. Once you reach a tree with fruit that cannot fit in your baskets, you must stop.

Given the integer array fruits, return the maximum number of fruits you can pick.

Input & Output

Example 1 — Mixed Fruits

$ Input: fruits = [1,2,1]

› Output: 3

💡 Note: We can collect all 3 fruits since there are only 2 distinct types (1 and 2)

Example 2 — Three Types

$ Input: fruits = [0,1,2,2]

› Output: 3

💡 Note: Starting from index 1, we can collect [1,2,2] which has 2 distinct types and length 3

Example 3 — Long Sequence

$ Input: fruits = [1,2,3,2,2]

› Output: 4

💡 Note: Starting from index 1, we can collect [2,3,2,2] which has 2 distinct types (2 and 3) and length 4

Constraints

1 ≤ fruits.length ≤ 10⁵
0 ≤ fruits[i] < fruits.length

Visualization

Tap to expand

Understanding the Visualization

Input Array

Array of fruit types [1,2,3,2,2]

Find Best Window

Find longest subarray with ≤ 2 distinct types

Output Count

Return length of best window: 4

Key Takeaway

🎯 Key Insight: This is a sliding window problem to find the longest subarray with at most 2 distinct elements

Asked in

A Amazon 45 G Google 32 F Facebook 28 M Microsoft 25

The key insight is that this is a longest subarray problem with at most 2 distinct elements. The optimal approach uses sliding window technique to maintain a window containing at most 2 fruit types. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force	O(n²)	O(1)	Try every possible starting position and count fruits until we need a third basket
Sliding Window	O(n)	O(1)	Use a sliding window to maintain at most 2 distinct fruit types efficiently

Brute Force — Algorithm Steps

For each starting position i
Count fruits from position i until we need a third basket
Update maximum count

Visualization

Tap to expand

Step-by-Step Walkthrough

Try Position 0

Start from index 0, count until third fruit type

Try Position 1

Start from index 1, count until third fruit type

Maximum

Return the maximum count found

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int* fruits, int fruitsSize) {
    int maxFruits = 0;
    
    for (int i = 0; i < fruitsSize; i++) {
        int basket1 = -1;
        int basket2 = -1;
        int count = 0;
        
        for (int j = i; j < fruitsSize; j++) {
            if (basket1 == -1) {
                basket1 = fruits[j];
                count++;
            } else if (fruits[j] == basket1) {
                count++;
            } else if (basket2 == -1) {
                basket2 = fruits[j];
                count++;
            } else if (fruits[j] == basket2) {
                count++;
            } else {
                break;
            }
        }
        
        if (count > maxFruits) {
            maxFruits = count;
        }
    }
    
    return maxFruits;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int fruits[10000];
    int size = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        fruits[size++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    printf("%d\n", solution(fruits, size));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

Nested loops - outer loop for starting positions, inner loop to count fruits

⚠ Quadratic Growth

Space Complexity

O(1)

Only using a few variables to track fruit types and counts

✓ Linear Space

78.0K Views

High Frequency

~25 min Avg. Time

1.9K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler