Advanced

Combined & Hybrid Patterns

The hardest problems blend sliding window with two-pointer logic or require creative adaptations of both patterns. Mastering these hybrids separates strong candidates from the rest.

Problem 1: Fruit Into Baskets (LeetCode 904)

Problem: You have a row of trees, each with a fruit type. You have two baskets, each holding one type. Starting from any tree, pick fruit from consecutive trees. What is the maximum number of fruits you can collect?

Translation: Find the longest subarray with at most 2 distinct values.

Example: fruits = [1,2,1,2,3] → 4 (subarray [1,2,1,2])

def total_fruit(fruits: list[int]) -> int:
    """Find longest subarray with at most 2 distinct elements.

    Variable sliding window with a frequency map.
    Time: O(n), Space: O(1) - map has at most 3 entries
    """
    basket = {}
    left = 0
    max_fruits = 0

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

        # Shrink window until we have at most 2 types
        while len(basket) > 2:
            basket[fruits[left]] -= 1
            if basket[fruits[left]] == 0:
                del basket[fruits[left]]
            left += 1

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

    return max_fruits


# Test
assert total_fruit([1, 2, 1]) == 3
assert total_fruit([0, 1, 2, 2]) == 3
assert total_fruit([1, 2, 3, 2, 2]) == 4
assert total_fruit([3, 3, 3, 1, 2, 1, 1, 2, 3, 3, 4]) == 5
print("All tests passed!")

Problem 2: Longest Turbulent Subarray (LeetCode 978)

Problem: A subarray is turbulent if the comparison sign alternates between consecutive elements. Find the length of the longest turbulent subarray.

Example: arr = [9,4,2,10,7,8,8,1,9] → 5 (subarray [4,2,10,7,8])

def max_turbulence_size(arr: list[int]) -> int:
    """Find length of longest turbulent (alternating) subarray.

    Two-pointer window: extend right while signs alternate, reset on violation.
    Time: O(n), Space: O(1)
    """
    n = len(arr)
    if n < 2:
        return n

    left = 0
    max_len = 1

    for right in range(1, n):
        # Compare current pair
        cmp = (arr[right] > arr[right - 1]) - (arr[right] < arr[right - 1])

        if cmp == 0:
            # Equal elements break turbulence
            left = right
        elif right == left + 1:
            # Starting a new potential turbulent subarray
            pass
        else:
            # Check if sign alternates from previous pair
            prev_cmp = (arr[right - 1] > arr[right - 2]) - (arr[right - 1] < arr[right - 2])
            if cmp == prev_cmp:
                # Same direction - reset window
                left = right - 1

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

    return max_len


# Test
assert max_turbulence_size([9, 4, 2, 10, 7, 8, 8, 1, 9]) == 5
assert max_turbulence_size([4, 8, 12, 16]) == 2
assert max_turbulence_size([100]) == 1
assert max_turbulence_size([9, 9]) == 1
print("All tests passed!")

Problem 3: Minimum Window Subsequence (LeetCode 727)

Problem: Given strings s and t, find the minimum window in s that contains t as a subsequence (characters in order, not necessarily contiguous).

Example: s = "abcdebdde", t = "bde" → "bcde"

def min_window_subsequence(s: str, t: str) -> str:
    """Find minimum window in s containing t as a subsequence.

    Forward pass to find end, backward pass to find start, then minimize.
    Time: O(|s| * |t|), Space: O(1)
    """
    min_len = float('inf')
    min_start = 0
    i = 0  # pointer in s

    while i < len(s):
        # Forward pass: find a window ending position
        j = 0  # pointer in t
        start = i

        while i < len(s) and j < len(t):
            if s[i] == t[j]:
                j += 1
            i += 1

        if j < len(t):
            break  # t not fully matched

        # i is now one past the end of the match
        end = i - 1

        # Backward pass: minimize the window by finding latest start
        j = len(t) - 1
        while j >= 0:
            if s[end] == t[j]:
                j -= 1
            end -= 1

        end += 1  # actual start of minimum window

        window_len = i - end
        if window_len < min_len:
            min_len = window_len
            min_start = end

        # Continue searching from end + 1
        i = end + 1

    return "" if min_len == float('inf') else s[min_start:min_start + min_len]


# Test
assert min_window_subsequence("abcdebdde", "bde") == "bcde"
assert min_window_subsequence("jmeqksfrsdcmsiwvaovztaqenrya", "u") == ""
assert min_window_subsequence("abcde", "ace") == "abcde"
print("All tests passed!")

Problem 4: Maximum Points from Cards (LeetCode 1423)

Problem: Given an array of card points, you can take exactly k cards from either end. Find the maximum score.

Translation: Find the minimum sum subarray of size (n-k) using a fixed window, then subtract from total.

Example: cardPoints = [1,2,3,4,5,6,1], k = 3 → 12

def max_score(card_points: list[int], k: int) -> int:
    """Find max points taking k cards from either end.

    Reverse thinking: minimize the sum of the (n-k) cards NOT taken.
    Those untaken cards form a contiguous subarray in the middle.
    Time: O(n), Space: O(1)
    """
    n = len(card_points)
    window_size = n - k
    total = sum(card_points)

    if window_size == 0:
        return total

    # Find minimum sum window of size (n-k)
    window_sum = sum(card_points[:window_size])
    min_window = window_sum

    for right in range(window_size, n):
        window_sum += card_points[right] - card_points[right - window_size]
        min_window = min(min_window, window_sum)

    return total - min_window


# Test
assert max_score([1, 2, 3, 4, 5, 6, 1], 3) == 12
assert max_score([2, 2, 2], 2) == 4
assert max_score([9, 7, 7, 9, 7, 7, 9], 7) == 55
assert max_score([1, 79, 80, 1, 1, 1, 200, 1], 3) == 202
print("All tests passed!")

Problem 5: Count Number of Nice Subarrays (LeetCode 1248)

Problem: Given an array of integers and an integer k, return the number of contiguous subarrays with exactly k odd numbers.

Example: nums = [1,1,2,1,1], k = 3 → 2

def number_of_subarrays(nums: list[int], k: int) -> int:
    """Count subarrays with exactly k odd numbers.

    Transform: treat odd as 1, even as 0. Then use at_most(k) - at_most(k-1).
    Time: O(n), Space: O(1)
    """
    def at_most(nums, k):
        left = 0
        count = 0
        odds = 0

        for right in range(len(nums)):
            if nums[right] % 2 == 1:
                odds += 1

            while odds > k:
                if nums[left] % 2 == 1:
                    odds -= 1
                left += 1

            count += right - left + 1

        return count

    return at_most(nums, k) - at_most(nums, k - 1)


# Test
assert number_of_subarrays([1, 1, 2, 1, 1], 3) == 2
assert number_of_subarrays([2, 4, 6], 1) == 0
assert number_of_subarrays([2, 2, 2, 1, 2, 2, 1, 2, 2, 2], 2) == 16
print("All tests passed!")

Summary

Problem	Hybrid Technique	Time	Space
Fruit Into Baskets	Variable window + frequency map	O(n)	O(1)
Longest Turbulent	Window + alternation tracking	O(n)	O(1)
Min Window Subsequence	Forward-backward two pointers	O(s×t)	O(1)
Max Points from Cards	Fixed window (complementary)	O(n)	O(1)
Nice Subarrays	at_most(k) - at_most(k-1)	O(n)	O(1)