Sliding Window Pattern - Part 2

July 21, 2021 - coding interview sliding window pattern arrays fruit into baskets

In the first part covering the sliding window pattern, we saw how it can be applied to solve the maximum subarray sum problem. In this second part of the series, we'll demonstrate how we can use a sliding window of dynamic size, to solve more interesting problems, such as the fruit into baskets problem.

Problem Statement

We are given an array of integers, each of which represents a tree. We are also given two baskets of unlimited capacity, but each basket can only hold fruit of a single type. We can start from any tree and we can only pick one fruit per tree while moving to the right. We cannot skip a tree and once we reach a tree with a fruit that cannot go in any of our baskets, we must stop.

The problem requires us to write an algorithm that returns the maximum number of fruits we can pick.

If you find the problem statement poorly worded, you are not alone. It might help to abstract the problem and reframe it in more concrete terms.

If we look closely at its core, the problem is asking what is the length of the longest contiguous subarray containing only two distinct elements?

Example

Given the following array of integers, where each integer represents a tree:

trees = [1,2,3,3,2,4]
answer = 4

We expect the answer to be 4, which is the number of fruit we can fit in our two baskets from picking the fruit off the trees in [2,3,3,2].

Brute Force Approach

The most straight forward approach to solve this problem would be to generate all the possible contiguous subarrays, choose the ones containing only two distinct elements, and keep track of the length of the longest one of them.

Just from the fact that we have to inspect all the possible subarrays, makes our time complexity O(N²).

Needless to say, this is prohibitive for this problem, and we can do much better.

Sliding Window Approach

While moving from left to right, picking a fruit from each tree, we will expand our window on the right side (end of the window) and determine whether our baskets can hold the fruit corresponding to the window. If they do, we will keep expanding our window. If not, we will have to shrink our window from the left side (start of the window) until our baskets can once again fit the fruit.

Let's rephrase this and abstract away from the fruit talk. We will visit each element in the array, expanding the sliding window and see whether the subarray contains two distinct elements, or less. If it does, great, we can keep expanding our window. If not, we will have to shrink our window until the subarray contains two or less distinct elements once again.

A key part of this approach will be the use of a Hash Map or dictionary. This will be used to quickly check how many distinct elements are in the subarray we are currently inspecting, and it will also hold the total count for each distinct element. Getting the number of entries (keys) in these data structures and getting their corresponding count (value), are both a constant O(1) operation.

Code

The following will resembles a solution that uses the pattern described above:

def totalFruit(fruits):
    # keeps track of the start of the window.
    window_start = 0
    # keeps track of the length of the longest subarray satisfying our conditions.
    max_len = 0
    # dictionary that keeps track of the distinct elements in our subarray, as well as their counts.
    fruit_count = {}
        
    for window_end in range(len(fruits)):
        fruit = fruits[window_end]
        # add the fruit to our dictionary.
        if fruit not in fruit_count:
            fruit_count[fruit] = 0
        fruit_count[fruit] += 1
            
        # this condition is met when our dictionary contains more than 2 distinct elements.
        # at this point we must shrink our window, until the subarray satisfies the constraints of the problem.
        while len(fruit_count) > 2:
            # get the element that will go out the sliding window.
            left_fruit = fruits[window_start]
            # reduce its count in the dictionary.
            fruit_count[left_fruit] -= 1
            # remove its corresponding key from the dictionary.
            if fruit_count[left_fruit] == 0:
                del fruit_count[left_fruit]
            # slide the window.
            window_start += 1
        # choose the longest out of the longest subarray encountered so far, and the current subarray in the sliding window.
        max_len = max(max_len, window_end - window_start + 1) 
    return max_len

Complexity

The time complexity of this algorithm is O(N), where N is the number of elements in our input array. We can arrive to this conclusion by considering the fact that we make N additions to our sliding window, and at most N-2 removals. Another way of looking at it is observing that the outer for loop iterates the input array just once, and the while loop, also processes each element just once.

The space complexity of this algorithm will be O(1) since at any point, there will be at most 3 entries in our dictionary. The additional space used by this data structure does not depend on the size of the input array.