# Sliding Window

## Overview

The sliding window is more of a technique than algorithm. It is a form of dynamic programming since it makes use of the problems overlapping subproblems.

Two pointers are used to create a "window" over some data in the array or string. The window contains the data you are currently looking at. This data is usually compared against some previously calculated "best" data (like min, max, longest, shortest etc).

## Usage

Used to find subarrays within an array that satisfies certain conditions.

An example:

given an array find the pair of contiguous numbers that have the greatest sum of all pairs

Used when wanting to find some max, min, longest, shortest etc value from contiguous elements in an array or string

When the brute force solution is nested arrays, see if a O(n) solution can be obtained using a sliding window

## Types

### Fast/Slow

Have a fast pointer that grows the window and a slow pointer that shrinks the window. The fast pointer advances until the window contains the data you are looking for. Then the slow pointer increments, shrinking the window. The slow pointer keeps incrementing until the window no longer contains valid data.

Example:

Minimum Window Substring question.

### Fast/Catch-up

Similar to Fast/Slow but the slow pointer jumps to the fast pointer position rather than slowly incrementing to it.

Example:

### Fast/Trailing

The slow pointer is a few indices behind the fast pointer. It is keeping track of some choice you have made.

Example:

### Front/Back

One pointer travels from the end of the array and one from the start of the array. One side is moved based on some condition.

Example:

### Expand around the center

This technique is used for finding palindromes. A way to visualize a palindrome is as a mirror image of itself based on a center point. For example: the string `aba`

has a center point `b`

and the letters are mirrored around that center point. So, we could set a left and right pointer to the letter `b`

. Then we would increment the right pointer, decrement the left pointer and compare the letters. We keep doing this process until a mismatch is found or all letters are read.

If there are an even number of letters in the palindrome, then the center point is the two center letters. Example: `abba`

the center would be `bb`

.

#### Code to check if a string is a palindrome

To find a palindrome/palindromes within a string, we need to loop over the string and provide the index for the left and right pointers. We need to perform the expand twice, once for the odd size case and once for the even sized case. In this case the left and right pointer assignment is different as the mid point is the current index and not calculated. Here, for even length substrings, the left pointer is the index and the right pointer is index + 1.

#### Code template for substring expand around the center problems :

This code is O(n^2) as we have the for loop and then the while loop. This is compared to the brute force solution of O(n^3) which requires two loops to form all possible substrings plus the while loop to check if the substring is a palindrome.

#### Examples

## Reference:

Last updated