Intersection of Two Arrays II

1. Define the problem

Given two integer arrays nums1 and nums2, return their intersection , where each element in the result appears as many times as it shows in both arrays. The result can be returned in any order . Sort both arrays first, then use two pointers moving through both, advancing whichever pointer sits on the smaller value until a match is found.

Constraints

1 ≤ nums1.length, nums2.length ≤ 1000
0 ≤ nums1_i, nums2_i ≤ 1000

Example

Inputnums1 = [1, 2, 2, 1], nums2 = [2, 2]

Output[2, 2]

Explanation The value 2 appears twice in nums1 and twice in nums2, so it appears twice in the intersection.

2. Know the words first

In plain terms

Intersection: The values that appear in both lists — if one shopping list has apples and bananas and another has bananas and grapes, their intersection is just bananas.

3. Visualize the solution

Walk sorted nums1 with pointer i, advancing at the smaller value

Statusinit

Sorted nums1 = [1, 1, 2, 2] and sorted nums2 = [2, 2]. i=0 (value 1) vs j=0 (value 2): 1 is smaller, so advance i.

What happens in this step

i = 0 (value 1), j = 0 (value 2)
compare sorted1[i]=1 vs sorted2[j]=2

1 is smaller, so i moves to index 1. Pointer j stays where it is.

Step 1 of 5

Steps to visualize

Sort both arrays in non-decreasing order.
The row below is sorted nums1 = [1, 1, 2, 2]; the frame marks pointer i.
Pointer j walks sorted nums2 = [2, 2]; its position is given in each note.
Advance whichever pointer sits on the smaller value.
When the values match, record it and advance both pointers.
Stop once either pointer reaches the end of its array.

4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Walk sorted nums1 with pointer i, advancing at the smaller value

Statusinit

Sorted nums1 = [1, 1, 2, 2] and sorted nums2 = [2, 2]. i=0 (value 1) vs j=0 (value 2): 1 is smaller, so advance i.

What happens in this step

i = 0 (value 1), j = 0 (value 2)
compare sorted1[i]=1 vs sorted2[j]=2

1 is smaller, so i moves to index 1. Pointer j stays where it is.

Step 1 of 5

5. Solution

Solution

solution.tsTypeScript

function intersect(nums1, nums2) {
  const sorted1 = [...nums1].sort((a, b) => a - b);
  const sorted2 = [...nums2].sort((a, b) => a - b);
  const result = [];
  let i = 0;
  let j = 0;

  while (i < sorted1.length && j < sorted2.length) {
    if (sorted1[i] < sorted2[j]) {
      i++;
    } else if (sorted1[i] > sorted2[j]) {
      j++;
    } else {
      result.push(sorted1[i]);
      i++;
      j++;
    }
  }

  return result;
}

Time: O(n log n + m log m)
Space: O(min(n, m))

6. Test cases

Test cases

Input	Expected	Covers
`nums1 = [1, 2, 2, 1], nums2 = [2, 2]`	`[2, 2]`	example from the docstring
`nums1 = [4, 9, 5], nums2 = [9, 4, 9, 8, 4]`	`[4, 9]`	duplicates on one side only, order preserved by sorting
`nums1 = [1, 2, 3], nums2 = [4, 5, 6]`	`[]`	no shared values between the two arrays
`nums1 = [], nums2 = [1, 2, 3]`	`[]`	one array is empty, so no intersection is possible
`nums1 = [1, 1, 2, 2, 2], nums2 = [1, 2, 2]`	`[1, 2, 2]`	duplicates on both sides with different counts, minimum count wins
`nums1 = [1], nums2 = [1]`	`[1]`	smallest valid input with a match
`nums1 = [1], nums2 = [2]`	`[]`	smallest valid input with no match

Intersection of Two Arrays II