Problem

Given two sorted arrays, find the intersection (elements present in both arrays).

Examples

Example 1:

1
2

Input: nums1 = [1,1,2,2], nums2 = [2,2]
Output: [2,2]

Example 2:

1
2
3

Input: nums1 = [4,5,9], nums2 = [4,4,8,9,9]
Output: [4,9]
Explanation: [9,4] is also accepted.

Solution

Method 1 - Using two pointers

We will approach this similarly to the “merging” step in merge sort by traversing both sorted arrays simultaneously. Suppose nums1 is indexed by i and nums2 is indexed by j. Then:

  • If nums1[i] == nums2[j], add the element to the intersection.
  • If nums1[i] > nums2[j], increment j.
  • If nums1[i] < nums2[j], increment i.

The space complexity is equivalent to the size of the intersection, which is the minimum of m and n. This question isn’t particularly challenging, but overthinking could lead to failure to answer correctly, negatively impacting your impression.

We have already seen this solution here, but after sorting here - Intersection of Two Arrays 1 - Unique Elements#Method 3 - Binary Search.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

public class Solution {

	public int[] intersect(int[] nums1, int[] nums2) {
		ArrayList<Integer> list = new ArrayList<Integer>();
		int i = 0, j = 0;

		while (i < nums1.length && j  <  nums2.length) {
			if (nums1[i]<nums2[j]) {
				i++;
			} else if (nums1[i] > nums2[j]) {
				j++;
			} else {
				list.add(nums1[i]);
				i++;
				j++;
			}
		}

		int[] result = new int[list.size()];
		int k = 0;
		while (k < list.size()) {
			result[k] = list.get(k);
			k++;
		}

		return result;
	}
}

Complexity

  • ⏰ Time complexity: O(m + n) where m and n is size of of nums1 and nums2.
  • 🧺 Space complexity: O(m) for using ansList