See all coding puzzles and patterns here.

---

Algorithm Description

The sliding window technique is a way to solve certain problems that require inspecting some iterable over a fixed or variable length.

An inspection window slides over the target iterable, adding and removing individual elements at each iteration.

Because the additions and removals are constant time instead of computing for the whole window each time, a factor $n$ in the runtime is converted a constant factor.

---

Performance Characteristics

Let $n =$ the number of elements in the iterable.

Then the base algorithm has a runtime complexity of $\Theta(n)$. Depending on how the elements in the window are processed, the nested runtime complexity can vary.

For example, if the exiting element is subtracted from a sum while the entering element is added to the sum, then the nested complexity is just $\Theta(1)$, resulting in an overall runtime complexity of $\Theta(n)$. However, if we are sorting the elements inside the window, then the nested complexity can be $\Theta(k)$ or $\Theta(k \cdot log(k))$, where $k = $ the size of the window, resulting in an overall runtime complexity of $\Theta(k \cdot n)$ or $\Theta(n \cdot k \cdot log(k))$.

For similar reasons, space complexity can range from $\Theta(1)$ upwards. For the examples in the previous paragraph, the space complexity might be $\Theta(k)$.

---

Puzzles

Puzzle	Difficulty	External Link
Find Anagrams in String	Medium
Largest K Elements	Medium