Unique Intersections

The Problem

Given two integer arrays arr1 and arr2, return an array containing all elements that appear in both arrays. Each element in the result must appear only once, regardless of how many times it appears in the inputs.

arr1 = [1, 2, 2, 3, 4],  arr2 = [2, 2, 3, 5]  →  [2, 3]
arr1 = [1, 2, 3],         arr2 = [4, 5, 6]      →  []
arr1 = [1, 1, 1],         arr2 = [1, 1]          →  [1]
arr1 = [1, 2, 3, 4, 5],   arr2 = [1, 3, 5, 7]   →  [1, 3, 5]

Examples

Example 1

Input:  arr1 = [1, 2, 2, 3, 4],  arr2 = [2, 2, 3, 5]
Output: [2, 3]
Explanation: 2 and 3 appear in both arrays. Even though 2 appears twice in both,
             it appears only once in the result.

Example 2

Input:  arr1 = [1, 3, 5],  arr2 = [2, 4, 6]
Output: []
Explanation: No value appears in both arrays.

Example 3

Input:  arr1 = [2, 2, 2],  arr2 = [2, 2]
Output: [2]
Explanation: 2 is common, but unique intersections means it appears once.

Intuition

The brute force way is to check every element of arr1 against every element of arr2 — that’s O(N × M). But if both arrays are sorted, you can do something much smarter: walk both simultaneously.

Think of it like merging, but instead of taking elements from either side, you’re looking for moments where both sides match. When arr1[i] == arr2[j], you’ve found a common element — record it and advance both pointers. When arr1[i] < arr2[j], the element in arr1 is too small to find a match on the right, so skip it. When arr1[i] > arr2[j], the element in arr2 is too small — skip it.

The uniqueness constraint adds one extra rule: after recording a match, if the next elements on either side are duplicates of what you just recorded, skip them. You only ever record a value the first time you encounter it.

---
config:
  theme: base
  themeVariables:
    primaryColor: "#dbeafe"
    primaryBorderColor: "#3b82f6"
    primaryTextColor: "#1e3a5f"
    lineColor: "#64748b"
    secondaryColor: "#ede9fe"
    tertiaryColor: "#fef9c3"
---
flowchart TB
  Sort["Sort arr1 and arr2"]
  Init(["i = 0, j = 0, result = []"])
  Check{"i < len(arr1)<br/>AND j < len(arr2)?"}
  Cmp{"arr1[i] vs arr2[j]"}
  Match["Record arr1[i] if not duplicate<br/>i += 1,  j += 1"]
  AdvI["i += 1<br/>(arr1[i] too small)"]
  AdvJ["j += 1<br/>(arr2[j] too small)"]
  Done(["return result"])

  Sort --> Init --> Check
  Check -->|"yes"| Cmp
  Cmp -->|"equal"| Match --> Check
  Cmp -->|"arr1[i] < arr2[j]"| AdvI --> Check
  Cmp -->|"arr1[i] > arr2[j]"| AdvJ --> Check
  Check -->|"no"| Done

Unique Intersections — sort both, then walk with two pointers. On a match, record only if the value is new. On a mismatch, advance the smaller pointer.

Brute Force: Nested Loops, O(N × M)

from typing import List

def unique_intersections_brute(arr1: List[int], arr2: List[int]) -> List[int]:
    # Use a set to avoid recording duplicates in the result
    seen = set()
    result = []

    # For every element in arr1, scan all of arr2 for a match
    for x in arr1:
        for y in arr2:
            if x == y and x not in seen:
                result.append(x)
                seen.add(x)
                break  # No need to keep scanning arr2 for this x

    return result

print(unique_intersections_brute([1, 2, 2, 3, 4], [2, 2, 3, 5]))  # [2, 3]

Works, but rescans arr2 for every element in arr1 — O(N × M) and easy to get wrong with the duplicate-tracking logic.

Solution

from typing import List

class Solution:
    def unique_intersections(self, arr1: List[int], arr2: List[int]) -> List[int]:
        # Sort both arrays to enable simultaneous traversal
        arr1.sort()
        arr2.sort()

        result = []
        # Initialize pointers at the start of each array
        i = 0
        j = 0

        # Main loop: run while both arrays have unprocessed elements
        while i < len(arr1) and j < len(arr2):
            if arr1[i] == arr2[j]:
                # Common element found — record only if it is not a duplicate of the last result entry
                if not result or result[-1] != arr1[i]:
                    result.append(arr1[i])
                # Advance both pointers past this match
                i += 1
                j += 1
            elif arr1[i] < arr2[j]:
                # arr1's element is smaller — it can't match anything in arr2 at or before j
                i += 1
            else:
                # arr2's element is smaller — it can't match anything in arr1 at or before i
                j += 1

        return result


sol = Solution()
print(sol.unique_intersections([1, 2, 2, 3, 4], [2, 2, 3, 5]))    # [2, 3]
print(sol.unique_intersections([1, 3, 5], [2, 4, 6]))              # []
print(sol.unique_intersections([2, 2, 2], [2, 2]))                 # [2]
print(sol.unique_intersections([1, 2, 3, 4, 5], [1, 3, 5, 7]))    # [1, 3, 5]
print(sol.unique_intersections([], [1, 2, 3]))                     # []

Dry Run — Example 1

arr1 = [1, 2, 2, 3, 4], arr2 = [2, 2, 3, 5] (both already sorted)

i=0, j=0, result=[]

Step 1 │ arr1[0]=1, arr2[0]=2 │ 1 < 2 → advance i          │ i=1, j=0
Step 2 │ arr1[1]=2, arr2[0]=2 │ 2 == 2 → result empty → record 2 → i=2, j=1  │ result=[2]
Step 3 │ arr1[2]=2, arr2[1]=2 │ 2 == 2 → result[-1]==2 → skip (duplicate)    │ i=3, j=2
Step 4 │ arr1[3]=3, arr2[2]=3 │ 3 == 3 → result[-1]=2 ≠ 3 → record 3 → i=4, j=3  │ result=[2,3]
Step 5 │ arr1[4]=4, arr2[3]=5 │ 4 < 5 → advance i          │ i=5, j=3

i=5 == len(arr1)=5 → loop exits

Result: [2, 3] ✓

Note: step 3 found a second (2,2) match but the duplicate check suppressed it.
The sorted order of both arrays means once a match is recorded, all subsequent
duplicates of that value appear consecutively and are caught immediately.

Why Sort First?

Without sorting, you can’t use the directional “advance the smaller” rule — you don’t know which pointer to move when there’s no match. The sort gives you the guarantee that:

• If arr1[i] < arr2[j], no element of arr2 at positions 0..j-1 equals arr1[i] (already passed), and no element at positions j..end is smaller than arr2[j] (sorted). So arr1[i] can never match — safely skip it.
• The symmetric argument applies for arr1[i] > arr2[j].

After sorting, the advance condition is always decisive. Without sorting, you’d need an inner scan — and that’s O(N × M) again.

Complexity Analysis

If both arrays arrive pre-sorted, the time is O(N + M).

Edge Cases

Key Takeaway

Unique Intersections = merge pattern + match-only recording + duplicate suppression. Sort both arrays once, then use a single simultaneous pass. The result[-1] != arr1[i] guard is the whole difference between this problem and Repeated Intersections — one line is all it takes to enforce uniqueness when the array is sorted.