Identify
- input is a linear data structure such as a linked list, array, or string
- problem based on an array, list, or string type of data structure
- find a subrange in that array or string to give the longest, shortest, or target values
- concepts like the longest/shortest substring, subarray, or a desired value of something that satisfies a given condition perfectly
Motive
- transform two nested loops into a single loop
- problems are painless to solve using a brute force approach in O(n²), O(n³), or O(n*k)
- reducing time complexity with the sliding window to O(n)
Steps
- hash table or set
- to count specific array input
- to uphold on increasing the window towards the right using an outer loop
- decrease by one inside a loop to reduce the window side by sliding towards the right
- store the current maximum/minimum window size or count
Complexity
Time O(n)
Space O(1)
Common Problems