DEV Community

Tammy Vo
Tammy Vo

Posted on

1 1

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.

Image of Datadog

How to Diagram Your Cloud Architecture

Cloud architecture diagrams provide critical visibility into the resources in your environment and how they’re connected. In our latest eBook, AWS Solution Architects Jason Mimick and James Wenzel walk through best practices on how to build effective and professional diagrams.

Download the Free eBook

Top comments (0)

Sentry image

See why 4M developers consider Sentry, “not bad.”

Fixing code doesn’t have to be the worst part of your day. Learn how Sentry can help.

Learn more

👋 Kindness is contagious

Please leave a ❤️ or a friendly comment on this post if you found it helpful!

Okay