[JAVA] Algorithm gymnastics 4

Find the Smallest Common Number From the three integer arrays sorted in ascending order, we need to find the smallest number that is common to all three arrays.

Description

Given three integer arrays sorted in ** ascending order **, implement an algorithm to find the smallest number common to all three arrays.

Let's look at the following three arrays. The solution is ** 6 **, the minimum number common to all arrays.

Tips

1. Take advantage of ascending arrays.
2. Use three pointers.

Solution Runtime Complexity O(n)

Memory Complexity O(1)

Commentary

Consider how to take advantage of the fact that arrays are sorted in ascending order.

Scan each array using three iterators at the same time. You can start by scanning the array from the 0th index, which has the minimum value for each array.

If the values of the array indexes pointed to by the three iterators are equal, Since it is the minimum value that exists in all arrays (because the arrays are sorted in ascending order), that value is returned.

Otherwise, check the iterator that points to the smallest of the three points Increment the iterator to point to the next index.

Returns Null if no common number is found when any of the three iterators reach the end of the array.

Implementation

Test

Output