Intersection of Two Sorted Arrays with Distinct Elements

Last Updated : 04 Oct, 2024

Given two sorted arrays a[] and b[] with distinct elements of size n and m respectively, the task is to find intersection (or common elements) of the two arrays. We need to return the intersection in sorted order.

Note: Intersection of two arrays can be defined as a set containing distinct common elements between the two arrays.

Examples:

Input: a[] = { 1, 2, 4, 5, 6 }, b[] = { 2, 4, 7, 9 }
Output: { 2, 4 }
Explanation: The common elements in both arrays are 2 and 4.

Input: a[] = { 2, 3, 4, 5 }, b[] = { 1, 7 }
Output: { }
Explanation: There are no common elements in array a[] and b[].

Table of Content

Approaches Same as Unsorted Arrays with distinct elements – Best Time O(n+m) and O(n) Space

The idea is to use the same approaches as discussed in Intersection of Two Arrays with Distinct Elements. The most optimal approach among them is to use Hash Set which has a time complexity of O(n+m) and Auxiliary Space of O(n).

[Expected Approach] Using Merge Step of Merge Sort - O(n+m) Time and O(1) Space

The idea is to find the intersection of two sorted arrays using merge step of merge sort. We maintain two pointers to traverse both arrays simultaneously.
If the element in first array is smaller, move the pointer of first array forward because this element cannot be part of the intersection.
If the element in second array is smaller, move the pointer of second array forward.
If both elements are equal, add one of them and move both the pointers forward.
This continues until one of the pointers reaches the end of its array.

C++

// C++ program for intersection of  // two sorted arrays with distinct elements #include <iostream> #include <vector> using namespace std; vector<int> intersection(vector<int>& a, vector<int>& b) {  vector<int> res;    int i=0;  int j=0;    // Start simultaneous traversal on both arrays  while (i < a.size() && j < b.size()) {    // if a[i] is smaller, then move in a[]   // towards larger value  if(a[i] < b[j]) {  i++;  }     // if b[j] is smaller, then move in b[]  // towards larger value  else if (a[i] > b[j]) {  j++;  }     // if a[i] == b[j], then this element is common  // add it to result array and move in both arrays  else {  res.push_back(a[i]);  i++;   j++;  }  }    return res; } int main() {  vector<int> a = {1, 2, 4, 5, 6};   vector<int> b = {2, 4, 7, 9};  vector<int> res = intersection(a, b);    for (int i = 0; i < res.size(); i++)   cout << res[i] << " ";  return 0; }

// C program for intersection of  // two sorted arrays with distinct elements #include <stdio.h> int* intersection(int a[], int b[], int n, int m, int *size) {  int* res = (int*) malloc(n * sizeof(int));  *size = 0;  int i = 0;  int j = 0;   // Start simultaneous traversal on both arrays  while (i < n && j < m) {    // if a[i] is smaller, then move in a[]   // towards larger value  if (a[i] < b[j]) {  i++;  }     // if b[j] is smaller, then move in b[]  // towards larger value  else if (a[i] > b[j]) {  j++;  }     // if a[i] == b[j], then this element is common  // add it to result array and move in both arrays  else {  res[(*size)++] = a[i];  i++;   j++;  }  }  return res; } int main() {  int a[] = {1, 2, 4, 5, 6};   int b[] = {2, 4, 7, 9};  int size;  int* res = intersection(a, b, 5, 4, &size);    for (int i = 0; i < size; i++)   printf("%d ", res[i]);  return 0; }

Java

// Java program for intersection of  // two sorted arrays with distinct elements import java.util.ArrayList; class GfG {  static ArrayList<Integer> intersection(int[] a, int[] b) {  ArrayList<Integer> res = new ArrayList<>();    int i = 0;  int j = 0;  // Start simultaneous traversal on both arrays  while (i < a.length && j < b.length) {    // if a[i] is smaller, then move in a[]   // towards larger value  if (a[i] < b[j]) {  i++;  }     // if b[j] is smaller, then move in b[]  // towards larger value  else if (a[i] > b[j]) {  j++;  }     // if a[i] == b[j], then this element is common  // add it to result array and move in both arrays  else {  res.add(a[i]);  i++;   j++;  }  }  return res;  }  public static void main(String[] args) {  int[] a = {1, 2, 4, 5, 6};   int[] b = {2, 4, 7, 9};  ArrayList<Integer> res = intersection(a, b);    for (int i = 0; i < res.size(); i++)   System.out.print(res.get(i) + " ");  } }

