Sliding window algorithm in Rest API

Introduction

The sliding window algorithm helps you efficiently process parts of data step-by-step without repeating work. It saves time by moving a 'window' over data instead of starting fresh each time.

When you want to find the maximum or minimum value in every part of a list or stream.

When you need to calculate sums or averages of continuous chunks of data.

When you want to detect patterns or anomalies in a sequence of data points.

When you process data streams in real-time and want to keep track of recent information.

When you want to optimize performance by avoiding repeated calculations over overlapping data.

Syntax

Rest API

class SlidingWindow:
    def __init__(self, size):
        self.size = size
        self.window = []

    def add(self, value):
        if len(self.window) == self.size:
            self.window.pop(0)  # Remove oldest value
        self.window.append(value)

    def get_window(self):
        return self.window

This class keeps a fixed-size window of the most recent values.

When adding a new value, it removes the oldest if the window is full.

Examples

Window fills up to size 3 with values 1, 2, 3.

Rest API

sw = SlidingWindow(3)
sw.add(1)
sw.add(2)
sw.add(3)
print(sw.get_window())  # Output: [1, 2, 3]

Adding 4 removes oldest value 1, window slides forward.

Rest API

sw.add(4)
print(sw.get_window())  # Output: [2, 3, 4]

Empty window initially returns an empty list.

Rest API

empty_sw = SlidingWindow(2)
print(empty_sw.get_window())  # Output: []

Window size 1 always keeps only the latest value.

Rest API

single_sw = SlidingWindow(1)
single_sw.add(10)
print(single_sw.get_window())  # Output: [10]
single_sw.add(20)
print(single_sw.get_window())  # Output: [20]

Sample Program

This program shows how the sliding window moves as new values are added. It starts empty, then fills up to size 3, and slides forward by removing the oldest value each time a new one is added.

Rest API

class SlidingWindow:
    def __init__(self, size):
        self.size = size
        self.window = []

    def add(self, value):
        if len(self.window) == self.size:
            self.window.pop(0)  # Remove oldest value
        self.window.append(value)

    def get_window(self):
        return self.window

# Create a sliding window of size 3
sliding_window = SlidingWindow(3)

# Add values and print window each time
print('Initial window:', sliding_window.get_window())

values_to_add = [5, 10, 15, 20, 25]
for value in values_to_add:
    sliding_window.add(value)
    print(f'Window after adding {value}:', sliding_window.get_window())

Important Notes

Time complexity of adding a value is O(1) because removing and appending are fast operations.

Space complexity is O(window size) since we only store a fixed number of elements.

A common mistake is forgetting to remove the oldest element when the window is full, which makes the window grow indefinitely.

Use sliding window when you want to process continuous chunks of data efficiently instead of recalculating from scratch.

Summary

The sliding window algorithm helps process data in fixed-size chunks efficiently.

It moves forward by removing the oldest data and adding new data.

This saves time and memory compared to recalculating over the entire data repeatedly.