Duplicate Aware Two Sum

The Problem

Given an integer array arr and a target, find all unique pairs of elements whose sum equals the target. Return every pair exactly once — no duplicates in the result.

Input:  arr = [1, 2, 2, 3, 4, 5],  target = 6
Output: [[1, 5], [2, 4]]

This differs from basic Two Sum in two ways:

1. Multiple pairs may exist (not just one)
2. Duplicate values in the input must not produce duplicate pairs in the output

Examples

Example 1

Input:  arr = [1, 2, 2, 3, 4, 5],  target = 6
Output: [[1, 5], [2, 4]]
Explanation: 1+5=6, 2+4=6. Note: even though there are two 2s, the pair [2,4] appears only once.

Example 2

Input:  arr = [1, 2, 2, 2, 2],  target = 3
Output: [[1, 2]]
Explanation: Only 1+2=3 is valid. Multiple 2s don't produce multiple [1,2] pairs.

Example 3

Input:  arr = [2],  target = 2
Output: []
Explanation: Can't form a pair from one element.

Intuition

Start with the standard Two Sum approach — sort, then two-pointer. The problem becomes: what happens when we find a valid pair and there are duplicates near left or right?

Without duplicate handling:

• arr = [1, 2, 2, 3, 4, 5], target=6
• When left=1 (value 2) and right=4 (value 4) match: record [2, 4]
• Increment left → left=2, still value 2. Decrement right → right=3, still value 4
• Record [2, 4] again! ❌ Duplicate in result.

The fix: after recording a match, skip all consecutive duplicates on both sides before moving the pointers. This ensures each unique value is only used once as a pair anchor.

---
config:
  theme: base
  themeVariables:
    primaryColor: "#dbeafe"
    primaryBorderColor: "#3b82f6"
    primaryTextColor: "#1e3a5f"
    lineColor: "#64748b"
    secondaryColor: "#ede9fe"
    tertiaryColor: "#fef9c3"
---
flowchart TB
  Sort["Sort arr → [1, 2, 2, 3, 4, 5]"]
  Init["left=0, right=5, result=[]"]
  Loop{"left < right?"}
  Calc["total = arr[left] + arr[right]"]
  Match{"total == target?"}
  Record["result.append([arr[left], arr[right]])"]
  SkipL["skip left duplicates\n(while arr[left]==arr[left+1]: left++)"]
  SkipR["skip right duplicates\n(while arr[right]==arr[right-1]: right--)"]
  Move["left++,  right--"]
  Less["left++  (increase sum)"]
  Greater["right--  (decrease sum)"]
  Done(["return result"])

  Sort --> Init --> Loop
  Loop -->|"yes"| Calc --> Match
  Match -->|"yes"| Record --> SkipL --> SkipR --> Move --> Loop
  Match -->|"no, total < target"| Less --> Loop
  Match -->|"no, total > target"| Greater --> Loop
  Loop -->|"no"| Done

Duplicate Aware Two Sum — after each match, exhaust all consecutive duplicates on both sides before advancing the pointers.

Applying the Diagnostic Questions

Q1 — Why “order doesn’t matter, and sorting additionally enables deduplication”?

Mental model: The output pairs are value-pairs — [[1, 5], [2, 4]] — not index-pairs. A pair [2, 4] is valid regardless of where the 2s and 4s sat in the original array. Since the answer depends only on values, sorting cannot invalidate any correct pair.

What sorting additionally enables: duplicate detection. After sorting, all copies of the same value are adjacent. When you want to skip duplicate instances of a matched value (to avoid recording the same pair twice), a sorted array makes this trivial: scan forward or backward until the value changes. On an unsorted array, duplicates could be scattered anywhere — deduplication would require a hash set O(n) extra space per match instead of a simple in-place scan.

Concrete impact: arr = [1, 2, 2, 3, 4, 5]. After sorting, the two 2s at indices 1 and 2 are adjacent. When left=1 matches at target 6, skipping forward while arr[left] == arr[left+1] exhausts both 2s in one scan. Without sorting, the second 2 might be at index 5 — you’d need a hash set to know you’d already seen a 2 as a left anchor.

