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:

garray671025306364array204567850array3161014

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#

Try it yourself#

C++

Java

Python

Ruby

#include <iostream>
#include <vector>
using namespace std;
int FindLeastCommonNumber(vector<int>& arr1, vector<int>& arr2,
                                             vector<int>& arr3) {
    //TODO: Write - Your - Code
    return -1;
}

#

#include <iostream> #include <vector> using namespace std; int FindLeastCommonNumber(vector<int>& arr1, vector<int>& arr2, vector<int>& arr3) { //TODO: Write - Your - Code return -1; }

Enter to Rename, Shift+Enter to Preview

Test

Need Hint?

Save

Reset

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 $0^{th}$ 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.

Created with Fabric.js 3.6.667102530636404567850161014Iterators pointing towards 0th index of all the arrays.But the values of arrays at 0th index are not the same.

1 of 8

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

C++

Java

Python

Ruby

#include <iostream>
#include <vector>
#include <string>
using namespace std;
int FindLeastCommonNumber(vector<int>& arr1, vector<int>& arr2,
                                             vector<int>& arr3) {
    // Initialize starting indexes for arr1, arr2 and arr3
    int i = 0, j = 0, k = 0;
    while (i < arr1.size() && j < arr2.size() && k < arr3.size()) {
        // Finding the smallest common number
        if ((arr1[i] == arr2[j]) && (arr2[j] == arr3[k])) return arr1[i];
        // Let's increment the iterator
        // for the smallest value.
        if (arr1[i] <= arr2[j] && arr1[i] <= arr3[k]) {
            i++;
        }
        else if (arr2[j] <= arr1[i] && arr2[j] <= arr3[k]) {
            j++;
        }
        else if (arr3[k] <= arr1[i] && arr3[k] <= arr2[j]) {
            k++;
        }
    }
    return -1;
}

#

#include <iostream> #include <vector> #include <string> using namespace std; int FindLeastCommonNumber(vector<int>& arr1, vector<int>& arr2, vector<int>& arr3) { // Initialize starting indexes for arr1, arr2 and arr3 int i = 0, j = 0, k = 0;

Enter to Rename, Shift+Enter to Preview

Run

Save

Reset

Time complexity#

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

Space complexity#

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

Back

Search a Rotated Array

Rotate an Array by N Elements

Mark as Completed

Report an Issue

Prelude

Arrays

Linked Lists

Strings

Stacks and Queues

Trees

Graphs

Further Reading

Find the Smallest Common Number