Identifying the simultaneous traversal pattern
The simultaneous traversal technique can only be applied to some specific problems. These are generally easy problems in which we must apply some function to the items of more than one array at once and iterate in some or all based on the outcome. Most problems have only two arrays, but some problems can have more than two. If the problem statement or its solution follows the generic template below, it can be solved by applying the simultaneous traversal technique.
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 two arrays `s` and `t`, check if `s` is a subsequence of `t`.
Find if array s is a subsequence of array t.
Brute force solution
The simplest brute-force solution to this problem is to pick the first item in s and traverse in the array t until we find the first occurrence of that item in t. We then pick the next item in s and traverse t from where we left off earlier until we find the first occurrence of the next item. We repeat this process and return true if we find all the items of s in t this way. Otherwise, if we reach the end of t while some items in s still remain, we return false.
Find if array s is a subsequence of array t
The implementation of the brute force solution is given as follows.
C++
Java
Typescript
Javascript
Python
The brute force implementation traverses both arrays simultaneously and is functionally equivalent to the implementation of the simultaneous traversal solution, which we will learn later. However, it is quite complicated and error-prone.
Simultaneous traversal solution
A solution to this problem is to compare the characters in both arrays and iterate in both s and t if they are equal; otherwise, we only iterate in t. This fits the generic template from the simultaneous traversal pattern we learned earlier.
We start from the first item in both arrays; if they are different, we move ahead only in t hoping we find the character ahead in t. Otherwise, if there is a match, we move ahead in both s and t to search for the next character from s in t. This way, we fix a character from s and search for it in t. Once we find it in t, we search for the next character from s in t in the same way.
Find if array s is a subsequence of array t using simultaneous traversal.
The implementation of the simultaneous traversal solution is given as follows.
C++
Java
Typescript
Javascript
Python
The above implementation is functionally the same as the brute force implementation but uses the template code of the simultaneous traversal technique. It is cleaner, much easier to understand, and less error-prone.
Example problems
Most problems that fall under this category are easy problems; a list of a few is given below.
We will now solve these problems to understand the simultaneous traversal technique better.