Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Find common elements out of two sorted array
import java.util.ArrayList;
public class FindCommonElementsInTwoArrays {
public ArrayList<Integer> findCommonElementsOfTwoArray(int[] array1, int[] array2) {
int[] larger = array1;
int[] smaller = array2;
if (array1.length < array2.length) {
larger = array2;
smaller = array1;
}
ArrayList<Integer> commonElementList = new ArrayList<>();
for (int i = 0; i < smaller.length; i++) {
int x = bs(larger, 0, larger.length - 1, smaller[i]);
if (x == smaller[i]) {
commonElementList.add(x);
}
}
return commonElementList;
}
private int bs(int[] numbers, int left, int right, int key) {
if (left <= right) {
int mid = (left + right) / 2;
if (key == numbers[mid]) {
return key;
}
if (key > numbers[mid]) {
return bs(numbers, mid + 1, right, key);
} else {
return bs(numbers, 0, mid - 1, key);
}
}
return -1;
}
}
import static org.junit.Assert.assertEquals;
import java.util.ArrayList;
import org.junit.Before;
import org.junit.Test;
public class FindCommonElementsInTwoArraysTest {
private FindCommonElementsInTwoArrays testClass;
@Before
public void setUp() {
testClass = new FindCommonElementsInTwoArrays();
}
@Test
public void findCommonElemsEx1() {
int[] array1 = { 2, 5, 8, 17, 18, 34, 37, 55 };
int[] array2 = { 3, 4, 5, 18, 31, 32, 55 };
ArrayList<Integer> commonList = testClass.findCommonElementsOfTwoArray(array1, array2);
assertEquals(5, commonList.get(0).intValue());
assertEquals(18, commonList.get(1).intValue());
}
}
@ymohammad

This comment has been minimized.

Copy link

@ymohammad ymohammad commented Mar 24, 2019

We can do this in O(m) as here we assumed both arrays are sorted. The above Algorithm will give O(mlogn) complexity.
Here m - the size of smaller array and n - the size of a bigger array.

Following code will give O(m) time complexity and O(1) space complexity.

public static ArrayList<Integer> getCommonElements(int[] arr1, int[] arr2) {
		int m = arr1.length;
		int n = arr2.length;
		ArrayList<Integer> result = new ArrayList<Integer>();
		int i = 0; int j = 0;
		while (i < m && j < n) {
			if (arr1[i] < arr2[j]) {
				i++;
			} else if (arr1[i] > arr2[j]) {
				j++;
			} else {
				//both are equals
				result.add(arr1[i]);
				i++;
				j++;
			}
		}
		return result;
	}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment