Array

Technically, an array can’t be resized. A dynamic array, or list, can be. In the context of algorithm problems, usually when people talk about arrays, they are referring to dynamic arrays.

Given an array, a subarray is a contiguous section of the array. All the elements must be adjacent to each other in the original array and in their original order.

A subarray or substring is a contiguous section of an array or string.
A subsequence is a set of elements of an array/string that keeps the same relative order but doesn’t need to be contiguous.
A subset is any set of elements from the original array or string. The order doesn’t matter and neither do the elements being beside each other. Subsets that contain the same elements are considered the same.

A subarray can be defined by two indices, the start and end. We can call the starting index the left bound and the ending index the right bound. Another name for subarray in this context is “window”.

There is a very common group of problems involving subarrays that can be solved efficiently with sliding window.

First, the problem will either explicitly or implicitly define criteria that make a subarray “valid”. There are 2 components regarding what makes a subarray valid:
1. A constraint metric. This is some attribute of a subarray. It could be the sum, the number of unique elements, the frequency of a specific element, or any other attribute.
2. A numeric restriction on the constraint metric. This is what the constraint metric should be for a subarray to be considered valid.
Second, the problem will ask you to find valid subarrays in some way.
1. The most common task you will see is finding the best valid subarray. The problem will define what makes a subarray better than another.
2. Another common task is finding the number of valid subarrays.

The idea of a sliding window is to add elements by sliding to the right until the window violates the constraint. Once it does, we shrink the window from the left until it no longer violates the constraint.

Common techniques: