Sliding Window

This technique refers to creating a window that "slides" through an input sequence (typically an array or string).

variable-length sliding window

Sliding windows can be either variable or fixed length. On this page, we'll cover variable-length sliding windows by looking at:

An example problem that illustrates the motivation for each type of sliding window, as well as how to implement it.
The types of problems for which each type of sliding window is useful, as well as templates you can use as a starting point.
A list of practice problems (with animated solutions and explanations!) for you to try to build upon the concepts covered here.

Problem: Fruit Into Baskets

DESCRIPTION (credit Leetcode.com)

Write a function to calculate the maximum number of fruits you can collect from an integer array fruits, where each element represents a type of fruit. You can start collecting fruits from any position in the array, but you must stop once you encounter a third distinct type of fruit. The goal is to find the longest subarray where at most two different types of fruits are collected.

Example: Input: fruits = [3, 3, 2, 1, 2, 1, 0] Output: 4 Explanation: We can pick up 4 fruit from the subarray [2, 1, 2, 1]

We'll walkthrough how to use the sliding window to solve this problem when fruits = [3, 3, 2, 1, 2, 1, 0].

The answer for the given input array is 4.

Naive Approach

To understand the motivation behind the sliding window pattern, let's start by looking at a naive approach to this problem, which considers every possible subarray in the input, and chooses the longest one with at most 2 distinct fruits.


def fruit_into_baskets(fruits):

    max_length = 0

    # i and j are the start and end indices of the subarray
    for i in range(len(fruits)):
        for j in range(i, len(fruits)):
            if len(set(fruits[i:j + 1])) <= 2:
                max_length = max(max_length, j - i + 1)
            else:
                # the subarray starting at i is invalid
                # so we break and move to the next one
                break
    
    return max_length

This approach considers O(n²) subarrays. For each subarray, it checks if it contains at most 2 distinct fruits by converting it to a set and checking its length, which takes O(n) time, for a total a time complexity of O(n³). We'll gradually improve this approach until we reach the sliding window pattern, which solves this problem in O(n) time.

Improvement 1: Build Incrementally

The first improvement is to use a variable to store the contents of the current subarray. We'll use a dictionary state that maps each fruit in the current subarray to the number of times it appears.

This choice of state is key as it allows us to:

Build the contents of the subarray incrementally. Each time we expand the subarray to include a new fruit, we'll increment the count of that fruit in state, which reuses work from the previous subarray.
Check if the subarray is valid by checking if state has 2 keys or less.

Since both of these operations take O(1) time, we can now check if a new subarray is valid in O(1) time. This brings the total time complexity of the solution down to O(n²).


def fruit_into_baskets(fruits):

    max_length = 0

    # i and j are the start and end indices of the subarray
    for i in range(len(fruits)):
        state = {}
        for j in range(i, len(fruits)):
            state[fruits[j]] = state.get(fruits[j], 0) + 1
            if len(state) <= 2:
                max_length = max(max_length, j - i + 1)
            else:
                # the subarray starting at i is invalid
                # so we break and move to the next one
                break
    
    return max_length

Improvement 2: Don't Blow It All Up!

In the above approach, we reset state each time we reach an invalid subarray and break from the inner loop. When the outer loop increments i, we end up rebuilding parts of the same subarray from the previous iteration, which we can see by visualizing the first few steps of the algorithm:

After incrementing i, we end up rebuilding the same subarrays ([1], [1, 2], [1, 2, 3]) from the previous iteration.

Rather than resetting the contents of state each time we reach an invalid subarray, we can instead think about removing fruits from the start of the subarray until it is valid again. This allows us to move onto the next valid subarray while also preserving work we've already done - which brings us to the sliding window pattern.

The Sliding Window

We now have enough context to understand the motivation behind the sliding window pattern. The "window" in the sliding window refers to a subarray we are considering to contain the maximum number of fruits we can collect.

Initialization

We use two pointers, start and end, to represent the start and end indices of the window. The window is initially empty, and so is the dictionary state that represents the contents of the window. We also initialize a variable max_fruit that represents the maximum amount of fruit we can collect.

start

fruit into baskets

0 / 1

Iteration

Next we repeatedly extend the current window incrementing end. Each time we do so, we add the fruit at end to state by incrementing its count in the dictionary, and then we compare the length of the window to the current value of max_fruit, and update it if its greater.

start: 0 | end: -

initialize variables

0 / 6

Contracting the Window

Eventually, we reach a window that is invalid because it contains 3 distinct fruits. Here, we contract the window by decrementing the count of the fruit at start in state, and then incrementing start to contract the window. We contract the window until it is valid again.

start: 0 | end: 2

update max_fruit

0 / 3

At this point, our window is ready to expand again, so we continue iterating until we reach the end of the array, at which point we return max_fruit.

start: 2 | end: 3

contract window

0 / 11

Solution

Here's what the final solution looks like:


