Leetcode - Sum of Three Values Solution

Three nested loops can find three numbers whose sum equals a target, but they take O(n³) time. A sorted array permits an O(n²) search with two pointers.

After the sort, fix one number and use two pointers to search for the other two. The comparison between the sum and the target determines which pointer moves.

Understanding the Problem

Given an array nums and a target value, determine if three numbers sum to the target. The indices must be different (i ≠ j ≠ k). The challenge is doing this efficiently without checking all possible triplets.

My First Approach

My initial solution was straightforward: check all possible triplets using three nested loops.

function hasThreeSumNaive(nums, target) {
  const n = nums.length;
  for (let i = 0; i < n - 2; i++) {
    for (let j = i + 1; j < n - 1; j++) {
      for (let k = j + 1; k < n; k++) {
        if (nums[i] + nums[j] + nums[k] === target) {
          return true;
        }
      }
    }
  }
  return false;
}

The three loops take O(n³) time. Each additional input value increases the number of triplets to check.

The Insight: Sorting + Two Pointers

The optimized approach combines two techniques:

1. Sort the array first: This enables the two pointers technique
2. Fix the first number with one loop
3. Use two pointers to find the other two numbers

Sorted order lets the search remove impossible pairs. If the sum is too small, no smaller right value can produce the target with the current left value. The left pointer advances. If the sum is too large, no larger left value can produce the target with the current right value. The right pointer moves left. Equal array values can leave the sum unchanged.

Two pointer implementation

function hasThreeSum(nums, target) {
  // Sort first - this is key!
  nums.sort((a, b) => a - b);
  const n = nums.length;

  // Fix the first number
  for (let i = 0; i < n - 2; i++) {
    let left = i + 1; // Second number starts after first
    let right = n - 1; // Third number starts at the end

    while (left < right) {
      const sum = nums[i] + nums[left] + nums[right];

      if (sum === target) {
        return true; // Found it!
      } else if (sum < target) {
        left++; // Need a larger sum, move left pointer right
      } else {
        right--; // Sum too large, move right pointer left
      }
    }
  }

  return false; // No triplet found
}

Pointer trace

For nums = [1, 2, 3, 4, 5] and target = 9, the pointers move as follows:

After sorting: [1, 2, 3, 4, 5] (already sorted in this case)

• i = 0 (fix 1), left = 1 (value 2), right = 4 (value 5): sum = 1+2+5 = 8 < 9
  • Sum is too small, move left pointer right
• i = 0 (fix 1), left = 2 (value 3), right = 4 (value 5): sum = 1+3+5 = 9 ✓ Found it!

The key is that because the array is sorted, we know:

• Moving the left pointer right cannot decrease the sum
• Moving the right pointer left cannot increase the sum
• We can eliminate many possibilities without checking them

Why Sorting Helps

Sorting enables the two pointers technique by giving us predictable behavior:

• If sum is too small: Move the left pointer right. The next value is greater than or equal to the previous value.
• If sum is too large: Move the right pointer left. The next value is less than or equal to the previous value.
• We can eliminate possibilities: If nums[i] + nums[left] + nums[right] > target, every larger right value also makes the sum too large.

Complexity Analysis

Time Complexity: O(n²)

• Sorting takes O(n log n)
• The outer loop runs n-2 times
• For each outer iteration, the inner while loop runs at most n times
• Total: O(n log n) + O(n²) = O(n²)

Space Complexity: O(1) for the pointer scan, plus sort workspace

The pointers use constant extra space. The nums.sort() call can allocate additional memory. V8 documents temporary storage in its sorting implementation. The O(1) bound applies only to the scan after sorting. The function also changes the input array's order.

Common Pitfalls

When implementing this, watch out for:

1. Forgetting to sort: The two pointers technique only works with sorted arrays
2. Off by one errors: Make sure your loop bounds are correct (i < n - 2, left < right)
3. Duplicate handling: If the problem requires unique triplets, you will need to skip duplicates
4. Integer overflow: For very large numbers, the sum might overflow

Sum search summary

• Sorting enables two pointers to reduce one dimension of nested loops
• Fix one element, then use two pointers for the remaining values
• Time complexity improves from O(n³) to O(n²), and the pattern applies to related sum problems

Sorting and two pointers are useful together when a problem asks for combinations that reach a target.