Find common elements in 'n' sorted arrays

Given 'n' sorted arrays, find elements which are common in all of these 'n' arrays. For example,

{23, 34, 67, 89, 123, 566, 1000},
{11, 22, 23, 24,33, 37, 185, 566, 987, 1223, 1234},
{23, 43, 67, 98, 566, 678},
{1, 4, 5, 23, 34, 76, 87, 132, 566, 665},
{1, 2, 3, 23, 24, 344, 566}
for these given arrays, output should be 23 and 566 since these elements are present in all arrays.                        

{1, 3, 4, 4, 5, 43, 67, 98, 566, 678},
{1, 4, 4, 5, 23, 34, 76, 87, 132, 566, 665},
{1, 2, 4, 4, 5, 23, 24, 344, 566}
For above arrays, output should be 1,4,4,5,566,


Video coming soon!



Subscribe for more updates


Preparing for interviews? IDeserve team is here to help.




Algorithm/Insights

Let's first look at an example to try and understand the algorithm.

In the above shown arrays, we start matching for first element 23 from array-0 in all other arrays. We start looking at elements from index-0 and in this case we find an element in all the other arrays which is equal to first element from array-0. Since this element 23 is present in all arrays, we print it out.

Now the interesting part:

As can be seen above, we now start matching for second element 34 from array-0 in all other arrays. Let's specifically look at array-2 matching process. Instead of starting to match element 34 from index 0, now we can directly start matching for element 34 from the index where we last left the matching process(at index = 2) for this array-2. This is because we know that all the arrays are sorted and therefore all elements to the left of element 23 are less than 23 and we are now trying to match for an element which surely is greater than or equal to 23(since array-0 is also sorted). Same is the case for matching process in array-3, array-4 and so on.  

Hopefully, this example has made the algorithm clear.

The algorithm is as following -
We are given 'n' sorted arrays, say array-1, array-2 to array-n. To find out common elements in these arrays, we pick each element starting from element at index 0 from array-1 and check if that element is present in all remaining arrays. To check if an element from array-0(elementArray0) is present in array-'i'(1 <= i <= n), we start looking at the elements in array-'i' starting from 'last checked index' until we find an element which is greater than or equal to element from array-0(elementArray0). This last checked index would be initialized to 0 for all arrays: array-1 to array-n. We stop when we find an element which is greater than or equal to 'elementArray0', save this index as 'last checked index' for array-'i' and proceed to array-'i+1' for matching element 'elementArray0'. Since array-'i' is sorted, we don't need to check for match from index 0 again when we are trying to match the next element from array-0. This 'last checked index' would be used to resume the matching operation for the next element from array-0.

In the worst case, every element from each array would be visited once and hence time complexity of this algorithm is O(m1 + m2 + m3 + .. + mn) where 'mi' is the length of 'i'th array and total number of arrays is 'n'.

Please checkout function printCommonElements(int[][] arrays) in code snippet for implementation details. Feel free to add comments below in case you have any feedback/queries.


Hone your coding skills!




AngryNerds Practice platform »

Algorithm Visualization




Code Snippet

			
package com.ideserve.questions.nilesh;

/**
 * <b>IDeserve <br>
 * <a href="https://www.youtube.com/c/IDeserve">https://www.youtube.com/c/IDeserve</a>
 * Finds common elements in 'n' sorted arrays in linear time. 
 * @author Nilesh
 */
public class CommonElementsSortedArrays 
{
    public static void printCommonElements(int[][] arrays)
    {
        if (arrays.length < 2)
        {
            System.out.println("Too few arrays");
            return;
        }
        
        // to store the current index for 0th array
        int baseIndex = 0;
        
        // to store the current index for each of the remaining n-1 arrays
        int[] indices = new int[arrays.length-1];
        
        // to track in how many arrays a specific element is found 
        int totalMatchFound;
        
        // variable used to terminate the search early 
        boolean smallestArrayTraversalComplete = false;
        /*
         *  pick elements one by one from the first array
         *  and check we find a match for them in all other arrays  
         */
        while ((baseIndex < arrays[0].length) && (!smallestArrayTraversalComplete)) 
        {
            totalMatchFound = 0;
            for (int i = 1; i < arrays.length; i++)
            {
                // get the index for this array where we last stopped
                int currIndex = indices[i-1];
                
                // skip all the elements in this array which are less than the element at baseIndex in 0th array
                while ((currIndex < arrays[i].length) && (arrays[i][currIndex] < arrays[0][baseIndex]))
                {
                    currIndex += 1;
                }
                
                // check if common element(which is equal to element at baseIndex in 0th array) has been found in this array
                if (currIndex < arrays[i].length)
                {
                    if ((arrays[i][currIndex] == arrays[0][baseIndex]))
                    {
                        totalMatchFound += 1;
                    }
                }
                // indicates that we have looked at all the elements of 'i'th array 
                else
                {
                    smallestArrayTraversalComplete = true;
                }
                
                // store this incremented index for this array- 
                // which would help to resume from this point for next matching round
                indices[i-1] = currIndex;
            }
            
            // check if element arrays[0][baseIndex] is found in all other arrays
            if (totalMatchFound == arrays.length-1)
            {
                System.out.println(arrays[0][baseIndex]);
            }
            baseIndex += 1;
        }
    }
    
    
    public static void main(String[] args)
    {
        int[][] arrays = {
                           {23, 34, 67, 89, 123, 566, 1000},
                           {11, 22, 23, 24,33, 37, 185, 566, 987, 1223, 1234},
                           {23, 43, 67, 98, 566, 678},
                           {1, 4, 5, 23, 34, 76, 87, 132, 566, 665},
                           {1, 2, 3, 23, 24, 344, 566}
                         };
        
        printCommonElements(arrays);
    }
}
		

Order of the Algorithm

Time Complexity is O(m1 + m2 + m3 + .. + mn)
Space Complexity is O(n)


Contribution

  • Sincere thanks from IDeserve community to Nilesh More for compiling current post.

    Nilesh More

    Ninja Programmer