Identifying the sliding window traversal pattern
The sliding window traversal technique can only be applied to some specific problems. These are generally easy or medium where we must apply some operations on either some or all nodes that are a fixed distance apart. If the problem statement or its solution follows the generic template below, it can be solved by applying the sliding window traversal technique.
k from the end or some other node.Example
Let's consider the following problem as an example to better understand how to identify and solve a problem using the simultaneous traversal technique
Problem statement: Given a list and a value `k` remove the kth node from the end.
Remove the 3rd node from the end.
Brute force solution
To delete the kth node from the end in a singly linked list, we need the reference to its previous node (the k+1th node from the end). The brute-force solution first finds the length of the linked list and then identifies the 0-based index of the k+1th node from the end.
If the zero based index of k+1th node is n, iterate n times from the head to get its reference and delete the node after it. We also need to handle the edge case where k equals the length of the linked list, and we delete the head of the list.
Remove the kth node from the end
The implementation of the brute force solution is given as follows.
C++
Java
Typescript
Javascript
Python
The brute-force solution requires two passes through the list: the first to find its length and the second to find the k+1th node from the end to delete the kth node.
Sliding window traversal solution
If we consider the last node of the linked list to be its end, the 1st node from the end is at 0 distance from it, the 2nd node from the end is at a distance of 1 from it, and so the kth node from the end is the node that is at a distance of k-1 before it.
The kth node from the end is k-1 distance before the last node.
If we consider two references start and end that are k-1 distance apart, when the end hits the last node, start holds the reference to the kth node from the end. The problem description fits the generic template for the sliding window traversal pattern we learned earlier.
k-1 distance from the end (last node).We initialize start and end with the head and iterate k-1 times using end to move end k-1 steps ahead of start (which creates a window of size k). If, at the end of these iterations, end hits the last node, it means k equals the length of the list, and we delete the head node. Otherwise, we traverse the list using this window until end hits the last node.
Move end k-1 steps ahead of start.
Since we need the node before the kth node from the end to delete the kth node, before traversing the list using the window, we create another reference variable prevToStart to hold the node before start. We save the previous value of start in prevToStart before updating it as we move the window. This way, when end hits the last node of the list, prevToStart has the reference to the k+1th node from the end, which we can use to delete the kth node from the end.
Remove the kth node from the end
The implementation of the sliding window traversal solution is given as follows.
C++
Java
Typescript
Javascript
Python
As the code above demonstrates, using the sliding window traversal technique, we delete the kth node from the end in a single pass.
Example problems
Most problems that fall under this category are medium problems; a list of a few is given below.
We will now solve these problems to understand the sliding window traversal technique better.