DEV Community

Tammy Vo
Tammy Vo

Posted on

Sliding Window Technique

When to use: Aims to reduce the use of nested loop and replace it with a single loop. Reduces the time complexity from O(n^2) to O(n).

Two types of sliding window:

Fixed window length k: the length of the window is fixed and you will be asked to find something in the window. For example, the maximum sum or maximum average of each window.
First we start by getting the sum of the k sized window and keep track of the max value then sliding it by removing from the left and adding to the right.

class Solution {
    public double findMaxAverage(int[] nums, int k) {

        double maxAverage = 0;
        int sum = 0;

        for(int i = 0; i < k; i++){
            sum += nums[i];

        maxAverage = sum;

        for(int i = k; i < nums.length; i++){
            sum += nums[i] - nums[i - k];
            maxAverage = Math.max(maxAverage, sum);

        return maxAverage/k;
Enter fullscreen mode Exit fullscreen mode

Dynamic-size sliding window: The window size is not fixed and is also known as the two-pointers technique.
However, in a dynamic sliding window problem, the right pointer will be continuously changing unlike a traditional two pointer problem where the right pointer is initialized as the end of the list/array. Usually you will be asked to find the subarray that meets the criteria.

Latest comments (0)