Triad sum nearest target

You are in the middle of a technical interview at Adobe. The interviewer gives you an array of integers and a target number, then asks: "Find three numbers whose sum is as close to the target as possible." Your first instinct might be to check every possible combination of three numbers, but with arrays up to 500 elements, that brute-force approach would be painfully slow. There has to be a smarter way. This problem, also known as 3Sum Closest on other platforms, is a staple at companies like Adobe, Yahoo, Meta, and Amazon. It tests whether you can combine sorting with the two-pointer technique to tame an otherwise expensive search.

TL;DR

Sort the array, then for each element fix it as the first of three, and use two pointers (one from the left, one from the right of the remaining subarray) to find the pair that brings the triplet sum closest to the target. Track the best sum seen so far by comparing absolute differences. If any triplet exactly matches the target, return immediately. This runs in O(n^2) time and O(1) space.

Why This Problem Matters

The "three sum closest" pattern builds directly on the classic two-sum and three-sum problems. If you can solve this, you already understand the core technique behind an entire family of interview questions involving sorted arrays and pointer manipulation. Companies love it because it tests three things at once: your ability to optimize from brute force, your comfort with the two-pointer pattern, and your attention to edge cases like overflow and exact matches.

Understanding the Problem

Given an integer array nums with n elements and an integer target, find three numbers in nums whose sum is closest to target. Return that sum.

Constraints:

• 3 ≤ nums.length ≤ 500
• nums[i] is in the range [-1000, 1000]
• target is in the range [-10000, 10000]
• Exactly one solution exists for each input

Here is an example:

threeSumClosest([-1, 2, 1, -4], 1) => 2
// Triplet (-1, 2, 1) has sum 2, which is closest to target 1

threeSumClosest([0, 0, 0], 1) => 0
// Only one triplet possible: (0, 0, 0) with sum 0

Edge Cases to Consider

1. All elements identical like [1, 1, 1, 1] with target 3. Only one distinct triplet sum is possible.
2. Negative elements like [-1, -1, -1, -1] with target -2. The closest sum is -3.
3. Large spread like [-1000, -1000, 1000, 1000, 0]. Sorting helps narrow the search quickly.
4. Exact match exists. If a triplet sums exactly to the target, return immediately.

From Brute Force to Optimized

The naive approach checks every possible triplet. With three nested loops, that is O(n^3). For n = 500, that is 125 million iterations. We can do much better.

If we sort the array first, we can replace the two inner loops with a single two-pointer scan. Sorting costs O(n log n), and the two-pointer pass for each fixed element costs O(n), giving us O(n^2) overall.

Why Sorting Enables Two Pointers

In a sorted array, the smallest unused values are on the left and the largest are on the right. When we fix one element and place pointers at the boundaries of the remaining subarray:

• If the current triplet sum is too small, moving the left pointer rightward increases the sum
• If the current triplet sum is too large, moving the right pointer leftward decreases the sum
• If the sum matches the target exactly, we are done

This directional certainty is what makes the two-pointer technique work. Without sorting, we would have no way to know which pointer to move.

Walkthrough with an Example

Let us trace through nums = [-1, 2, 1, -4] with target = 1.

Step 1: Sort the array.

After sorting: [-4, -1, 1, 2].

Step 2: Fix each element and run two pointers.

Here is how closestSum evolves through the iterations:

The final answer is 2, which comes from the triplet (-1, 1, 2).

Implementation

Prefer a different language? Jump to solutions in other languages.

import java.util.Arrays;

public class Solution {

  public int threeSumClosest(int[] nums, int target) {
    // Sort the array to enable the two-pointer technique
    Arrays.sort(nums);
    // Initialize closestSum with the sum of the first three elements
    int closestSum = nums[0] + nums[1] + nums[2];

    // Fix each element as the first of three
    for (int i = 0; i < nums.length - 2; i++) {
      int left = i + 1;
      int right = nums.length - 1;

      while (left < right) {
        int currentSum = nums[i] + nums[left] + nums[right];

        // Update closestSum if we found a better match
        if (Math.abs(currentSum - target) < Math.abs(closestSum - target)) {
          closestSum = currentSum;
        }

        // Decide which pointer to move
        if (currentSum < target) {
          left++;
        } else if (currentSum > target) {
          right--;
        } else {
          // Exact match, can't do better
          return currentSum;
        }
      }
    }

    return closestSum;
  }
}

