# 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