Sorted Arrays Intersection Editorial

Practice Problem Link: Sorted Arrays Intersection

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

Given 2 sorted arrays, return the intersection of both the arrays. The intersection of 2 arrays means all the elements which are present in both.

Naive Approach

In the naive approach, we maintain hashes of elements of both arrays. Then for each elements in array A, we add min(HashA(A[i]), HashB(A[i])) copies of A[i] into our resultant list, and return it. Keep previous and current counters to keep track of distinct elements in the array only.

Analysis

• Time Complexity: O(n + m)
• Space Complexity: O(Largest Element in A)

Implementation

C++

vector<int> intersection(vector<int> &A, vector<int> &B) {
	vector<int> result;
	int maxElement = *max_element(A.begin(), A.end());
	int hashA[maxElement + 1] = {0};
	int hashB[maxElement + 1] = {0};
	for(int i = 0; i < A.size(); i++) {
		hashA[A[i]]++;
	}
	for(int i = 0; i < B.size(); i++) {
		hashB[B[i]]++;
	}
	int current = 0, previous = -1;
	for(int i = 0; i < A.size(); i++) {
		current = A[i];
		if(current == previous) {
			continue;
		}
		for(int j = 1; j <= min(hashA[A[i]], hashB[A[i]]); j++) {
			result.push_back(A[i]);
		}
		previous = current;
	}
	return result;
}

Java

class Solution {
	List<Integer> intersection (int[] A, int[] B) {
		List<Integer> result = new ArrayList<Integer>();
		int maxElement = Integer.MIN_VALUE;
		for(int i = 0; i < A.length; i++) {
			maxElement = Math.max(maxElement, A[i]);
		}
		for(int i = 0; i < B.length; i++) {
			maxElement = Math.max(maxElement, B[i]);
		}
		int hashA[] = new int[maxElement + 1];
		int hashB[] = new int[maxElement + 1];
		for(int i = 0; i < A.length; i++) {
			hashA[A[i]]++;
		}
		for(int i = 0; i < B.length; i++) {
			hashB[B[i]]++;
		}
		int current = 0, previous = -1;
		for(int i = 0; i < A.length; i++) {
			current = A[i];
			if(current == previous) {
				continue;
			}
			for(int j = 1; j <= Math.min(hashA[A[i]], hashB[A[i]]); j++) {
				result.add(A[i]);
			}
			previous = current;
		}
		return result;
	}
}

Optimal Approach

In the optimal approach, we will use 2 pointers, to merge the intersection of the 2 arrays in a merge-sort-based manner. The Algorithm is :

1. Use two index variables first and second, initial values of both to be set to 0.
2. If arr1[first] is smaller than arr2[second] then increment first.
3. If arr1[first] is greater than arr2[second] then increment second.
4. Else store any of them and increment both index variables.

Analysis

• Time Complexity: O(n + m)
• Space Complexity: O(1)

Implementation

C++

vector<int> intersection(vector<int> &A, vector<int> &B) {
	int first = 0, second = 0, n = A.size(), m = B.size();
	vector<int> result;
	while(first < n && second < m) {
		if(A[first] < B[second]) {
			first++;
		}
		else if(A[first] > B[second]) {
			second++;
		}
		else {
			result.push_back(A[first]);
			first++;
			second++;
		}
	}
	return result;
}

Java

class Solution {
	List<Integer> intersection (int[] A, int[] B) {
		int first = 0, second = 0, n = A.length, m = B.length;
		List<Integer> result = new ArrayList<Integer>();
		while(first < n && second < m) {
			if(A[first] < B[second]) {
				first++;
			}
			else if(A[first] > B[second]) {
				second++;
			}
			else {
				result.add(A[first]);
				first++;
				second++;
			}
		}
		return result;
	}
}