Here are the key decisions behind this code.

Why initialize closestSum with nums[0] + nums[1] + nums[2]? Using Integer.MAX_VALUE would cause overflow when computing Math.abs(closestSum - target). The sum of the first three elements is always a valid triplet sum, so it is a safe starting point.

Why compare Math.abs(currentSum - target) against Math.abs(closestSum - target)? We care about the distance from the target, not the direction. A sum of -2 with target 1 (distance 3) is worse than a sum of 3 with target 1 (distance 2), even though -2 is smaller.

Why return early when currentSum == target? A difference of zero is the smallest possible. No other triplet can beat it, so returning immediately avoids unnecessary work.

Complexity Analysis

Time Complexity: O(n^2)

Sorting the array takes O(n log n). The outer loop runs n - 2 times, and for each iteration the two-pointer scan runs in O(n) time. That gives us O(n * n) = O(n^2) for the main loop. Since O(n^2) dominates O(n log n), the overall time complexity is O(n^2).

For n = 500, that is roughly 250,000 operations instead of 125 million with brute force.

Space Complexity: O(1)

The algorithm uses only a fixed number of variables: closestSum, left, right, and currentSum. No auxiliary data structures are needed. The sorting is done in-place. Some sort implementations use O(log n) stack space for recursion, but this does not depend on input size in a meaningful way.

Common Pitfalls

1. Overflow with Integer.MAX_VALUE. If you initialize closestSum to Integer.MAX_VALUE, then closestSum - target overflows. Always initialize with the actual sum of three elements.

2. Forgetting to sort. The two-pointer technique only works on sorted data. Without the Arrays.sort() call, pointer movements are meaningless.

3. Moving the wrong pointer. When currentSum is less than target, you need to increase the sum by moving the left pointer right. Moving the right pointer left would make the sum even smaller.

4. Skipping the early return. While not a correctness bug, failing to return when currentSum == target means you keep scanning unnecessarily. In interviews, mentioning this optimization shows attention to detail.

Interview Tips

When solving this problem in an interview:

1. Start with brute force. Mention that checking all C(n, 3) triplets works but runs in O(n^3). This shows you understand the problem before optimizing.

2. Explain the sorting insight. "If I sort the array first, I can fix one element and use two pointers to efficiently search for the best pair. That reduces O(n^3) to O(n^2)."

3. Trace through a small example. Use [-1, 2, 1, -4] with target 1. Walk through sorting, then show how pointers converge.

4. Watch for follow-up questions:

   • "How would you handle finding ALL triplets with the closest sum?" (Track a list instead of a single value)
   • "What if you needed the four numbers closest to target?" (Same pattern with an additional outer loop, O(n^3))
   • "How does this relate to 3Sum?" (3Sum is the special case where target = 0 and you need exact matches)

Key Takeaways

• Sorting an array enables the two-pointer technique, converting an O(n^2) pair search into O(n) per fixed element.
• Initialize closestSum with a real triplet sum (first three elements after sorting) to avoid integer overflow.
• Compare absolute differences |currentSum - target| to track which sum is closest, and return immediately when the difference hits zero.
• The "fix one, scan two" pattern applies to many problems: 3Sum, 3Sum Closest, 4Sum, and variants. It is a reusable tool for an entire category of interview questions.
• Test with identical elements, all negatives, and arrays where an exact match exists to catch subtle bugs.

Practice Makes Perfect

Once you are comfortable with this problem, try these related challenges to deepen your understanding of the sort-and-two-pointers pattern:

• Zero Sum Triplet Finder (the classic 3Sum)
• Two Sum / Find Pair Indices in Sorted Array
• Maximize Water Storage Between Lines (another two-pointer classic)

This problem and thousands of others are available on Firecode, where over 50,000 users have successfully prepared for technical interviews and landed six and seven-figure jobs at top tech companies. Whether you are just starting out or preparing for your next role at a FAANG company, consistent practice with patterns like sort-and-two-pointers will sharpen your skills for interview day.

Solutions in Other Languages

Python

