Sliding Window

Sliding windows provide a fixed width view into a list that moves along the length of the list. If used properly it can reduce the time complexity of a problem.

Implementing a sliding window

const std = @import("std");

pub fn main() void {
  const data = [_]i32{ 1, 2, 3, 4, 5, 6, 7, 8 };
  const window_size = 4;

  // +1 ensures the loop includes the last valid window.
  for (0..(data.len - window_size + 1)) |i| {
    // window represents a slice of size `window_size` of `data`.
    const window = data[i..(i + window_size)];
    std.debug.print("Window {d}: {any}\n", .{i, window});
  }
}

In the example above we implement a sliding window of size 4 elements on an array of 8 elements. Let’s step through each iteration until we view the entire length of the data array.

To do this we use the formula data.len - window_size + 1. Our for loop starts with 0 and iterates a number of times provided by our formula which tells us how many iterations we’ll need, given a window size, to view the entire length of the array. For the code above this is 0 through 4 (5 iterations).

Let’s step through each iteration to see what’s going on.