Leetcode - Sum of Three Values Solution

Finding three numbers that sum to a target value sounds like it needs three nested loops. But there's a much better approach: sort the array first, then use two pointers. This combination of sorting and two pointers transforms an O(n³) brute force solution into an elegant O(n²) algorithm.

The key insight is that sorting enables us to use the two pointers technique. Once the array is sorted, we can fix one number and use two pointers to find the other two, moving them based on whether the sum is too small or too large.

Understanding the Problem

Given an array nums and a target value, determine if there are three numbers that 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;
}

This works, but it's O(n³) time complexity. For large arrays, this becomes prohibitively slow. I knew there had to be a better way.

The Insight: Sorting + Two Pointers

The breakthrough came when I realized I could combine 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

The two pointers technique works because when the array is sorted, we can intelligently move the pointers based on whether the sum is too small or too large. If the sum is too small, we move the left pointer right (increasing the sum). If the sum is too large, we move the right pointer left (decreasing the sum).

The Solution

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
}

How It Works

Let me trace through an example with nums = [1, 2, 3, 4, 5] and target = 9:

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 left right increases the sum
• Moving right left decreases 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: Moving the left pointer right increases it (because values are larger)
• If sum is too large: Moving the right pointer left decreases it (because values are smaller)
• We can eliminate possibilities: If nums[i] + nums[left] + nums[right] > target, we know that nums[i] + nums[left] + nums[k] > target for all k > right, so we can skip checking those

Complexity Analysis

Time Complexity: O(n²)

• Sorting takes O(n log n)
• The outer loop runs n-2 times
• The inner while loop runs at most n times in total across all iterations
• Total: O(n log n) + O(n²) = O(n²)

Space Complexity: O(1)

• Only using a few variables for pointers
• Sorting can be done in-place (though JavaScript's sort may use extra space)

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'll need to skip duplicates
4. Integer overflow: For very large numbers, the sum might overflow

Key Takeaways

• Sorting + two pointers is a powerful combination for finding pairs or triplets
• Two pointers reduces one dimension of nested loops
• The pattern: fix one element, use two pointers for the rest
• Time complexity improves from O(n³) to O(n²)
• This pattern appears in many problems involving finding combinations that sum to a target

The combination of sorting and two pointers is one of my favorite techniques. It turns what seems like a complex problem into an elegant solution. Once you see the pattern, you'll recognize opportunities to use it in many similar problems.