What is the time and space complexity of Intersection of Two Arrays II?

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

Intersection of Two Arrays II

Easy

Concept

Code

Loading editor...

Tap Analyze to see visualization

Click Analyze to visualize

See step-by-step execution, variables, and output

Variables

Run code to see variables

Output

Console output will appear here

Press Space to start•← → to step•? all shortcuts

Solution Guide: Intersection of Two Arrays II

Approach

Sort both arrays first. Use two pointers, one per array. When values are equal, add to the result and advance both. When they differ, advance the pointer at the smaller value to catch up. This naturally handles duplicate counts.

Complexity Analysis

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

Pattern

Two Pointers (Same Direction) + Sort

Why It Works

Sorting groups identical values together. The pointer with the smaller value advances to find a potential match, and matching consumes one occurrence from each array, correctly counting shared duplicates.

Updated Feb 2026