How to do the intersection of two sorted arrays?

How to do the intersection of two sorted arrays?

Add Comment


  • 4 Answer(s)

    Logic:

    print the element if the element is present or available in both the arrays.

    • Use two index variables i and j, after that initial the values i = 0, j = 0
    • If arr01 [i] is smaller than arr02 [j] then increment i.
    • If arr01 [i] is greater than arr02 [j] then increment j.
    • If both are same then print any of them and increment both i and j.
    Answered on February 19, 2019.
    Add Comment

    Clues –

    Solution must be O(M + N) in time and O(min(M, N)) space.
    Can you apply merge sort’s merging logic here?
    Solution – This is simple, we can do this in O(M + N) time, where M and N are the array lengths. What we will do here is similar to the “merging” step in merge sort. We will traverse the two sorted arrays simultaneously. Let’s say the first array, A, is indexed by i, and the second array, B, is indexed by j, then,

    A[i] == B[j] – then add it to the intersection.
    A[i] > B[j] – then increment j.
    A[i] B[j]) {
    // Increment index to second array
    ++j;
    } else {
    // A[i] < B[j]
    // Increment index to first array
    ++i;
    }
    }

    return intersection;
    }

    Answered on February 19, 2019.
    Add Comment
    public class IntersecionPoint2Arrays {
    int intersectionPoint = 1;
    int x;
    int y;
    public int intersection(int[] arrA, int[] arrB) {
    while (x < arrA.length && y < arrB.length) {
    if (arrA[x] > arrB[y])
    y++;
    else if (arrA[x] < arrB[y])
    x++;
    else {
    intersectionPoint = arrA[x];
    return intersectionPoint;
    }
    }
    return intersectionPoint;
    }
    public static void main(String[] args) throws java.lang.Exception {
    int[] a = { 1, 2, 3, 6, 8, 10 };
    int[] b = { 4, 5, 6, 11, 15, 20 };
    IntersecionPoint2Arrays i = new IntersecionPoint2Arrays();
    System.out.println(Intersection point is : + i.intersection(a, b));
    }
    }

    Output:

    Intersection point is : 6
    Answered on February 20, 2019.
    Add Comment

    Given two unsorted arrays that represent two sets (elements in every array are distinct), find union and intersection of two arrays.

    For example, if the input arrays are:
    arr1[] = {7, 1, 5, 2, 3, 6}
    arr2[] = {3, 8, 6, 20, 7}
    Then your program should print Union as {1, 2, 3, 5, 6, 7, 8, 20} and Intersection as {3, 6}. Note that the elements of union and intersection can be printed in any order.

    Answered on February 21, 2019.
    Add Comment


  • Your Answer

    By posting your answer, you agree to the privacy policy and terms of service.