Understanding the sliding window traversal pattern
The traversal of a linked list is generally done using a single reference variable to hold the current node. Some problems, however, require you to perform some operations on two nodes at some distance from each other. Unlike arrays, where we can access item k steps ahead of the current item by adding k to the current index, we need to iterate k times and traverse the list from the current node for a singly linked list, which is inefficient if we need to do this for multiple nodes.
This presents another use case for the sliding window technique, apart from aggregating values in a subarray or sublist. We can use a window of size k denoted by two references and move it to access all nodes k steps apart in a singly linked list.
The sliding window traversal uses two pointers to traverse the list.
The sliding window technique can also solve aggregation problems on sublists like subarrays. However, in this lesson, we will only learn about the sized sliding window traversal technique, which traverses a list using a sliding window. More so, we will only learn about the fixed-sized sliding window, as most problems require performing operations on nodes apart by a fixed distance.
Sliding window traversal technique
Consider we are given a singly linked list and need to perform some operations on all nodes that are at a distance of k from each other. We create two references start and end, and initialize them with the head of the linked list.
We then iterate k times and move the end reference k steps ahead from start. This way, start and end denote a window of size k+1 such that end is exactly k steps away from start.
k from each other denote a window of size k+1 as both nodes are included in the window.Two nodes that are at a distance of k denote a window of size k+1 as the window includes both the nodes.
We perform the required operations on the nodes held in start and end and move both of them one step ahead by setting them to their respective next nodes. We repeat this process until end hits null at the end of the list. At the end of all iterations, we would have applied the given operation on all nodes that are k steps away from each other.
Consider the example below with a window of size 3. (k = 3)
Sliding window traversal to process nodes apart by distance k
Algorithm
The algorithm given below outlines the sliding window traversal technique for a window of size k.
- Step 1: Initialize two references, `start` and `end` to the head of the list.
- Step 2: Iterate k times using a loop and move `end` reference k steps ahead
- Step 3: Loop while `end` != `null` and do the following
- Step 3.1: Process nodes held in `start` and `end` as they are k steps apart
- Step 3.2: Move both `start` and `end` one step ahead by setting them to their next nodes.
Implementation
Given below is the generic code implementation of the fixed-size sliding window traversal technique on a linked list with window size k using references start and end as the boundaries of the window.
C++
Java
Typescript
Javascript
Python
Complexity Analysis
The algorithm's time and space complexity is easy to understand. We create a sliding window of size k and move it one step at a time until it hots null at the end of the list. The variable end iterates from 0 to N-1, where N is the size of the list. So, the runtime complexity is linear O(N).
Since we do not create a new data structure, the space complexity is constant O(1).
Best Case
- Space Complexity - O(1)
- Time Complexity - O(N)
Worst Case
- Space Complexity - O(1)
- Time Complexity - O(N)
Later in the course, we will examine techniques for identifying problems that can be solved using the sliding window traversal technique and walk through an example to better understand it.