Interview Problem Explained: Fruit Into Baskets (Two Pointer Technique)

Understanding the Problem: Fruits into Baskets

Imagine you’re tasked with collecting fruits from a row of fruit trees. Each tree produces a specific type of fruit, and you’re given two baskets with the following constraints:

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

2. Combined, the baskets can hold fruits from no more than two types.

3. Each basket can hold an unlimited quantity of fruits.

Fruit-Picking Rules:

• You may start picking fruits from any tree and must move only to the right, collecting one fruit per tree.

• If the current tree’s fruit type is already in your baskets, you can continue collecting.

• However, if you encounter a third fruit type that’s not already in your baskets, you must stop collecting at that point.

Your goal is to calculate the maximum number of fruits you can collect under these conditions.

Step 1. Naive Approach

Idea

Let’s begin with the most basic approach.

This method tries every possible case one by one, following these steps:

From every starting point, we move right and check whether the basket contains only two types of fruits.

In other words, for each starting index, we continue picking fruits as long as we’re within the two-type constraint.

Logic Breakdown

Here’s how we can break it down:

1. Try every possible starting index i.

2. From each i, move right:

   • If the current fruit is already in the basket or there’s still room for a new type, pick it.

   • If it’s a third fruit type and both baskets are already filled, stop.

3. Track how many fruits were collected from each starting index and return the maximum.

Time and Space Complexity

Let’s assume the number of fruit trees is N.

In this approach:

• We try all possible starting points → this takes N iterations.

• For each starting point, we move right until the condition breaks → this can take up to N iterations again.

So the total time complexity becomes O(N²).

When the number of trees is large (up to 10⁵), this results in time limit exceeded.

Since the constraint is N ≤ 10⁵, this approach leads to timeouts.

Code Implementation

def totalFruit(fruits):
    n = len(fruits)  # Number of fruit trees
    max_fruits = 0   # To track the maximum number of fruits collected

    # 1. Try every starting point i
    for i in range(n):
        basket = set()  # Store the types of fruits
        count = 0
        # 2. Move right from the current starting point
        for j in range(i, n):
            fruit = fruits[j]
            # 2-a. If the fruit is already in the basket or there’s still room
            if fruit in basket or len(basket) < 2:
                basket.add(fruit)
                count += 1
            else:
                # 2-b. A third type appears → stop collecting
                break
        # 3. Update the maximum if necessary
        max_fruits = max(max_fruits, count)

    return max_fruits

Step 2: Optimized Approach Using Two Pointer

Idea

In Step 1, we saw that although the approach was straightforward, it was highly inefficient.

To reduce the time complexity, we need to either:

1. Reduce the cost of considering every possible starting index i, or

2. Reduce the cost of finding the maximum rightward position we can move to from each i.

Generally, it’s easier to begin optimization by focusing on the smallest unit of inefficiency.

In this case, we focus on step 2: how far to the right we can move from each starting point.

Let’s examine an example input to better understand where the inefficiency lies:

Input example: fruits = [1, 1, 2, 2, 3, 3, 3, 1, 2, 1, 1, 2, 4]

If we mark the maximum valid range (from each starting index i to the farthest valid end index):

Do you notice a pattern?

Exactly—as the starting index increases, the end index never decreases.

And if you think about it for a moment, the reason becomes clear:

• Let’s say you start at i = 0 and move right to find the farthest point end such that you’re still within the two-type limit.

• Now move to i = 1. The fruits you saw from i = 0 to end are still valid. The sequence is still made up of at most two types.

• This means you don’t need to reset the end pointer each time you move the starting index forward.

In Step 1, however, we were rechecking everything from scratch for each new i.

This is the key inefficiency we’re going to fix.

Logic Breakdown

Let’s restructure the logic:

1. Define the variable end as the farthest valid right-end index of a range.

2. For every possible starting index i, do the following:

3. Reuse the result from the previous range and attempt to expand end further.

4. Count the number of fruits collected in that range and update the result if it’s greater than the current maximum.

This idea is known as the Two Pointer technique.

💡What is Two Pointer?

Two Pointer is an algorithmic technique where you use two indices to explore a range within an array. It’s widely used for sliding window problems, subarrays, or finding conditions over sequences.
The key advantage is that it avoids redundant calculations and often improves the time complexity from O(N²) to O(N).

Reference: Two Pointer - Concept & Example

Code Implementation