def fruit_into_baskets(fruits):
  start = 0
  state = {}
  max_fruit = 0

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

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

    max_fruit = max(max_fruit, end - start + 1)

  return max_fruit

start

fruit into baskets

0 / 21

The length of the window at any time is end - start + 1.
When we decrement the count of a fruit in state as part of contracting the window, we need to delete the fruit from state if its count is 0. This is because we rely on the number of keys in state to check if the window is valid.

Complexity

The time complexity of this algorithm is O(n), where n is the length of the input array. end iterates through the array once, and start iterates through the array at most once. Each time either moves, we arrive at a new window, which requires O(1) time to check if its valid.
The space complexity of this algorithm is O(1), since state never contains more than 3 keys.

Template

Here's a template you can use as a starting point for solving problems with a variable-length sliding window.


def variable_length_sliding_window(nums):
  state = # choose appropriate data structure
  start = 0
  max_ = 0

  for end in range(len(nums)):
    # extend window
    # add nums[end] to state in O(1) in time

    while state is not valid:
      # repeatedly contract window until it is valid again
      # remove nums[start] from state in O(1) in time
      start += 1

    # INVARIANT: state of current window is valid here.
    max_ = max(max_, end - start + 1)

  return max_

When Do I Use This?

Consider using the sliding window pattern for questions that involve searching for a continuous subsequence in an array or string that satisfies a certain constraint.

If you know the length of the subsequence you are looking for, use a fixed-length sliding window. Otherwise, use a variable-length sliding window.

Examples:

Finding the largest substring without repeating characters in a given string (variable-length).
Finding the largest substring containing a single character that can be made by replacing at most k characters in a given string (variable-length).
Finding the largest sum of a subarray of size k without duplicate elements in a given array (fixed-length).

Practice Problems

When practicing these problems, it is important to think about the approrpriate data structure state to store the contents of the current window. Make sure it supports both:

Adding and removing elements from the window in O(1) time.
Checking if the window is valid in O(1) time.

Dictionaries and sets are often the best choices.

Question	Difficulty
Longest Substring Without Repeating Characters	Medium
Longest Repeating Character Replacement	Medium

Next: Longest Substring Without Repeating Characters

Your account is free and you can post anonymously if you choose.

Loading comments...

Back to Home

Eliminating Pairs

Overview

Container With Most Water

3-Sum

Triangle Numbers

Pointers as Regions

Move Zeroes

Sort Colors

Trapping Rain Water

Variable-Length

Overview

Longest Substring Without Repeating Characters

Longest Repeating Character Replacement

Fixed-Length

Overview

Maximum Sum of Subarrays of Size K

Max Points You Can Obtain From Cards

Max Sum of Distinct Subarrays Length k

Overview

Can Attend Meetings

Insert Interval

Non-Overlapping Intervals

Merge Intervals

Employee Free Time

Overview

Valid Parentheses

Decode String

Longest Valid Parentheses

Monotonic Stack

Overview

Daily Temperatures

Largest Rectangle in Histogram

Overview

Linked List Cycle

Palindrome Linked List

Remove Nth Node From End of List

Reorder List

Swap Nodes in Pairs

Overview

Apple Harvest (Koko Eating Bananas)

Search in Rotated Sorted Array

Overview

Kth Largest Element in an Array

K Closest Points to Origin

Find K Closest Elements

Merge K Sorted Lists

Introduction

Binary Trees

Overview

Level Order Sum

Rightmost Node

Zigzag Level Order

Maximum Width of Binary Tree

Graphs

Overview

Minimum Knight Moves

Rotting Oranges

01-Matrix

Bus Routes

Overview

Word Search

Solution Space Trees

Subsets

Generate Parentheses

Combination Sum

Topological Sort

Overview

Course Schedule

Course Schedule II

Fundamentals

Solving a Question with Dynamic Programming

Counting Bits

Decode Ways

Maximal Square

Unique Paths

Longest Increasing Subsequence

Word Break

Maximum Profit in Job Scheduling

Overview

Best Time to Buy and Sell Stock

Gas Station

Jump Game

Overview

Implement Trie Methods

Prefix Matching

Overview

Count Vowels in Substrings

Subarray Sum Equals K

Spiral Matrix

Rotate Image

Set Matrix Zeroes

Two Pointers: Trapping Rain Water

Longest Substring Without Repeating Characters

Sliding Window

This technique refers to creating a window that "slides" through an input sequence (typically an array or string).

variable-length sliding window

Sliding windows can be either variable or fixed length. On this page, we'll cover variable-length sliding windows by looking at:

An example problem that illustrates the motivation for each type of sliding window, as well as how to implement it.
The types of problems for which each type of sliding window is useful, as well as templates you can use as a starting point.
A list of practice problems (with animated solutions and explanations!) for you to try to build upon the concepts covered here.

Problem: Fruit Into Baskets

DESCRIPTION (credit Leetcode.com)