class Solution:
    def three_sum_closest(self, nums, target):
        nums.sort()
        closest_sum = nums[0] + nums[1] + nums[2]

        for i in range(len(nums) - 2):
            left, right = i + 1, len(nums) - 1
            while left < right:
                current_sum = nums[i] + nums[left] + nums[right]
                if abs(current_sum - target) < abs(closest_sum - target):
                    closest_sum = current_sum

                if current_sum < target:
                    left += 1
                elif current_sum > target:
                    right -= 1
                else:
                    return current_sum

        return closest_sum

JavaScript

class Solution {
  threeSumClosest(nums, target) {
    nums.sort((a, b) => a - b);
    let closestSum = nums[0] + nums[1] + nums[2];

    for (let i = 0; i < nums.length - 2; i++) {
      let left = i + 1;
      let right = nums.length - 1;

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

        if (Math.abs(currentSum - target) < Math.abs(closestSum - target)) {
          closestSum = currentSum;
        }

        if (currentSum < target) {
          left++;
        } else if (currentSum > target) {
          right--;
        } else {
          return currentSum;
        }
      }
    }

    return closestSum;
  }
}

TypeScript

class Solution {
  threeSumClosest(nums: number[], target: number): number {
    nums.sort((a, b) => a - b);
    let closestSum = nums[0] + nums[1] + nums[2];

    for (let i = 0; i < nums.length - 2; i++) {
      let left = i + 1;
      let right = nums.length - 1;

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

        if (Math.abs(currentSum - target) < Math.abs(closestSum - target)) {
          closestSum = currentSum;
        }

        if (currentSum < target) {
          left++;
        } else if (currentSum > target) {
          right--;
        } else {
          return currentSum;
        }
      }
    }

    return closestSum;
  }
}

C++

#include <vector>
#include <algorithm>

class Solution {
public:
    int threeSumClosest(std::vector<int> &nums, int target) {
        std::sort(nums.begin(), nums.end());
        int closestSum = nums[0] + nums[1] + nums[2];

        for (size_t i = 0; i < nums.size() - 2; ++i) {
            size_t left = i + 1;
            size_t right = nums.size() - 1;

            while (left < right) {
                int currentSum = nums[i] + nums[left] + nums[right];

                if (std::abs(currentSum - target) < std::abs(closestSum - target)) {
                    closestSum = currentSum;
                }

                if (currentSum < target) {
                    ++left;
                } else if (currentSum > target) {
                    --right;
                } else {
                    return currentSum;
                }
            }
        }

        return closestSum;
    }
};

Go

import "sort"

