Sliding Window

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

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

Fixed-Length Sliding Window

When you know the length of the subsequence you are looking for, you can use a fixed-length sliding window. The concept is similar to the variable-length sliding window, but the implementation is a bit simpler, as during each iteration, you both add and remove an element from the window to maintain its fixed size.

fixed-length sliding window of size 3

Problem: Maximum Sum of Subarray with Size K

DESCRIPTION

Given an array of integers nums and an integer k, find the maximum sum of any contiguous subarray of size k.

Example: Input: nums = [2, 1, 5, 1, 3, 2], k = 3 Output: 9 Explanation: The subarray with the maximum sum is [5, 1, 3] with a sum of 9.

We start by extending the window to size k. Whenever our window is of size k, we first compute the sum of the window and update max_sum if it is larger than max_sum. Then, we contract the window by removing the leftmost element to prepare for the next iteration. Note how we calculate the sum of the window incrementally by adding the new element and removing from the previous sum.

Solution


def max_subarray_sum(nums, k):
  max_sum = 0
  state = 0
  start = 0

  for end in range(len(nums)):
    state += nums[end]

    if end - start + 1 == k:
      max_sum = max(max_sum, state)
      state -= nums[start]
      start += 1

  return max_sum

start

max subarray sum of size k

0 / 16

Template

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


def fixed_length_sliding_window(nums, k):
  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

    if end - start + 1 == k:
      # INVARIANT: size of the window is k here.
      max_ = max(max_, contents of state)

      # contract window
      # remove nums[start] from state in O(1) in time
      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.

Fixed-Length

Question	Difficulty
Maximum Sum of Subarrays of Size K	Easy
Max Points You Can Obtain From Cards	Medium
Max Sum of Distinct Subarrays Length k	Medium

Next: Maximum Sum of Subarrays of Size K

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

Longest Repeating Character Replacement

Maximum Sum of Subarrays of Size K

Sliding Window

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

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

Fixed-Length Sliding Window

fixed-length sliding window of size 3

Problem: Maximum Sum of Subarray with Size K

DESCRIPTION

Given an array of integers nums and an integer k, find the maximum sum of any contiguous subarray of size k.

Example: Input: nums = [2, 1, 5, 1, 3, 2], k = 3 Output: 9 Explanation: The subarray with the maximum sum is [5, 1, 3] with a sum of 9.

Solution


def max_subarray_sum(nums, k):
  max_sum = 0
  state = 0
  start = 0

  for end in range(len(nums)):
    state += nums[end]

    if end - start + 1 == k:
      max_sum = max(max_sum, state)
      state -= nums[start]
      start += 1

  return max_sum

start

max subarray sum of size k

0 / 16

Template

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


def fixed_length_sliding_window(nums, k):
  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

    if end - start + 1 == k:
      # INVARIANT: size of the window is k here.
      max_ = max(max_, contents of state)

      # contract window
      # remove nums[start] from state in O(1) in time
      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.

Fixed-Length

Question	Difficulty
Maximum Sum of Subarrays of Size K	Easy
Max Points You Can Obtain From Cards	Medium
Max Sum of Distinct Subarrays Length k	Medium

Next: Maximum Sum of Subarrays of Size K

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