Sliding Window Pattern 2

Mastering the Sliding Window Pattern: Solving the Fruit Into Baskets Problem

Introduction

The sliding window technique is a powerful strategy for solving problems involving arrays or strings, especially when looking for contiguous subarrays that satisfy specific conditions. In this article, we’ll explore this pattern by solving the Fruit Into Baskets problem from LeetCode, which challenges us to find the longest contiguous subarray containing at most two distinct elements.

Problem Overview

In the Fruit Into Baskets problem:

• You’re given an array where each element represents a type of fruit
• You have two baskets, each can hold only one type of fruit
• You want to pick fruits such that you collect the maximum number of fruits while maintaining at most two types of fruits in your baskets

This translates to finding the longest contiguous subarray with at most two distinct values.

Solution Code

from typing import List
 
class Solution:
    def totalFruit(self, fruits: List[int]) -> int:
        basket = {}  # Dictionary to store fruit counts
        left = 0     # Left pointer of our window
        max_fruits = 0  # Track maximum fruits collected
        
        for right, fruit in enumerate(fruits):
            # Add current fruit to basket
            basket[fruit] = basket.get(fruit, 0) + 1
            
            # If we have more than 2 types, shrink window from left
            while len(basket) > 2:
                basket[fruits[left]] -= 1
                if basket[fruits[left]] == 0:
                    del basket[fruits[left]]
                left += 1
            
            # Update maximum window size
            max_fruits = max(max_fruits, right - left + 1)
        
        return max_fruits

Understanding the Sliding Window Pattern

The sliding window pattern maintains a subarray (window) defined by two pointers that move through the array. The key aspects are:

1. Window Expansion: The right pointer moves forward to include new elements
2. Window Contraction: The left pointer moves forward when the window violates constraints
3. Tracking State: Maintaining information about the current window’s contents

Step-by-Step Explanation

1. Initialization

We initialize:

• A dictionary basket to track fruit counts in the current window
• A left pointer at position 0
• max_fruits to store our result

2. Window Expansion

We iterate through the array using the right pointer:

for right, fruit in enumerate(fruits):
    basket[fruit] = basket.get(fruit, 0) + 1

For each fruit, we add it to our basket, incrementing its count.

3. Window Contraction

When our basket contains more than two fruit types:

while len(basket) > 2:
    basket[fruits[left]] -= 1
    if basket[fruits[left]] == 0:
        del basket[fruits[left]]
    left += 1

We remove fruits from the left until we’re back to two types, updating counts and removing entries that reach zero.

4. Result Tracking

After ensuring the window is valid, we update our maximum:

max_fruits = max(max_fruits, right - left + 1)

Why This Works

The algorithm efficiently explores all possible valid subarrays by:

1. Expanding to include new elements
2. Contracting when constraints are violated
3. Tracking the best solution encountered

The time complexity is O(n) as each element is processed at most twice (once by each pointer). Space complexity is O(1) as the dictionary holds at most three entries.

Example Walkthrough

Let’s trace through an example with fruits = [1, 2, 1, 2, 3]:

1. Window: [1] → Types: {1:1} → Max: 1
2. Window: [1,2] → Types: {1:1, 2:1} → Max: 2
3. Window: [1,2,1] → Types: {1:2, 2:1} → Max: 3
4. Window: [1,2,1,2] → Types: {1:2, 2:2} → Max: 4
5. Window becomes invalid with type 3 added:
   • Remove fruit at left (type 1) → Types: {1:1, 2:2, 3:1}
   • Continue removing until valid: Remove type 1 → Types: {2:2, 3:1}
   • Window: [2,1,2,3] becomes [2,3]
   • Max remains 4

Final result: 4

Key Insights

1. The sliding window technique is optimal for contiguous subarray problems
2. We use a dictionary to efficiently track element frequencies
3. The while loop ensures we always maintain a valid window
4. We update our result at each step after ensuring window validity

Variations and Applications

The sliding window pattern can be adapted for various problems:

• Longest substring with at most K distinct characters
• Minimum size subarray sum
• Find all anagrams in a string
• Maximum consecutive ones

Conclusion

The sliding window pattern is a fundamental technique for solving array and string problems efficiently. By maintaining a dynamic window that expands and contracts based on constraints, we can solve many problems in linear time while keeping space complexity minimal.

Understanding this pattern will help you tackle a wide range of coding challenges and technical interviews more effectively. Remember the key components: two pointers, a way to track window state, and logic to expand/contract the window based on constraints.