Python

# Python program for intersection of  # two sorted arrays with distinct elements def intersection(a, b): res = [] i = 0 j = 0 # Start simultaneous traversal on both arrays while i < len(a) and j < len(b): # if a[i] is smaller, then move in a[]  # towards larger value if a[i] < b[j]: i += 1 # if b[j] is smaller, then move in b[] # towards larger value elif a[i] > b[j]: j += 1 # if a[i] == b[j], then this element is common # add it to result array and move in both arrays else: res.append(a[i]) i += 1 j += 1 return res if __name__ == "__main__": a = [1, 2, 4, 5, 6] b = [2, 4, 7, 9] res = intersection(a, b) for i in range(len(res)): print(res[i], end=" ")

// C# program for intersection of  // two sorted arrays with distinct elements using System; using System.Collections.Generic; class GfG {  static List<int> intersection(int[] a, int[] b) {  List<int> res = new List<int>();    int i = 0;  int j = 0;  // Start simultaneous traversal on both arrays  while (i < a.Length && j < b.Length) {    // if a[i] is smaller, then move in a[]   // towards larger value  if (a[i] < b[j]) {  i++;  }     // if b[j] is smaller, then move in b[]  // towards larger value  else if (a[i] > b[j]) {  j++;  }     // if a[i] == b[j], then this element is common  // add it to result array and move in both arrays  else {  res.Add(a[i]);  i++;   j++;  }  }  return res;  }  static void Main() {  int[] a = {1, 2, 4, 5, 6};   int[] b = {2, 4, 7, 9};  List<int> res = intersection(a, b);    for (int i = 0; i < res.Count; i++)   Console.Write(res[i] + " ");  } }

JavaScript

// JavaScript program for intersection of  // two sorted arrays with distinct elements function intersection(a, b) {  const res = [];    let i = 0;  let j = 0;  // Start simultaneous traversal on both arrays  while (i < a.length && j < b.length) {    // if a[i] is smaller, then move in a[]   // towards larger value  if (a[i] < b[j]) {  i++;  }     // if b[j] is smaller, then move in b[]  // towards larger value  else if (a[i] > b[j]) {  j++;  }     // if a[i] == b[j], then this element is common  // add it to result array and move in both arrays  else {  res.push(a[i]);  i++;   j++;  }  }  return res; } const a = [1, 2, 4, 5, 6];  const b = [2, 4, 7, 9]; const res = intersection(a, b); console.log(res.join(' '));

Output

2 4

Time Complexity: O(n + m), where n and m are size of array a[] and b[] respectively.
Auxiliary Space: O(1)

[Alternate Approach 1] Using Binary Search - O(n * log (m)) Time and O(1) Space

The idea is to check each element of array a[] and see if it is in array b[]. If it is, we add it to the result array. Since b[] is already sorted, we can use binary search to find the elements in log(n) time.

C++

// C++ program for intersection of two sorted arrays  // with distinct elements using Binary Search #include <iostream> #include <vector> using namespace std; // Function to perform binary search int binarySearch(vector<int> &arr, int lo, int hi, int target) {  while (lo <= hi){  int mid = lo + (hi - lo) / 2;  if (arr[mid] == target)  return mid;  if (arr[mid] < target)  lo = mid + 1;  else  hi = mid - 1;  }  return -1; } vector<int> intersection(vector<int>& a, vector<int>& b) {  vector<int> res;  // Traverse through array a[] and search every   // element a[i] in array b[]  for (int i = 0; i < a.size(); i++) {     // If found in b[], then add this  // element to result array  if (binarySearch(b, 0, b.size()-1, a[i]) != -1) {   res.push_back(a[i]);  }  }  return res; } int main() {  vector<int> a = {1, 2, 4, 5, 6};   vector<int> b = {2, 4, 7, 9};  vector<int> res = intersection(a, b);    for (int i = 0; i < res.size(); i++)   cout << res[i] << " ";  return 0; }

