Sliding Window Problems

Fri, Jul 28, 2023 4-minute read

Understanding Sliding Window Problems

Introduction

Sliding window problems are a common type of algorithmic challenge that involve iterating over a data structure, typically an array or a list, using a “window” of fixed size. As the name implies, this window “slides” over the data structure, helping to solve problems more efficiently.

The concept is surprisingly simple, yet mastering it can dramatically increase your problem-solving speed and efficiency, especially in fields like competitive programming or technical interviews.

Basic Concept

Imagine you have a long row of houses, and you’re tasked with painting a series of adjacent houses. However, you can only see a certain number of houses at a time. To solve this, you start from one end of the row and move your gaze along, keeping track of the houses you’ve just seen. This method of viewing the houses is akin to the sliding window technique.

In terms of programming, imagine a list of numbers. A “sliding window” of size k would mean we consider k elements at a time. We start from the first k elements, perform some operations, and then move (or slide) our window one step to the right, now considering elements 2 to k+1.

int[] nums = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
int windowSize = 3;

// Initial window: [1, 2, 3]
// Next window: [2, 3, 4]
// Next window: [3, 4, 5]
// ...

Advantages

The sliding window technique can make an algorithm more efficient by avoiding redundant computations. Instead of recalculating information for each subset, the algorithm can reuse computations from the previous window, saving time and computational resources.

Simple Example: Maximum Sum Subarray of Size K

Let’s start with a classic example: Given an array of integers and a number k, find the maximum sum of any contiguous subarray of size k.

The naive approach would be to generate all subarrays of size k, compute their sums, and return the maximum sum, which would take O(n*k) time. However, with the sliding window technique, we can solve this problem in O(n) time.

Here’s a simple Java code to illustrate this:

public int maxSumSubarray(int[] nums, int k) {
    int windowSum = 0;
    int maxSum = 0;
    int windowStart = 0;

    // Create the initial window and calculate its sum
    for (int windowEnd = 0; windowEnd < k; windowEnd++) {
        windowSum += nums[windowEnd];
    }

    maxSum = windowSum;

    // Slide the window along the array
    for (int windowEnd = k; windowEnd < nums.length; windowEnd++) {
        // Slide the window
        windowSum += nums[windowEnd] - nums[windowStart];
        windowStart++;

        // Update the max sum if necessary
        maxSum = Math.max(maxSum, windowSum);
    }

    return maxSum;
}

More Advanced Example: Olympic Averages

Now let’s move to a more complex problem: Given a list of numbers, calculate a “rolling Olympic average” for each set of 5 consecutive numbers. An Olympic average of 5 numbers is the average of the middle 3 numbers when sorted (ignoring the highest and lowest).

public ArrayList<Double> rollingOlympicAverage(ArrayList<Integer> input) {
    ArrayList<Double> averages = new ArrayList<>();

    for (int i = 2; i < input.size() - 2; i++) {
        ArrayList<Integer> fiveNumbers = new ArrayList<>();

        // Add the five numbers to the list
        for (int j = i - 2; j <= i + 2; j++) {
            fiveNumbers.add(input.get(j));
        }

        // Sort the list
        Collections.sort(fiveNumbers);

        // Remove the smallest and largest numbers
        fiveNumbers.remove(0);
        fiveNumbers.remove(fiveNumbers.size() - 1);

        // Calculate the average of the remaining numbers
        double average = 0;
        for (int num : fiveNumbers) {
            average += num;
        }
        average /= 3;

        // Add the average to the result list
        averages.add(average);
    }

    return averages;
}

This example demonstrates how the sliding window technique can solve more complex problems. By manipulating the elements in the window, we can calculate complex statistics like Olympic averages.

Conclusion

Mastering the sliding window technique is a powerful tool in a programmer’s toolkit. From simple problems like finding maximum subarray sums to more complex ones like calculating rolling Olympic averages, this technique is an efficient way to solve a wide range of problems. The key is understanding how to set up the window, how to move it, and how to efficiently perform calculations based on the elements in the window.

Git Forked