Open-Source Internship opportunity by OpenGenus for programmers. Apply now.

In this article, we have explained how to solve Fruit into Baskets problem efficiently using the idea of Sliding Window.

Table of contents:

Problem statement: Fruit into Baskets
Solution Approach
2.1. Naive Approach (Brute Force)
2.2. Optimized Solution (Sliding Window)
2.3. Pseudocode
2.4. Time and Space Complexity
Similar Problems

Prerequisite: Sliding Window

This problem is similar to Leetcode problem 904. Fruit Into Baskets.

Problem statement: Fruit into Baskets

The fruit into baskets problem is based on the idea of a farm which has a row of trees of various fruit. This row of trees is represented as a list, trees, where trees[i] refers to the type of fruit the i-th tree in the row produces.

The problem here is that you want to pick as many fruit from these trees as possible but the rules of the farm state that you cannot pick more than two total types of fruit. It is also stated that you can only pick one fruit from each tree.

Furthermore, you have to pick a starting tree and move one tree to the right every time, picking one fruit from every new tree tree. Our ultimate goal is to find the ideal starting spot so we can pick the maximum number of fruit possible.

If, for example, we had a tree row designated by the list [0,2,2,3,2], where 0, 2, and 3 where types of fruit, we could pick a total of 4 fruits because we can start at index 1 and pick from [2,2,3,2] which is a total four fruits.

In another example, if we had the list [3,4,2,2,3,2,3,2,3,4,5,6,7] we could pick a total of 7 fruits because we start at index 2 and pick [2,2,3,2,3,2,3] which is a total of seven fruit.

In simpler terms, this long-winded question is essentially asking to find the longest contigous subarray with at most 2 integers.

Solution Approach

Naive Approach (Brute Force)

The naive, brute force solution here would essentially be checking every contingous subarray of the input array and filtering for ones that have at most two elements and finding the largest such array. This approach is very ineffecient as you would be making many redundant checks. The runtime would be in the order of (n^3) as you'd need a nested for loop to collect all the subarrays then scan them for ones with only two unique numbers than ultimately find the max.

As you can probably imagine we can find a much more efficient solution.

Optimized Solution (Sliding Window)

This problem lends itself to a sliding window type solution. We essentially need to find the largest contigous subarray with at most 2 types of fruit. To implement this approach, we will create a sliding window that will start at index 0 and grow to the right at every iteration. Each time we add a new element to the sliding window we will count its occurences in an auxillary data structure like a hash map.

If the length of this hash map becomes larger than 2 then we will shrink the window and remove an occurence of the character which was removed from the window. If a character in the hash map has an occurunce count of zero, we delete it. We do this until the length of the hash map is back to two.

At the end of each iteration, we keep track of a running max which we will return in the end.

Visualization of Sliding window approach! Sliding-Window-Demo

We can see how the window dynamically changes based on the contents of the auxillary data structure. Also, note that the running maximum is only calculated after any possible shrinking is done as it is possible that the window initially covers an invalid subarray but it will fix itself immediately after.

Also, if the question changed where the number of fruit types allowed was some variable K, we can easily change our code to account for that by replacing the check of len(basket)>2 with len(basket)>k.

Pseudocode

Initialize a window by using left and right indexes to denote the start and end of the window. Both will be initialized to zero.
Initialize a hash map which will be used to keep track of the fruits in the current window .
Increment the length of the window by one. And add an occurence of the new character added to the windo w to the aforementioned hash map.
Now, we will check if the length of the hash map is greater than two(not possible in the first few iterations) since we updated the hash_map in the previous step.
If the hash map is larger than length 2 then we shrink the window by one and accordingly remove an occurence of the removed character(the one cut off after shrinking the window) from the hash map. We do this until the hash map is of desired length 2.
We update the rolling max to be the max of the rolling max and the length of the current window.
This happens until the end of the window hits the end of the list. And we can return the output which should have the correct length of the largest contingous subarray of only two elements from the initial list.

Time and Space Complexity

The time complexity of this algorithm is O(n) were n is the length of the input list. This is the case as it only passes through the list once. And we don't have to iterate through the hash map to access its elements as it has constant time look up.

The space complexity of this algorithm is constant or O(1) as the hash map will only ever be length three at most and will not scale with the length of the input list.

Python Implementation

def totalFruit(self, fruits):
    window_start = 0
    max_so_far = 0
    fruit_basket = {}
    for window_end in range(len(fruits)):
        right_fruit = fruits[window_end]
        if right_fruit not in fruit_basket:
            fruit_basket[right_fruit] = 1
        else:
            fruit_basket[right_fruit] += 1

        while len(fruit_basket) > 2:
            left_fruit = fruits[window_start]
            fruit_basket[left_fruit] -= 1
            if fruit_basket[left_fruit] == 0:
                del fruit_basket[left_fruit]
            window_start += 1
        max_so_far = max(max_so_far, window_end - window_start+1)
    return max_so_far

Fruit into Baskets

Algorithms Sliding Window technique