Sorting Problem

Intersection Of Three Sorted Arrays

Problem

Given three arrays sorted in the ascending order, return their intersection sorted array in the ascending order.

Example


{
"arr1": [2, 5, 10],
"arr2": [2, 3, 4, 10],
"arr3": [2, 4, 10]
}

and 

{
"arr1": [1, 2, 3],
"arr2": [],
"arr3": [2, 2]
}



Output:

[2,10] and [-1]

Solution


function find_intersection(arr1, arr2, arr3) {
    let n1 = arr1.length;

    // stores size of arr2
    let n2 = arr2.length;

    // stores size of arr3
    let n3 = arr3.length;

    // stores starting index of arr1
    let i = 0;

    // stores starting index of arr2
    let j = 0;

    // stores starting index of arr3
    let k = 0;
    
    let result = [];

    /*
     * traverses the arrays until 
     * we reach the end of
     * one of the arrays
    */
    while (i < n1 && j < n2 && k < n3) {
        // if the integers appointed by i, j and k are equal
        if (arr1[i] == arr2[j] && arr2[j] == arr3[k]) {
            // prints the common integer
            result.push(arr1[i]);

            // increases i, j and k by 1
            i++; j++; k++;
        }

        /*
         * otherwise, if arr1[i] < arr2[j]
         * we have already found one smaller integer
         * which is arr1[i]
         */
        else if (arr1[i] < arr2[j]) {
            i++; // increases i by 1
        }

        /*
         * otherwise, if arr2[j] < arr3[k]
         * we have got a smaller integer
         * which is arr2[j]
         */
        else if (arr2[j] < arr3[k]) {
            j++; // increases j by 1
        }

        /*
         * otherwise, we consider arr3[k] to be smaller
         */
        else {
            k++; // increases k by 1
        }
    }
    
    return result.length > 0 ? result : [-1];
}

Leave a comment