def totalFruit(fruits):
    n = len(fruits)  # Total number of trees
    max_fruits = 0   # To track the result
    basket = {}      # Dictionary to store fruit types and their counts
    end = -1         # End of the valid range, initialized to -1

    # 1. Consider every starting index i
    for i in range(n):
        # 2. Expand the end pointer as far as possible
        while end < n - 1:
            next_fruit = fruits[end + 1]
            # If basket is full and the next fruit is a new type, stop
            if len(basket) >= 2 and next_fruit not in basket:
                break
            # Otherwise, expand the window
            end += 1
            basket[next_fruit] = basket.get(next_fruit, 0) + 1

        # 3. Update the maximum fruits collected
        max_fruits = max(max_fruits, end - i + 1)

        # 4. Remove the i-th fruit as the window moves forward
        basket[fruits[i]] -= 1
        if basket[fruits[i]] == 0:
            del basket[fruits[i]]

    return max_fruits

Time and Space Complexity

1) Time Complexity

Even though we have a for loop with a while loop inside, the total time complexity is O(N), not O(N²).

• The for loop increments i from left to right.

• The while loop also moves the end pointer from left to right.

• Since both pointers only move forward and never backtrack, they cover each element at most once.

Thus, the total number of operations is linear in the size of the input array.

2) Space Complexity

The basket dictionary stores at most three fruit types (but the problem only allows two), so the space used is O(1).

By applying the Two Pointer technique, we’ve optimized the solution from O(N²) to O(N) while still solving the problem correctly.

Frequently Asked Questions

Q. What key algorithm concept can I learn from this problem?

This problem teaches you how to apply the Two Pointer technique.

It’s particularly useful in scenarios where you need to maintain certain constraints while iterating through a sequence, like keeping a subarray within two types of elements.

Q. I’m new to this type of problem. How should a beginner approach it? Any prerequisites?

Before worrying about time or space complexity, you should first be able to come up with and implement a basic (naive) approach.

If you’re unable to come up with that initial version or find yourself struggling to structure the idea, it may be a sign that you need more practice with brute-force or simulation-type problems.

Once you can do that, the next step is to ask:

• Can I calculate the time and space complexity on my own?

• Can I analyze and optimize the approach?

If you can answer those questions, then you’re at the right level to tackle this problem.

Q. What should I keep in mind when solving this in an interview setting?

Many candidates fail to break down their thinking process or explain how they arrived at a solution.

A common mistake is relying on memory or simply recognizing patterns without real understanding.

This is known as pattern recognition, and while it might get you past some practice problems, it’s not the right approach for interviews.

Instead, train yourself to:

• Start with the most basic idea (even if inefficient)

• Break it down into steps

• Then look for ways to optimize it from there

Interviewers care less about the final answer and more about how you structure your thinking and how clearly you explain your logic.

How to Prepare for Interviews with the "Fruit Into Baskets" Problem

The Fruit Into Baskets problem is one of the most frequently asked coding interview questions based on the Two Pointer technique.

It often appears in interviews for top tech companies like FAANG and fast-growing startups, especially in problems involving arrays or subarrays.

Similar Problems to Practice

• Longest Substring Without Repeating Characters (LeetCode #3)

• Minimum Size Subarray Sum (LeetCode #209)

• Sum of Consecutive Integers (Codetree)

These problems all involve variations of the Two Pointer technique and are great for training your ability to think through constraints and efficiently explore ranges in arrays.

How to Review After Solving

1. Summarize the type of problem → Write down that this is a “Two Pointer + condition maintenance” problem.

2. Describe the core logic in one sentence → For example: “Expand the window while maintaining two fruit types, shrink it when a third appears.”

3. Compare how similar ideas are used in different problems → How was the Two Pointer window expanded or contracted in each problem? What changed based on the constraints?

Why This Problem Matters

“Fruit Into Baskets” may look simple at first glance, but it’s a classic Two Pointer interview problem that tests your ability to structure, optimize, and communicate your solution clearly.

From identifying inefficiencies in naive logic

→ to implementing a window-based approach
→ to analyzing time and space complexity,

this problem walks you through the full lifecycle of algorithmic thinking.

If you're preparing for technical interviews—whether for your first job or a FAANG-level role—this kind of problem is a must-practice. But don’t stop at just solving it once.

Try to explain your thinking aloud, analyze edge cases, and practice follow-up questions. Codetree offers a guided path for mastering problems like this—starting from foundational concepts to real interview-level training with feedback.