Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Pinterest
Share On Reddit
Share On Stumbleupon
Contact us
Hide Buttons

Find intersection between Two Sorted Arrays.

Objec­tive: Given two sorted arrays, Find inter­sec­tion point between them.

Exam­ples:

int[] a = { 1, 2, 3, 6, 8, 10 };
int[] b = { 4, 5, 6, 11, 15, 20 };
Output: Intersection point is : 6

Approach:

Naive Approach: Use 2 loops and com­pare each ele­ments in both array and as soon as you find the inter­sec­tion point, return it. Time Com­plex­ity — O(n2).

Bet­ter Approach: Time Com­plex­ity — O(n)

  • Say Arrays are arrA[] and arrB[] and indexes for nav­i­ga­tion are x and y respectively.
  • Since arrays are sorted, com­pare the first ele­ment of both the arrays.(x=0, y=0)
  • If both ele­ments are same, we have our inter­sec­tion point, return it.
  • Else if ele­ment of arrA[x] > ele­ment of arrB[y], increase the arrB[] index, y++.
  • Else if ele­ment of arrA[x] < ele­ment of arrB[y], increase the arrA[] index, x++.
  • If any of the array gets over that means you have not found the inter­sec­tion point. return –1.


Com­plete Code:


Out­put:

Intersection point is : 6

You may also like...

  • Pras­anth RJ

    Dude this doesn’t work . Try this input

    int[] a = { 1, 2, 3, 6, 8, 10 };
    int[] b = { 4, 5, 11, 6, 15, 20 };

    or this

    int[] a = { 1, 2, 3, 6, 8, 10 };
    int[] b = { 4, 5, 11, 15, 6, 20 };

    I have mod­i­fied this

    pack­age com.prasanth.groovy;

    pub­lic class IntersecionPoint2Arrays {

    int inter­sec­tion­Point = –1;
    int x;
    int y;

    pub­lic int intersection(int[] arrA, int[] arrB) {
    while (x < arrA.length) {

    for(int z : arrB)
    {
    if (arrA[x] == z)
    return inter­sec­tion­Point = arrA[x];

    }
    x++;

    }
    return –1;
    }

    pub­lic sta­tic void main(String[] args) throws java.lang.Exception {
    int[] a = { 1, –2, 3, 6, 8, 10 };
    int[] b = { 31, 30, 61, 11, 34, –2 };
    IntersecionPoint2Arrays i = new IntersecionPoint2Arrays();
    System.out.println(“Intersection point is : ” + i.intersection(a, b));

    }
    }

  • Pras­anth RJ

    ooh the pre­con­di­tion says the arrays are sorted .. Then I think the first case fails when both ele­ments show up in the same place …

    eg a[4] = 6 and b[4] = 6

    int[] a = { 1, 2, 3, 6, 8, 10 };
    int[] b = { 4, 5, 11, 6, 15, 20 };

    • Sumit Jain

      is it work­ing fine now?
      sorry for the late response