Two Sum

The Problem

Given an integer array arr and a target integer, find two distinct elements in the array whose sum equals the target. Return them as a pair. If no such pair exists, return an empty array.

It is guaranteed that at most one answer exists.

Input:  arr = [2, 8, 3, 6, 4],  target = 7
Output: [3, 4]

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

Examples

Example 1

Input:  arr = [2, 8, 3, 6, 4],  target = 7
Output: [3, 4]
Explanation: 3 + 4 = 7

Example 2

Input:  arr = [2, -1, 5, -4, 3],  target = 34
Output: []
Explanation: No pair sums to 34.

Example 3

Input:  arr = [2],  target = 2
Output: []
Explanation: Only one element — can't form a pair.

Intuition

The brute-force approach checks every pair: O(n²). The reduction insight is:

Order doesn’t matter → we can sort. Sorted array → two-pointer works.

After sorting, the array has a useful property: arr[left] is the smallest remaining element and arr[right] is the largest. Their sum gives us directional information:

• Sum too small? Only increasing left can raise the sum.
• Sum too large? Only decreasing right can lower the sum.
• Sum exact? Found it.

---
config:
  theme: base
  themeVariables:
    primaryColor: "#dbeafe"
    primaryBorderColor: "#3b82f6"
    primaryTextColor: "#1e3a5f"
    lineColor: "#64748b"
    secondaryColor: "#ede9fe"
    tertiaryColor: "#fef9c3"
---
flowchart TB
  Sort["Sort arr → [2, 3, 4, 6, 8]"]
  Init["left = 0,  right = 4"]
  Loop{"left < right?"}
  Calc["sum = arr[left] + arr[right]"]
  Eq{"sum == target?"}
  Lt{"sum < target?"}
  RetOK(["return [arr[left], arr[right]]"])
  MoveL["left++  (need larger sum)"]
  MoveR["right--  (need smaller sum)"]
  RetNone(["return []"])

  Sort --> Init --> Loop
  Loop -->|"yes"| Calc --> Eq
  Eq -->|"yes"| RetOK
  Eq -->|"no"| Lt
  Lt -->|"yes"| MoveL --> Loop
  Lt -->|"no"| MoveR --> Loop
  Loop -->|"no"| RetNone

Two-pointer Two Sum — sort once, then converge from both ends in O(n).

Applying the Diagnostic Questions

Q1 — Why “order doesn’t matter, so sorting is permitted”?

Mental model: The output is a pair of values — [3, 4] — not a pair of indices. The problem says nothing about the positions those values came from. A pair (3, 4) summing to 7 is valid whether 3 appeared before or after 4 in the original array. When the answer depends only on values, sorting cannot invalidate a correct answer — and it gives us a structure we can exploit.

Concrete impact: arr = [2, 8, 3, 6, 4], target = 7. Unsorted, the pair (3, 4) sits at non-adjacent indices 2 and 4 — invisible without checking every combination. After sorting to [2, 3, 4, 6, 8], 3 and 4 are adjacent and the min/max structure guides the search directly.

What breaks if position mattered? If the problem asked “find a pair at consecutive positions” or “the second element must appear after the first in the original array,” sorting would destroy the positional information needed. Here there is no such constraint — position-independence is the prerequisite for the sorting reduction.

Q3 — Why “both ends give decisive direction after sorting”?

Mental model: After sorting, arr[left] is the minimum of the unexamined window and arr[right] is the maximum. This gives every pointer move a guaranteed effect: moving left right replaces the minimum with a larger value — the sum strictly increases. Moving right left replaces the maximum with a smaller value — the sum strictly decreases. That decisive direction is what eliminates one element per step with a provable reason.

Concrete trace: sorted [2, 3, 4, 6, 8], target = 7:

• left=0 (2), right=4 (8): sum 10 > 7 → arr[right]=8 is too large for any remaining left partner (min is 2, so best sum with 8 is already 10) → discard arr[right], right--
• left=0 (2), right=3 (6): sum 8 > 7 → same reasoning → right--
• left=0 (2), right=2 (4): sum 6 < 7 → arr[left]=2 can never reach target with any remaining right partner (max is 4, best sum 6 < 7) → discard arr[left], left++
• left=1 (3), right=2 (4): sum 7 == target ✓

What breaks on an unsorted array? Without sorting, moving left right might land on a smaller value — the sum could decrease instead of increase. The decisive direction disappears, and you’d need to try every combination: O(n²).

Solution

from typing import List

class Solution:
    def two_sum(self, arr: List[int], target: int) -> List[int]:
        # Sort the array to enable the two-pointer reduction
        arr.sort()

        # Initialize left pointer at the smallest element
        left  = 0
        # Initialize right pointer at the largest element
        right = len(arr) - 1

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

            if current == target:
                return [arr[left], arr[right]]
            elif current < 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

        # Pointers crossed — no valid pair exists
        return []


# --- Test ---
sol = Solution()
print(sol.two_sum([2, 8, 3, 6, 4], 7))         # [3, 4]
print(sol.two_sum([2, -1, 5, -4, 3], 34))       # []
print(sol.two_sum([2], 2))                       # []
print(sol.two_sum([-3, -1, 0, 2, 4, 6], 3))     # [-3, 6] or [1, 2] — sorted pick

Dry Run — Example 1

arr = [2, 8, 3, 6, 4], target = 7

After sort: [2, 3, 4, 6, 8]

Complexity Analysis

If the array were already sorted, the solution would be O(n) time and O(1) space — the sort is the only overhead.

Edge Cases

Key Takeaway

Two Sum is the canonical two-pointer reduction problem. The reduction step — sort so that the array becomes directionally meaningful — is the key insight. Once sorted, the two-pointer pass eliminates one element per step with a guaranteed correct reason, giving O(n log n) total instead of O(n²).