Understanding the simultaneous traversal pattern

We traverse an array to search for and perform operations on some data items. However, there are cases where we may need to operate on data items from two arrays of different sizes at once. This requires traversing both arrays at the same time, and the decision to move to the next item in any of those may depend on the outcome of some function. We may move ahead only in one array or in both of them. The simultaneous traversal technique can be used to iterate in both arrays simultaneously in a single pass.

Simultaneous traversal technique

The simultaneous traversal technique is just an extension of traversing in a single array. Consider we have two arrays arr1 and arr2, we maintain two variables, index1 and index2 holding the current index of the first and second array, respectively. In each iteration, based on some condition, we move ahead in either one or both arrays. This process is repeated until any array is traversed completely, which is the terminating condition in most cases. After the simultaneous traversal terminates, we may want to check if any array has still not been completely traversed and process its items.

This technique can be applied to two arrays in multiple ways, depending on the direction of traversal and the number of hops in iteration. We could either traverse from start to end in both arrays, the other way around, or a mix of both. Another variation would be if we hop multiple steps in each array in every iteration instead of just one.

Algorithm

The algorithm below is for a case where we move from start to end in both arrays and only one step in either of them in each iteration based on some condition. It can be easily modified for use with other variations of this pattern.

• Step 1: Initialize two variables `index1` and `index2` with 0
• Step 2: Loop while `index1` < `arr1.size()` and do `index2` < `arr2.size()` and do the following
  • Step 2.1: Decide if we should traverse in the first array. If yes, process `arr1[index1]` and increment `index1`.
  • Step 2.2: Decide if we should traverse in the second array. If yes, process `arr2[index2]` and increment `index2`.
• Step 3: If `arr1` is not fully traversed yet, iterate in `arr1` using `index1` and process all items
• Step 4: If `arr2` is not fully traversed yet, iterate in `arr2` using `index2` and process all items

Implementation

The implementation of the simultaneous traversal technique for the variation described above is given below. It can be modified for use with other variations easily.

Complexity Analysis

The simultaneous traversal technique iterates through two arrays, but each array is completely traversed only once. So, if we have two arrays with sizes N and M, the runtime complexity is linear O(N + M). 

We don't create additional data structures to traverse both arrays, so the space complexity is constant O(1).

Best Case

• Space Complexity - O(1)
• Time Complexity - O(N+M)

Worst Case

• Space Complexity - O(1)
• Time Complexity - O(N+M)