Find the Smallest Common Number

Statement#

We’re given three integer arrays, each sorted in ascending order. Return the smallest number common in all three arrays. In case no number is common, return -1.

Example#

Let’s look at the three arrays below, where $6$​ is the smallest number that is common in all the arrays:

Sample input#

v1 = [6, 7, 10, 25, 30, 63, 64]
v2 = [0, 4, 5, 6, 7, 8, 50]
v3 = [1, 6, 10, 14]

Expected output#

6

Try it yourself#

Solution#

• The arrays are sorted in ascending order. We will use three iterators simultaneously to traverse each of the arrays. We can start traversing each array from the 0th0^{th}0th index, which always has the smallest value.
• If the values pointed to by the three iterators are equal, that is the solution. Since the arrays are sorted in ascending order, that value must be the smallest value present in all of the arrays.
• Otherwise, we see which of the three iterators points to the smallest value and increment that iterator so that it points to the next index.
• If any of the three iterators reaches the end of the array before we find the common number, we return -1.

Let’s visualize the step by step implementation of the solution described above.

Let’s take a look at the solution code below:

Time complexity#

The time complexity of the solution is linear, $O(n)$.

Space complexity#

The space complexity of the solution is constant, $O(1)$.