Triplet Sum Close to Target in O(N²) Time

Felix Lee
1 min readJul 24, 2022

--

https://quotesgram.com/img/funny-triplet-quotes/7074867/

Problem Statement

Given an integer array nums of length n and an integer target, find three integers in nums such that the sum is closest to target.

Return the sum of the three integers.

Key Ideas

  1. Use 3 pointers to point to the current element, next(left) element, and the last(right) element.
  2. Sum the 3 elements.
  3. If the difference between the current sum and target is smaller than the difference between our result and the target, set our result to the current sum.
  4. If current sum is larger than target, move the last(right) index to the left to get a smaller sum. (Remember target — sum = difference , so if larger sum = larger difference)
  5. Otherwise, move the next(left) index to the right to get a larger sum.

Time and Space Complexity

Time Complexity

We sort the array initially, so it’s O(N * log(N)). We have a loop nested inside a loop so it is O(N²). Overall the function takes O(N * log(N) + N²) which is asymptotically equivalent to O(N²).

Space Complexity

We sort the array at the beginning, the sorting takes O(N) space.

--

--

Felix Lee
Felix Lee

Written by Felix Lee

Software engineer in Singapore. Write random tech stuff. Still figuring out this “life” thing in life.