// C program for intersection of two sorted arrays  // with distinct elements using Binary Search #include <stdio.h> int binarySearch(int arr[], int lo, int hi, int target) {  while (lo <= hi) {  int mid = lo + (hi - lo) / 2;    if (arr[mid] == target)  return mid;  if (arr[mid] < target)  lo = mid + 1;  else  hi = mid - 1;  }  return -1; } int* intersection(int a[], int b[], int n, int m, int *size) {  *size = 0;  int* res = (int*) malloc(n * sizeof(int));    // Traverse through array a[] and search every   // element a[i] in array b[]  for (int i = 0; i < n; i++) {    // If found in b[], then add this  // element to result array  if (binarySearch(b, 0, m - 1, a[i]) != -1) {   res[(*size)++] = a[i];  }  }  return res; } int main() {  int a[] = {1, 2, 4, 5, 6};   int b[] = {2, 4, 7, 9};  int size;    int* res = intersection(a, b, 5, 4, &size);    for (int i = 0; i < size; i++)   printf("%d ", res[i]);  return 0; }

Java

// Java program for intersection of two sorted arrays  // with distinct elements using Binary Search import java.util.ArrayList; class GfG {    // Function to perform binary search  static int binarySearch(int[] arr, int lo, int hi, int target) {  while (lo <= hi) {  int mid = lo + (hi - lo) / 2;    if (arr[mid] == target)  return mid;  if (arr[mid] < target)  lo = mid + 1;  else  hi = mid - 1;  }  return -1;  }  static ArrayList<Integer> intersection(int[] a, int[] b) {  ArrayList<Integer> res = new ArrayList<>();  // Traverse through array a[] and search every   // element a[i] in array b[]  for (int i = 0; i < a.length; i++) {    // If found in b[], then add this  // element to result array  if (binarySearch(b, 0, b.length - 1, a[i]) != -1) {   res.add(a[i]);  }  }  return res;  }  public static void main(String[] args) {  int[] a = {1, 2, 4, 5, 6};   int[] b = {2, 4, 7, 9};  ArrayList<Integer> res = intersection(a, b);    for (int i = 0; i < res.size(); i++)   System.out.print(res.get(i) + " ");  } }

Python

# Python program for intersection of two sorted arrays  # with distinct elements using Binary Search def binarySearch(arr, lo, hi, target): while lo <= hi: mid = lo + (hi - lo) // 2 if arr[mid] == target: return mid if arr[mid] < target: lo = mid + 1 else: hi = mid - 1 return -1 def intersection(a, b): res = [] # Traverse through array a[] and search every  # element a[i] in array b[] for i in range(len(a)): # If found in b[], then add this # element to result array if binarySearch(b, 0, len(b) - 1, a[i]) != -1: res.append(a[i]) return res if __name__ == "__main__": a = [1, 2, 4, 5, 6] b = [2, 4, 7, 9] res = intersection(a, b) for i in range(len(res)): print(res[i], end=" ")

// C# program for intersection of two sorted arrays  // with distinct elements using Binary Search using System; using System.Collections.Generic; class GfG {    // Function to perform binary search  static int binarySearch(int[] arr, int lo, int hi, int target) {  while (lo <= hi) {  int mid = lo + (hi - lo) / 2;  if (arr[mid] == target)  return mid;  if (arr[mid] < target)  lo = mid + 1;  else  hi = mid - 1;  }  return -1;  }  static List<int> intersection(int[] a, int[] b) {  List<int> res = new List<int>();  // Traverse through array a[] and search every   // element a[i] in array b[]  for (int i = 0; i < a.Length; i++) {    // If found in b[], then add this  // element to result array  if (binarySearch(b, 0, b.Length - 1, a[i]) != -1) {   res.Add(a[i]);  }  }  return res;  }  static void Main() {  int[] a = {1, 2, 4, 5, 6};   int[] b = {2, 4, 7, 9};  List<int> res = intersection(a, b);    for (int i = 0; i < res.Count; i++)   Console.Write(res[i] + " ");  } }

JavaScript

// JavaScript program for intersection of two sorted arrays  // with distinct elements using Binary Search function binarySearch(arr, lo, hi, target) {  while (lo <= hi) {  const mid = lo + Math.floor((hi - lo) / 2);    if (arr[mid] === target)  return mid;  if (arr[mid] < target)  lo = mid + 1;  else  hi = mid - 1;  }  return -1; } function intersection(a, b) {  const res = [];  // Traverse through array a[] and search every   // element a[i] in array b[]  for (let i = 0; i < a.length; i++) {    // If found in b[], then add this  // element to result array  if (binarySearch(b, 0, b.length - 1, a[i]) !== -1) {   res.push(a[i]);  }  }  return res; } const a = [1, 2, 4, 5, 6];  const b = [2, 4, 7, 9]; const res = intersection(a, b); console.log(res.join(' '));