Three Number Sum

Tags

Three Number Sum

Category

Arrays

Difficulty

Medium

Problem Statement

Given a non-empty array of distinct integers and a target sum, find all unique triplets in the array that sum to the target. Return the triplets sorted, both within each triplet and across the list of triplets.

Intuition

Sorting the array first enables a two-pointer technique. For each element, the problem reduces to a two-number-sum on the remaining elements to the right. By fixing one element and using two pointers (one at the start and one at the end of the remaining subarray), we efficiently find all pairs that complete the triplet.

Approach

  1. Sort the array in ascending order.
  2. Initialize an empty list to hold the result triplets.
  3. For each index i from 0 to length - 3:
    • Set left = i + 1 and right = length - 1.
    • While left < right:
      • Compute currentSum = array[i] + array[left] + array[right].
      • If currentSum == target, add the triplet, then move both pointers inward.
      • If currentSum < target, move left right to increase the sum.
      • If currentSum > target, move right left to decrease the sum.
  4. Return the list of triplets.

Pseudocode

function threeNumberSum(array, targetSum):
    sort(array)
    triplets = []
    for i from 0 to length(array) - 3:
        left = i + 1
        right = length(array) - 1
        while left < right:
            currentSum = array[i] + array[left] + array[right]
            if currentSum == targetSum:
                triplets.append([array[i], array[left], array[right]])
                left += 1
                right -= 1
            else if currentSum < targetSum:
                left += 1
            else:
                right -= 1
    return triplets

Time & Space Complexity

  • Time: O(n^2) — Sorting is O(n log n), and for each of the n elements, the two-pointer scan is O(n), giving O(n^2) overall.
  • Space: O(n) — For the output list (not counting it, the algorithm itself uses O(1) extra space beyond the sort).

Key Insights

  • Sorting is the critical enabler for the two-pointer technique.
  • Distinct integers mean no need to handle duplicate skipping (unlike the classic LeetCode 3Sum).
  • Moving both pointers after finding a match is correct because the array has distinct values, so neither pointer alone could form another valid triplet with the fixed element.

Edge Cases

  • Array has fewer than three elements — no triplets possible.
  • No triplets sum to the target — return an empty list.
  • Multiple valid triplets — all are captured by the two-pointer sweep.
  • All negative or all positive numbers — the algorithm works regardless of sign.

Linked mentions