Interesection of two sorted array in linear time

Concept of merge function used
 avatar
BlueDragon2707
java
2 years ago
689 B
3
Indexable
package sort;

public class IntersectionOfTwoSortedArray {

	public static void main(String[] args) {

		int arr1[] = { 2, 15, 20, 20, 30, 40, 60 };
		int arr2[] = { 10, 11, 14, 14, 15, 20, 20, 20, 40, 40 };

		// O/P : 15 20 40

		int i = 0, j = 0;

		while (i < arr1.length && j < arr2.length) {

			if (i > 0 && arr1[i] == arr1[i - 1]) {
				i++;
				continue;
			}

			if (j > 0 && arr2[j] == arr2[j - 1]) {
				j++;
				continue;
			}

			if (arr1[i] < arr2[j])
				i++; // increament the small one (as array is already sorted)
			else if (arr1[i] > arr2[j])
				j++;
			else {
				System.out.println(arr1[i]);
				i++;
				j++;
			}
		}

	}

}
Editor is loading...