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:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| 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