# Move Along

## Dynamic-Size Sliding Window Pattern/Technique

The dynamic-size sliding window pattern optimizes algorithms that involve searching an array or string for a consecutive subsection that satisfies a given condition. Unlike the fixed-size sliding window, this window’s size **changes** as it moves along the data structure.

To solve problems like these, we could apply a brute force solution with a nested loop, but it would produce O(n²) time complexity at best. Applying the dynamic-size sliding window pattern can reduce the time complexity to O(n) and space complexity to O(1).

## Moving on

In this pattern, two pointers create a window that represents the current subsection of the data structure. One pointer is the **leading edge** and the other pointer is the **trailing edge**. This window, or chunk, is evaluated to see if it satisfies the given criteria (e.g. the sum of its values is equal to *k*).

Even if the window satisfies the given criteria, the window’s size is changed to see if it can do better (e.g. create a longer/shorter subsection with the sum of its values equal to *k*).

The window grows (by incrementing the **leading edge**) or shrinks (by incrementing the **trailing edge**), moving it along the data structure.

The window keeps inching along until it reaches the stopping condition, usually the end of the data structure.

The criteria will vary from problem to problem. Based on the problem’s criteria, the solution will usually need two variables, in addition to the pointers, to help track the result. Sometimes, an auxiliary data structure (e.g. hash table) is needed instead of a primitive data type to track a result.

## We are moving in the right direction when the problem:

- involves a data structure that is iterable (
*arrays*,*strings*,*etc.*) - asks to find a subsection (
*substring/subarray*) that meets a*desired condition/target value (*e.g.*max/min/common/longest/shortest/contains)* - does NOT have a size constraint

## Example — JavaScript

Write a function called minSubArrayLen which accepts two parameters — anarrayof positive integers and a positive integer. The function should return theminimal lengthof a contiguoussubarrayof which thesum is greater than or equal to the intger passed in. If there isn’t one, return 0.Examples:

minSubArrayLen([2,3,1,2,4,3], 7) // 2

minSubArrayLen([2,1,6,5,4], 9) // 2

minSubArrayLen([3,1,7,11,2,9,8,21,62,33,19], 52) // 1

minSubArrayLen([1,4,16,22,5,7,8,9,10], 39) // 3

minSubArrayLen([1,4,16,22,5,7,8,9,10], 55) // 5

minSubArrayLen([4,3,3,8,1,2,3], 11) // 2

minSubArrayLen([1,4,16,22,5,7,8,9,10], 95) // 0

## Sample Problems

- Max Consecutive Ones III
- Longest Substring Without Repeating Characters
- Longest Substring with At Least K Repeating Characters
- Minimum Window Substring
- Longest Repeating Character Replacement

📚 Resources 👀

Sliding Window Technique — Algorithmic Mental Models

Udemy: JavaScript Algorithms and Data Structures Masterclass