Intersection of two arrays

Given two integer arrays nums1 and nums2, sorted in non-decreasing order, return their intersection in sorted order.

The intersection must contain each element common to both arrays exactly once.

Brute Force Approach

The most direct idea is to take each element from nums1 and search the complete nums2 array for the same value.

Finding a match confirms that the element belongs to both arrays. A second search inside the result prevents repeated common values from being added more than once.

Algorithm

• Create an empty intersectionResult to store distinct values that are present in both arrays.

• Traverse nums1 from left to right and search the complete nums2 array for the current value to determine whether it belongs to both arrays.

• If no matching value exists in nums2, ignore the current element because it cannot be part of the intersection.

• If a match is found, search intersectionResult to check whether the value has already been added, preventing duplicate entries.

• Append the value only when it is not already present. Since nums1 is sorted and processed from left to right, the collected distinct values remain sorted.

• Return intersectionResult after every value of nums1 has been checked.

Dry Run

Solution

Complexity Analysis

Time Complexity: O(N × M), where N and M represent the sizes of nums1 and nums2. Each value of nums1 may require scanning the complete nums2 array. Searching the developing result adds at most O(N × R) work, where R ≤ M, so the overall worst-case complexity remains O(N × M).

Space Complexity: O(1) auxiliary space when returned output storage is excluded. The returned intersection requires O(R) space.

Better Approach

Repeatedly scanning nums2 makes the Brute Force Approach expensive. A hash set can remember all distinct values from one array and answer membership questions much faster.

A second set can collect matching values without allowing duplicates. Since hash sets do not preserve sorted order, the collected intersection must be sorted before being returned.

Algorithm

• Create firstSet and insert every value from nums1, allowing membership checks to be performed in average constant time while automatically ignoring duplicates.

• Create an empty intersectionSet to store values confirmed in both arrays without allowing repeated result entries.

• Traverse nums2 and check whether each current value exists in firstSet.

• If the value exists, insert it into intersectionSet, since it is present in both input arrays.

• Convert intersectionSet into intersectionResult and sort it because hash-set traversal does not guarantee sorted order.

• Return intersectionResult as the distinct sorted intersection.

Dry Run

Solution

Complexity Analysis

Time Complexity: O(N + M + R log R) on average, where N and M represent the input sizes and R represents the number of distinct common elements. Building and checking the hash sets requires O(N + M) average time, while sorting the result requires O(R log R) time.

Space Complexity: O(N + R) auxiliary space because firstSet may store every distinct value from nums1, while intersectionSet stores the distinct common values. Building firstSet from the smaller input array can reduce this to O(min(N, M) + R).

Optimal Approach

The sorted order allows both arrays to be examined together. When the current values differ, the smaller value cannot match the current larger value or any later value in the other array.

Moving the pointer at the smaller value safely removes that impossible candidate. Equal values belong to the intersection, so one copy is collected before both pointers move forward.

Algorithm

• Create an empty intersectionResult and initialize i = 0 and j = 0, where each pointer represents the smallest unprocessed value in its corresponding sorted array.

• Compare nums1[i] and nums2[j] while both pointers remain within their arrays.

• If nums1[i] < nums2[j], move i forward because the current value from nums1 is too small to match nums2[j] or any value appearing after it.

• If nums2[j] < nums1[i], move j forward for the same reason.

• If both values are equal, append the value only when it differs from the last stored result value, then move both pointers because both current occurrences have been processed.

• Return intersectionResult when either array is exhausted, since no additional common value can exist after that point.

Dry Run

Solution

Complexity Analysis

Time Complexity: O(N + M), where N and M represent the sizes of nums1 and nums2. Pointer i processes every value from nums1 at most once, while pointer j processes every value from nums2 at most once.

Space Complexity: O(1) auxiliary space when returned output storage is excluded. The returned intersection array requires O(R) space, where R represents the number of distinct common elements.

FAQs

Q1. Why is checking only the final result value enough to remove duplicates in the Optimal Approach?

Both arrays are processed in sorted order, so repeated equal candidates arrive consecutively. Any duplicate match must therefore equal the most recently inserted result value.

Q2. What changes when duplicate occurrences must be preserved in the intersection?

The number of copies added for a value must equal the smaller frequency across both arrays. During two-pointer traversal, every equal pair contributes one copy before both pointers move.

Q3. Can the two-pointer approach work when the input arrays are unsorted?

No. Moving the pointer containing the smaller value is safe only because all later values are at least as large. Unsorted arrays require sorting first or using hash-based frequency or membership structures.

Q4. How can the Better Approach use less auxiliary space?

Store the values of the smaller input array inside the membership set and traverse the larger array. The membership structure then requires O(min(N, M)) space instead of always using O(N) space.

Q5. How can the intersection of more than two sorted arrays be found?

Repeated two-pointer intersection can combine the arrays one at a time. Processing can stop immediately when any intermediate intersection becomes empty.