This post is completed by 2 users

  • 1
Add to List

459. Given an array, find three-element sum closest to Zero

Objective: Given an array of integers, find the sum of any three elements which is closest to zero. The array may contain positive and negative elements. 


Given Input: [-1, 4, -2, 5, 10, -5]
Minimum Sum with three elements is: 1
Explanation:  -1, 4, -2 sums to -1 

Given Input: [-1, 4, -2, 5, 10, -5, 1]
Minimum Sum with three elements is: 0
Explanation:  1, 4, -5 sums to 0


Brute force: Check all the sets with three elements. Use three nested loops, first two loops will fix the two elements in an array and iterate the rest of the array using the third loop and check the sum. Keep track of a minimum positive-sum which is close to zero and the minimum negative-sum which is close to zero. If any point sum becomes zero return 0 (since its best we can get). 

Time Complexity: (N3)

Better Solution:

  1. Sort the given array in ascending order.
  2. Initialize sum = 0, positiveClose = INTEGER_MAXIMUM, negativeClose = INTEGER_MINIMUM.  
  3. Use two loops. 
  4. Fix the element using the outer loop. Call it first 
    1. sum = first element. 
    2. Inside the inner loop, take two pointers, second and third. second at the next element to the first element and third at the last element in the array. Do sum = sum +second+third. 
    3. Now if sum = 0, return 0. 
    4. Else if sum > 0 , do positiveClose = minimum(positiveClose, sum)
    5. Else do negativeClose = maximum(negativeClose, sum)
  5. If abs(negativeClose)<positiveClose return negativeClose else return positiveClose.

Time Complexity: O(N2)


Given Input: [-1, 4, -2, 5, 10, -5]
Minimum Sum with three elements is: 1