func threeSumClosest(nums []int, target int) int {
    sort.Ints(nums)
    closestSum := nums[0] + nums[1] + nums[2]

    for i := 0; i < len(nums)-2; i++ {
        left, right := i+1, len(nums)-1
        for left < right {
            currentSum := nums[i] + nums[left] + nums[right]
            if abs(target-currentSum) < abs(target-closestSum) {
                closestSum = currentSum
            }
            if currentSum < target {
                left++
            } else if currentSum > target {
                right--
            } else {
                return currentSum
            }
        }
    }

    return closestSum
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

Scala

class Solution {
  def threeSumClosest(nums: Array[Int], target: Int): Int = {
    val sortedNums = nums.sorted
    var closestSum = sortedNums(0) + sortedNums(1) + sortedNums(2)

    for (i <- 0 until sortedNums.length - 2) {
      var left = i + 1
      var right = sortedNums.length - 1

      while (left < right) {
        val currentSum = sortedNums(i) + sortedNums(left) + sortedNums(right)
        if (math.abs(currentSum - target) < math.abs(closestSum - target)) {
          closestSum = currentSum
        }

        if (currentSum < target) {
          left += 1
        } else if (currentSum > target) {
          right -= 1
        } else {
          return currentSum
        }
      }
    }

    closestSum
  }
}

Kotlin

class Solution {
  fun threeSumClosest(nums: IntArray, target: Int): Int {
    nums.sort()
    var closestSum = nums[0] + nums[1] + nums[2]

    for (i in 0 until nums.size - 2) {
      var left = i + 1
      var right = nums.lastIndex
      while (left < right) {
        val currentSum = nums[i] + nums[left] + nums[right]
        if (kotlin.math.abs(currentSum - target) < kotlin.math.abs(closestSum - target)) {
          closestSum = currentSum
        }
        if (currentSum < target) {
          left++
        } else if (currentSum > target) {
          right--
        } else {
          return currentSum
        }
      }
    }

    return closestSum
  }
}

Swift

class Solution {
    func threeSumClosest(_ nums: [Int], _ target: Int) -> Int {
        var nums = nums.sorted()
        var closestSum = nums[0] + nums[1] + nums[2]

        for i in 0..<nums.count - 2 {
            var left = i + 1
            var right = nums.count - 1
            while left < right {
                let currentSum = nums[i] + nums[left] + nums[right]
                if abs(currentSum - target) < abs(closestSum - target) {
                    closestSum = currentSum
                }
                if currentSum < target {
                    left += 1
                } else if currentSum > target {
                    right -= 1
                } else {
                    return currentSum
                }
            }
        }

        return closestSum
    }
}

Rust

impl Solution {
    pub fn three_sum_closest(&self, mut nums: Vec<i32>, target: i32) -> i32 {
        nums.sort();
        let mut closest_sum = nums[0] + nums[1] + nums[2];

        for i in 0..nums.len() - 2 {
            let mut left = i + 1;
            let mut right = nums.len() - 1;
            while left < right {
                let current_sum = nums[i] + nums[left] + nums[right];
                if (current_sum - target).abs() < (closest_sum - target).abs() {
                    closest_sum = current_sum;
                }
                if current_sum < target {
                    left += 1;
                } else if current_sum > target {
                    right -= 1;
                } else {
                    return current_sum;
                }
            }
        }

        closest_sum
    }
}

Ruby

class Solution
  def three_sum_closest(nums, target)
    nums.sort!
    closest_sum = nums[0] + nums[1] + nums[2]

    (0...nums.length - 2).each do |i|
      left = i + 1
      right = nums.length - 1
      while left < right
        current_sum = nums[i] + nums[left] + nums[right]
        if (current_sum - target).abs < (closest_sum - target).abs
          closest_sum = current_sum
        end
        if current_sum < target
          left += 1
        elsif current_sum > target
          right -= 1
        else
          return current_sum
        end
      end
    end

    closest_sum
  end
end

Dart

class Solution {
  int threeSumClosest(List<int> nums, int target) {
    nums.sort();
    int closestSum = nums[0] + nums[1] + nums[2];

    for (int i = 0; i < nums.length - 2; i++) {
      int left = i + 1;
      int right = nums.length - 1;
      while (left < right) {
        int currentSum = nums[i] + nums[left] + nums[right];
        if ((currentSum - target).abs() < (closestSum - target).abs()) {
          closestSum = currentSum;
        }
        if (currentSum < target) {
          left++;
        } else if (currentSum > target) {
          right--;
        } else {
          return currentSum;
        }
      }
    }

    return closestSum;
  }
}

PHP

class Solution {
    public function threeSumClosest(array $nums, int $target): int {
        sort($nums);
        $closestSum = $nums[0] + $nums[1] + $nums[2];

        for ($i = 0; $i < count($nums) - 2; $i++) {
            $left = $i + 1;
            $right = count($nums) - 1;

            while ($left < $right) {
                $currentSum = $nums[$i] + $nums[$left] + $nums[$right];

                if (abs($currentSum - $target) < abs($closestSum - $target)) {
                    $closestSum = $currentSum;
                }

                if ($currentSum < $target) {
                    $left++;
                } elseif ($currentSum > $target) {
                    $right--;
                } else {
                    return $currentSum;
                }
            }
        }

        return $closestSum;
    }
}

C#

using System;

public class Solution {
    public int ThreeSumClosest(int[] nums, int target) {
        Array.Sort(nums);
        int closestSum = nums[0] + nums[1] + nums[2];

        for (int i = 0; i < nums.Length - 2; i++) {
            int left = i + 1;
            int right = nums.Length - 1;
            while (left < right) {
                int currentSum = nums[i] + nums[left] + nums[right];
                if (Math.Abs(currentSum - target) < Math.Abs(closestSum - target)) {
                    closestSum = currentSum;
                }
                if (currentSum < target) {
                    left++;
                } else if (currentSum > target) {
                    right--;
                } else {
                    return currentSum;
                }
            }
        }

        return closestSum;
    }
}