Q3 — Why “both ends give decisive direction, with duplicate-skip added after each match”?

Mental model: The decisive-direction argument from Two Sum applies unchanged: after sorting, arr[left] is the current minimum, arr[right] the current maximum. sum < target → only left++ can increase the sum. sum > target → only right-- can decrease it. When sum == target, both the current left value and right value form a valid pair — record it, then eliminate all copies of both values before continuing.

Why must you skip duplicates before continuing? After recording [arr[left], arr[right]], the very next step moves to arr[left+1] and arr[right-1]. If arr[left+1] == arr[left], you’ve found the same pair value again — the result would contain a duplicate. The skip burns through all consecutive copies so the next unique value pair is what gets evaluated next.

Concrete trace: arr = [1, 2, 2, 3, 4, 5], target = 6. At left=1 (2), right=4 (4): match, record [2, 4]. Skip left: arr[1]==arr[2] (both 2) → left++ → left=2; arr[2]!=arr[3] → stop; return left+1 = 3. Skip right: arr[4]!=arr[3] → no skip; return right-1 = 3. Now left=3, right=3: left >= right → done. Exactly one [2, 4] recorded.

What breaks if you skip the duplicate-skip step? For arr = [2, 2, 2, 2], target = 4: without skipping, every (left, right) pair where both values are 2 produces [2, 2] — that’s 4 × 4 = 16 recordings for a single unique pair. The skip step enforces “each unique value combination appears exactly once in the output.”

Solution

from typing import List

class Solution:

    def skip_duplicates_left(self, arr: List[int], left: int, right: int) -> int:
        # Skip all consecutive equal values from the left side
        while left < right and arr[left] == arr[left + 1]:
            left += 1
        # Return the index one step past the last duplicate
        return left + 1

    def skip_duplicates_right(self, arr: List[int], left: int, right: int) -> int:
        # Skip all consecutive equal values from the right side
        while left < right and arr[right] == arr[right - 1]:
            right -= 1
        # Return the index one step past the last duplicate
        return right - 1

    def duplicate_aware_two_sum(
        self, arr: List[int], target: int
    ) -> List[List[int]]:
        # Sort the array to enable the two-pointer reduction
        arr.sort()
        result = []
        left   = 0
        right  = len(arr) - 1

        # Run while there are unseen pairs remaining
        while left < right:
            total = arr[left] + arr[right]

            if total == target:
                result.append([arr[left], arr[right]])
                # Skip past consecutive duplicates on both sides before moving inward
                left  = self.skip_duplicates_left(arr, left, right)
                right = self.skip_duplicates_right(arr, left, right)

            elif total < target:
                # Sum too small — move left pointer to a larger value
                left += 1
            else:
                # Sum too large — move right pointer to a smaller value
                right -= 1

        return result


# --- Test ---
sol = Solution()
print(sol.duplicate_aware_two_sum([1, 2, 2, 3, 4, 5], 6))   # [[1,5],[2,4]]
print(sol.duplicate_aware_two_sum([1, 2, 2, 2, 2], 3))       # [[1,2]]
print(sol.duplicate_aware_two_sum([2], 2))                    # []
print(sol.duplicate_aware_two_sum([3, 3, 3], 6))              # [[3,3]]

Dry Run — Example 1

arr = [1, 2, 2, 3, 4, 5], target = 6

After sort: [1, 2, 2, 3, 4, 5]

Return [[1, 5], [2, 4]] ✓

What skip_duplicates_left does at step 2 (left=1, right=4):

• arr[1] == arr[2] (both 2) → left++ → left=2
• arr[2] != arr[3] → stop, return left + 1 = 3

So left jumps to 3, skipping both the 2s. The pair [2,4] appears exactly once.

Complexity Analysis

Edge Cases

Key Takeaway

Duplicate Aware Two Sum extends Two Sum with a single post-match clean-up step: skip all consecutive duplicates on both sides before continuing. This O(n) skip is what prevents the result from containing repeated pairs. The pattern — do the work, then skip duplicates, then advance — recurs in Three Sum and Four Sum.