Example: Input: fruits = [3, 3, 2, 1, 2, 1, 0] Output: 4 Explanation: We can pick up 4 fruit from the subarray [2, 1, 2, 1]

We'll walkthrough how to use the sliding window to solve this problem when fruits = [3, 3, 2, 1, 2, 1, 0].

The answer for the given input array is 4.

Naive Approach


def fruit_into_baskets(fruits):

    max_length = 0

    # i and j are the start and end indices of the subarray
    for i in range(len(fruits)):
        for j in range(i, len(fruits)):
            if len(set(fruits[i:j + 1])) <= 2:
                max_length = max(max_length, j - i + 1)
            else:
                # the subarray starting at i is invalid
                # so we break and move to the next one
                break
    
    return max_length

Improvement 1: Build Incrementally

The first improvement is to use a variable to store the contents of the current subarray. We'll use a dictionary state that maps each fruit in the current subarray to the number of times it appears.

This choice of state is key as it allows us to:

Build the contents of the subarray incrementally. Each time we expand the subarray to include a new fruit, we'll increment the count of that fruit in state, which reuses work from the previous subarray.
Check if the subarray is valid by checking if state has 2 keys or less.

Since both of these operations take O(1) time, we can now check if a new subarray is valid in O(1) time. This brings the total time complexity of the solution down to O(n²).


def fruit_into_baskets(fruits):

    max_length = 0

    # i and j are the start and end indices of the subarray
    for i in range(len(fruits)):
        state = {}
        for j in range(i, len(fruits)):
            state[fruits[j]] = state.get(fruits[j], 0) + 1
            if len(state) <= 2:
                max_length = max(max_length, j - i + 1)
            else:
                # the subarray starting at i is invalid
                # so we break and move to the next one
                break
    
    return max_length

Improvement 2: Don't Blow It All Up!

After incrementing i, we end up rebuilding the same subarrays ([1], [1, 2], [1, 2, 3]) from the previous iteration.

The Sliding Window

Initialization

start

fruit into baskets

0 / 1

Iteration

start: 0 | end: -

initialize variables

0 / 6

Contracting the Window

start: 0 | end: 2

update max_fruit

0 / 3

At this point, our window is ready to expand again, so we continue iterating until we reach the end of the array, at which point we return max_fruit.

start: 2 | end: 3

contract window

0 / 11

Solution

Here's what the final solution looks like:


def fruit_into_baskets(fruits):
  start = 0
  state = {}
  max_fruit = 0

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

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

    max_fruit = max(max_fruit, end - start + 1)

  return max_fruit

start

fruit into baskets

0 / 21

The length of the window at any time is end - start + 1.
When we decrement the count of a fruit in state as part of contracting the window, we need to delete the fruit from state if its count is 0. This is because we rely on the number of keys in state to check if the window is valid.

Complexity

The time complexity of this algorithm is O(n), where n is the length of the input array. end iterates through the array once, and start iterates through the array at most once. Each time either moves, we arrive at a new window, which requires O(1) time to check if its valid.
The space complexity of this algorithm is O(1), since state never contains more than 3 keys.

Template

Here's a template you can use as a starting point for solving problems with a variable-length sliding window.


def variable_length_sliding_window(nums):
  state = # choose appropriate data structure
  start = 0
  max_ = 0

  for end in range(len(nums)):
    # extend window
    # add nums[end] to state in O(1) in time

    while state is not valid:
      # repeatedly contract window until it is valid again
      # remove nums[start] from state in O(1) in time
      start += 1

    # INVARIANT: state of current window is valid here.
    max_ = max(max_, end - start + 1)

  return max_

When Do I Use This?

Consider using the sliding window pattern for questions that involve searching for a continuous subsequence in an array or string that satisfies a certain constraint.

If you know the length of the subsequence you are looking for, use a fixed-length sliding window. Otherwise, use a variable-length sliding window.

Examples:

Finding the largest substring without repeating characters in a given string (variable-length).
Finding the largest substring containing a single character that can be made by replacing at most k characters in a given string (variable-length).
Finding the largest sum of a subarray of size k without duplicate elements in a given array (fixed-length).

Practice Problems

When practicing these problems, it is important to think about the approrpriate data structure state to store the contents of the current window. Make sure it supports both:

Adding and removing elements from the window in O(1) time.
Checking if the window is valid in O(1) time.

Dictionaries and sets are often the best choices.

Question	Difficulty
Longest Substring Without Repeating Characters	Medium
Longest Repeating Character Replacement	Medium

Next: Longest Substring Without Repeating Characters

Your account is free and you can post anonymously if you choose.

Loading comments...

BlogBehavioral Interview Examples Interviewing for Experienced SWEs All Blog Posts

Compare UsCompare to Interviewing.io

LinksFAQ Schedule Mock Interviews Pricing Become a Coach Our Coaches Learn System Design Learn DSA

LegalTerms and Conditions Privacy Policy

Contactsupport@hellointerview.com7511 Greenwood Ave North
Unit #4238 Seattle, WA 98103