Algorithm Patterns: Sliding Window

The sliding window pattern is a technique used to reduce the number of nested loops in an algorithm. It’s based on the two-pointers pattern in which the pointers are used to set window bounds.

Using the sliding window pattern, we can process data in segments rather than the entire list. For example, if we need to find three consecutive integers in an array with the largest sum, we can set the window size to 3. This will allow us to process three elements of data at once.

Example: Maximum in Sliding Window

You are given an array of integers nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position. Return the max sliding window.

Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
Output: [3,3,5,5,6,7]
Explanation: 
Window position                Max
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

As we said the main sliding window is a technique used to reduce the number of nested loops.

• Iterate through the List element by element
• Add the element into another list called currentWindow
• If the number of elements in the currentWindow bigger than or equal to the window size, Get the max value from these its and Remove the first element in the current window
• repeat these steps until you have list of result

Java Code

public List<Integer> maxSlidingWindow(List<Integer>nums, int k) {
        List result = new ArrayList<Integer>();
        List<Integer> currentWindow = new ArrayList<Integer>();
    
        for(int i=0; i< nums.size(); i++){
            currentWindow.add(nums.get(i));
            if(currentWindow.size() >= k){
                Integer max = Collections.max(currentWindow);
                currentWindow.remove(0);
                result.add(max);
            }
        }
        return result;
    };

Time Complexity

The time complexity of the above algorithm is O(N), where ’N’ is the total number of elements in the given List.

Space Complexity

The space complexity of this solution is O(k), where k is the window size.

Leet Code Problems

• Best Time to Buy and Sell Stock (easy)
• Longest Substring Without Repeating Characters (medium)
• Minimum Size Subarray Sum (medium)
• Sliding window maximum (hard)
• Repeated DNA Sequences (hard)
• Minimum Window Substring (hard)