Scale Engineer

Intersection of Two Arrays II

Easy
#0337Time: O(n log n + m log m), where `n` and `m` are the lengths of the arrays. The dominant operation is sorting. The two-pointer scan takes linear time, O(n + m).Space: O(log n + log m) to O(n + m), depending on the implementation of the sorting algorithm used by the language's standard library. This does not include the space for the result list, which is O(min(n, m)).1 company
Patterns
Two Pointers
Algorithms
Binary SearchSorting
Data structures
ArrayHash Table
Companies
Yandex

Prompt

Given two integer arrays nums1 and nums2, return an array of their intersection. Each element in the result must appear as many times as it shows in both arrays and you may return the result in any order.

 

Example 1:

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

Example 2:

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

 

Constraints:

  • 1 <= nums1.length, nums2.length <= 1000
  • 0 <= nums1[i], nums2[i] <= 1000

 

Follow up:

  • What if the given array is already sorted? How would you optimize your algorithm?
  • What if nums1's size is small compared to nums2's size? Which algorithm is better?
  • What if elements of nums2 are stored on disk, and the memory is limited such that you cannot load all elements into the memory at once?

Approaches

3 approaches with complexity analysis and trade-offs.

This approach first sorts both arrays. Then, it uses two pointers to iterate through the sorted arrays simultaneously. By comparing the elements at the pointers, we can find the common elements efficiently in a single pass after sorting.

Algorithm

  • Sort both input arrays, nums1 and nums2.
  • Initialize two pointers, i = 0 for nums1 and j = 0 for nums2.
  • Initialize an empty list intersection.
  • While i < nums1.length and j < nums2.length:
    • If nums1[i] < nums2[j], increment i.
    • Else if nums1[i] > nums2[j], increment j.
    • Else (if nums1[i] == nums2[j]):
      • Add nums1[i] to the intersection list.
      • Increment both i and j.
  • Convert the intersection list to an array and return it.

Walkthrough

A more efficient way to solve the problem is to first sort both arrays. Once sorted, we can use a two-pointer technique. We initialize one pointer at the beginning of each array. We then compare the elements at the two pointers:

  • If the element in nums1 is smaller, we advance the pointer for nums1 because we need to find a larger value to match the current element in nums2.
  • If the element in nums2 is smaller, we advance the pointer for nums2 for the same reason.
  • If the elements are equal, we have found a common element. We add it to our result list and advance both pointers to look for the next potential match. This process continues until one of the pointers goes past the end of its array.

This approach is particularly effective if the arrays are already sorted (a follow-up question), as the sorting step can be skipped, making the algorithm run in linear time.

import java.util.ArrayList;import java.util.Arrays;import java.util.List; class Solution {    public int[] intersect(int[] nums1, int[] nums2) {        Arrays.sort(nums1);        Arrays.sort(nums2);                int i = 0, j = 0;        List<Integer> intersection = new ArrayList<>();                while (i < nums1.length && j < nums2.length) {            if (nums1[i] < nums2[j]) {                i++;            } else if (nums1[i] > nums2[j]) {                j++;            } else {                intersection.add(nums1[i]);                i++;                j++;            }        }                // Convert List to array        int[] result = new int[intersection.size()];        for (int k = 0; k < intersection.size(); k++) {            result[k] = intersection.get(k);        }        return result;    }}

Complexity

Time

O(n log n + m log m), where `n` and `m` are the lengths of the arrays. The dominant operation is sorting. The two-pointer scan takes linear time, O(n + m).

Space

O(log n + log m) to O(n + m), depending on the implementation of the sorting algorithm used by the language's standard library. This does not include the space for the result list, which is O(min(n, m)).

Trade-offs

Pros

  • Very efficient if the arrays are already sorted (O(n + m) time).

  • Space-efficient, especially if an in-place sort with logarithmic space is used.

Cons

  • The sorting step can be costly if the arrays are large and unsorted.

  • Modifies the original arrays if sorted in-place, which might not be desirable.

Solutions

public class Solution {    public int[] Intersect(int[] nums1, int[] nums2) {        HashSet < int > hs1 = new HashSet < int > (nums1.Concat(nums2).ToArray());        Dictionary < int, int > dict = new Dictionary < int, int > ();        List < int > result = new List < int > ();        foreach(int x in hs1) {            dict[x] = 0;        }        foreach(int x in nums1) {            if (dict.ContainsKey(x)) {                dict[x] += 1;            } else {                dict[x] = 1;            }        }        foreach(int x in nums2) {            if (dict[x] > 0) {                result.Add(x);                dict[x] -= 1;            }        }        return result.ToArray();    }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem