Skip to main content

86. Intersection of Two Arrays II

easyAsked at Workday

Return the intersection of two integer arrays preserving duplicate counts. Workday uses this for hash-map counting — same shape as 'employees who appear in both the active roster and the payroll batch'.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Workday loops.

  • Glassdoor (2025)— Workday SDE1 phone screen.

Problem

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.

Constraints

  • 1 <= nums1.length, nums2.length <= 1000
  • 0 <= nums1[i], nums2[i] <= 1000
  • Follow-up: What if the given array is already sorted?
  • What if nums1's size is small compared to nums2's size?
  • What if elements of nums2 are stored on disk?

Examples

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]

Approaches

1. Sort both + two pointers

Sort, then walk both with pointers.

Time
O(n log n + m log m)
Space
O(1) extra)
nums1.sort(); nums2.sort();
let i=0,j=0,res=[];
while (i<nums1.length && j<nums2.length) {
  if (nums1[i]<nums2[j]) i++;
  else if (nums1[i]>nums2[j]) j++;
  else { res.push(nums1[i]); i++; j++; }
}
return res;

Tradeoff: Two pointers — good when arrays are already sorted (follow-up).

2. Hash map count

Count one array. Walk the other, decrementing counts and emitting matches.

Time
O(n + m)
Space
O(min(n, m))
function intersect(nums1, nums2) {
  if (nums1.length > nums2.length) return intersect(nums2, nums1);
  const counts = new Map();
  for (const x of nums1) counts.set(x, (counts.get(x) || 0) + 1);
  const result = [];
  for (const x of nums2) {
    if (counts.get(x) > 0) {
      result.push(x);
      counts.set(x, counts.get(x) - 1);
    }
  }
  return result;
}

Tradeoff: O(n + m) time, O(min) space. Counting the smaller array minimizes the hash map size.

Workday-specific tips

Workday loves the follow-up questions on this one. Discuss the disk-storage variant: external sort + two-pointer streaming. Always count the smaller array first.

Common mistakes

  • Using a Set instead of Map — drops duplicate counts.
  • Counting the larger array — wastes memory.
  • Decrementing without checking > 0 — emits duplicates beyond actual count.

Follow-up questions

An interviewer at Workday may pivot to one of these next:

  • Intersection of Two Arrays (LC 349) — distinct elements only.
  • Already-sorted version — two pointers, O(1) extra space.
  • Disk-resident nums2 — external sort or streaming.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Which to count?

The smaller array. The hash map is sized by distinct elements of whichever you count — pick smaller for memory.

Sorted variant?

Two pointers, no extra map. O(n + m) time, O(1) extra space.

Practice these live with InterviewChamp.AI

Drill Intersection of Two Arrays II and other Workday interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →