Understanding the variable sized sliding window pattern

Some problems require us to remember the occurrences of data items in a sequence of data for all windows, not just fixed-size windows. These are generally medium or hard problems that can be solved using nested loops to get the required results from all windows. To solve them, we would need to run fixed-sized sliding windows of all sizes from 1 to N (the size of the sequence) through the sequence along with a hash map that maps all data items in the window to some value defined by the problem (for example, the frequency of each item).

However, for some problems, we may only need to find results for some subarrays and skip the remaining. These problems can be solved by the variable-sized sliding window technique, which contracts or expands the window in each iteration as it slides through the sequence. We also add and remove the contributions of data items moving in and out of the window to the hash map to ensure it always has mapped values for all items in the window. It is a powerful technique that can solve many problems in a single pass that would otherwise need nested loops to compute subarrays.

Variable sized sliding technique

The variable-sized sliding window technique uses two variables start and end to maintain a window in the sequence (the window is the range [start, end - 1], inclusive at both ends, and empty when start == end) and a hash map to map data items in the window to some value defined by the problem (for example, the frequency with which each item appears in the window).