### 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]
// ...
``````

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++) {
}

// 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