Objective: Given two sorted arrays, Find intersection point between them.
Examples:
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 compare each elements in both array and as soon as you find the intersection point, return it. Time Complexity – O(n2).
Better Approach: Time Complexity – O(n)
- Say Arrays are arrA[] and arrB[] and indexes for navigation are x and y respectively.
- Since arrays are sorted, compare the first element of both the arrays.(x=0, y=0)
- If both elements are same, we have our intersection point, return it.
- Else if element of arrA[x] > element of arrB[y], increase the arrB[] index, y++.
- Else if element of arrA[x] < element of arrB[y], increase the arrA[] index, x++.
- If any of the array gets over that means you have not found the intersection point. return -1.
Complete Code:
| 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
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 modified this
package com.prasanth.groovy;
public class IntersecionPoint2Arrays {
int intersectionPoint = -1;
int x;
int y;
public int intersection(int[] arrA, int[] arrB) {
while (x < arrA.length) {
for(int z : arrB)
{
if (arrA[x] == z)
return intersectionPoint = arrA[x];
}
x++;
}
return -1;
}
public static 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));
}
}
Question says Sorted array. :/
ooh the precondition says the arrays are sorted .. Then I think the first case fails when both elements 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 };
is it working fine now?
sorry for the late response