13

Given an array of numbers, find out if 3 of them add up to 0.

Do it in N^2, how would one do this?

4
  • 5
    Just as a pointer, the general form of this problem is called "subset sum" if you want to look up more info about it. The general form is NP-complete, but it's tractable if you restrict the subsets you're looking at to some fixed size (in this case 3). Aug 16, 2009 at 1:00
  • Does the array contain negative numbers, or only positive numbers? Does it contain zeros?
    – Alex
    Aug 16, 2009 at 19:17
  • 2
    This is a well known problem in CS: en.wikipedia.org/wiki/3SUM
    – user361676
    Sep 9, 2012 at 12:56
  • Finding three elements in an array whose sum is closest to a given number is a more general version of this question, but the answer is the same. Nov 5, 2017 at 16:59

7 Answers 7

40

O(n^2) solution without hash tables (because using hash tables is cheating :P). Here's the pseudocode:

Sort the array // O(nlogn)

for each i from 1 to len(array) - 1
  iter = i + 1
  rev_iter = len(array) - 1
  while iter < rev_iter
    tmp = array[iter] + array[rev_iter] + array[i]
    if  tmp > 0
       rev_iter--
    else if tmp < 0
       iter++
    else 
      return true
return false

Basically using a sorted array, for each number (target) in an array, you use two pointers, one starting from the front and one starting from the back of the array, check if the sum of the elements pointed to by the pointers is >, < or == to the target, and advance the pointers accordingly or return true if the target is found.

9
  • len(n) is the length of the array :)
    – Charles Ma
    Aug 16, 2009 at 23:08
  • hey charles, i have 1 more question. In your code, isn't it possible for the target to be the same as the array[inter] or array[reviter]? So then you are adding the same number twice?
    – ryan
    Aug 16, 2009 at 23:17
  • @Ryan: The pseudocode (err, python) I wrote below based on this addresses exactly that: it stops when lower increments to target's index or upper decrements to that point. See the "while lower < i < upper: " loop control. Charles Ma's original code tries to find just the first mathcing instance. The code I wrote finds all unique instances in the integers provided.
    – hughdbrown
    Aug 16, 2009 at 23:35
  • yep, it is possible, so we can first do a check to make sure the index of target, iter, and reviter are not equal. i'll change the code to do that. if you want all possible solutions, hughbrown's code does that :)
    – Charles Ma
    Aug 17, 2009 at 10:02
  • 1
    heh, just found some optimizations to get around the problem of the target being the same number as one of the pointed to numbers :)
    – Charles Ma
    Aug 17, 2009 at 10:18
9

Not for credit or anything, but here is my python version of Charles Ma's solution. Very cool.

def find_sum_to_zero(arr):
    arr = sorted(arr)
    for i, target in enumerate(arr):
        lower, upper = 0, len(arr)-1
        while lower < i < upper:
            tmp = target + arr[lower] + arr[upper]
            if tmp > 0:
                upper -= 1
            elif tmp < 0:
                lower += 1
            else:
                yield arr[lower], target, arr[upper]
                lower += 1
                upper -= 1

if __name__ == '__main__':
    # Get a list of random integers with no duplicates
    from random import randint
    arr = list(set(randint(-200, 200) for _ in range(50)))
    for s in find_sum_to_zero(arr):
        print s

Much later:

def find_sum_to_zero(arr):
    limits = 0, len(arr) - 1
    arr = sorted(arr)
    for i, target in enumerate(arr):
        lower, upper = limits
        while lower < i < upper:
            values = (arr[lower], target, arr[upper])
            tmp = sum(values)
            if not tmp:
                yield values
            lower += tmp <= 0
            upper -= tmp >= 0
1
  • 1
    If you want an explanation, here are the non-obvious bits for a non-python developer: (1) enumerate returns each element of a sequence with its integer index, starting from 0 (2) "lower < i < upper" means "lower < i and i < upper" in a single test (3) yield returns a value from a function but allows execution to continue from that point the next time it is requested (4) set() returns a group of unique items, dumping multiple occurrences (5) multiple variables can be assigned in a single statement (6) the generator statement says, "Give me 50 integers in the range -200 to 200
    – hughdbrown
    Aug 17, 2009 at 13:43
8

put the negative of each number into a hash table or some other constant time lookup data structure. (n)

loop through the array getting each set of two numbers (n^2), and see if their sum is in the hash table.

3
  • This solution will also work for a slightly different question: Are there three/four numbers which sum can be devided by a constant q without remainder?
    – Anna
    Aug 16, 2009 at 5:35
  • This works but it uses O(n) memory which can be avoided if we use one of the other solutions mentioned above.
    – tdeegan
    Nov 20, 2014 at 16:29
  • If this solution is going to be used, then you need to keep track of the index of the number you added to the hashtable so while doing the n^2 loop, you avoid using the same number twice.
    – ralzaul
    Jan 15, 2018 at 17:03
1

First sort the array, then for each negative number (A) in the array, find two elements in the array adding up to -A. Finding 2 elements in a sorted array that add up to the given number takes O(n) time, so the entire time complexity is O(n^2).

1

C++ implementation based on the pseudocode provided by Charles Ma, for anyone interested.

#include <iostream>
using namespace std;

void merge(int originalArray[], int low, int high, int sizeOfOriginalArray){
    //    Step 4: Merge sorted halves into an auxiliary array
    int aux[sizeOfOriginalArray];
    int auxArrayIndex, left, right, mid;

    auxArrayIndex = low;
    mid = (low + high)/2;
    right = mid + 1;
    left = low;

    //    choose the smaller of the two values "pointed to" by left, right
    //    copy that value into auxArray[auxArrayIndex]
    //    increment either left or right as appropriate
    //    increment auxArrayIndex
    while ((left <= mid) && (right <= high)) {
        if (originalArray[left] <= originalArray[right]) {
            aux[auxArrayIndex] = originalArray[left];
            left++;
            auxArrayIndex++;
        }else{
            aux[auxArrayIndex] = originalArray[right];
            right++;
            auxArrayIndex++;
        }
    }

    //    here when one of the two sorted halves has "run out" of values, but
    //    there are still some in the other half; copy all the remaining values
    //    to auxArray
    //    Note: only 1 of the next 2 loops will actually execute
    while (left <= mid) {
        aux[auxArrayIndex] = originalArray[left];
        left++;
        auxArrayIndex++;
    }

    while (right <= high) {
        aux[auxArrayIndex] = originalArray[right];
        right++;
        auxArrayIndex++;
    }

    //    all values are in auxArray; copy them back into originalArray
    int index = low;
    while (index <= high) {
        originalArray[index] = aux[index];
        index++;
    }
}

void mergeSortArray(int originalArray[], int low, int high){
    int sizeOfOriginalArray = high + 1;
    //    base case
    if (low >= high) {
        return;
    }

    //    Step 1: Find the middle of the array (conceptually, divide it in half)
    int mid = (low + high)/2;

    //    Steps 2 and 3: Recursively sort the 2 halves of origianlArray and then merge those
    mergeSortArray(originalArray, low, mid);
    mergeSortArray(originalArray, mid + 1, high);
    merge(originalArray, low, high, sizeOfOriginalArray);
}

//O(n^2) solution without hash tables
//Basically using a sorted array, for each number in an array, you use two pointers, one starting from the number and one starting from the end of the array, check if the sum of the three elements pointed to by the pointers (and the current number) is >, < or == to the targetSum, and advance the pointers accordingly or return true if the targetSum is found.

bool is3SumPossible(int originalArray[], int targetSum, int sizeOfOriginalArray){
    int high = sizeOfOriginalArray - 1;
    mergeSortArray(originalArray, 0, high);

    int temp;

    for (int k = 0; k < sizeOfOriginalArray; k++) {
        for (int i = k, j = sizeOfOriginalArray-1; i <= j; ) {
            temp = originalArray[k] + originalArray[i] + originalArray[j];
            if (temp == targetSum) {
                return true;
            }else if (temp < targetSum){
                i++;
            }else if (temp > targetSum){
                j--;
            }
        }
    }
    return false;
}

int main()
{
    int arr[] = {2, -5, 10, 9, 8, 7, 3};
    int size = sizeof(arr)/sizeof(int);
    int targetSum = 5;

    //3Sum possible?
    bool ans = is3SumPossible(arr, targetSum, size); //size of the array passed as a function parameter because the array itself is passed as a pointer. Hence, it is cummbersome to calculate the size of the array inside is3SumPossible()

    if (ans) {
        cout<<"Possible";
    }else{
        cout<<"Not possible";
    }

    return 0;
}
0

This is my approach using Swift 3 in N^2 log N...

let integers = [-50,-40, 10, 30, 40, 50, -20, -10, 0, 5]

First step, sort array

let sortedArray = integers.sorted()

second, implement a binary search method that returns an index like so...

func find(value: Int, in array: [Int]) -> Int {

    var leftIndex = 0
    var rightIndex = array.count - 1

    while leftIndex <= rightIndex {

        let middleIndex = (leftIndex + rightIndex) / 2
        let middleValue = array[middleIndex]

        if middleValue == value {
            return middleIndex
        }
        if value < middleValue {
            rightIndex = middleIndex - 1
        }
        if value > middleValue {
            leftIndex = middleIndex + 1
        }
    }
    return 0
}

Finally, implement a method that keeps track of each time a set of "triplets" sum 0...

func getTimesTripleSumEqualZero(in integers: [Int]) -> Int {

    let n = integers.count
    var count  = 0

    //loop the array twice N^2
    for i in 0..<n {
        for j in (i + 1)..<n {
            //Sum the first pair and assign it as a negative value
            let twoSum = -(integers[i] + integers[j])
           // perform a binary search log N
            // it will return the index of the give number
            let index = find(value: twoSum, in: integers)
            //to avoid duplications we need to do this check by checking the items at correspondingly indexes
            if (integers[i] < integers[j] &&  integers[j] < integers[index]) {
                print("\([integers[i], integers[j], integers[index]])")
                count += 1
            }
        }
    }
    return count
}

print("count:", findTripleSumEqualZeroBinary(in: sortedArray))

prints--- count: 7

0
void findTriplets(int arr[], int n) 
{ 
    bool found = false; 
    for (int i=0; i<n-1; i++) 
    { 
        unordered_set<int> s; 
        for (int j=i+1; j<n; j++) 
        { 
            int x = -(arr[i] + arr[j]); 
            if (s.find(x) != s.end()) 
            {  
                printf("%d %d %d\n", x, arr[i], arr[j]); 
                found = true; 
            } 
            else
                s.insert(arr[j]); 
        }  
    } 
    if (found == false) 
        cout << " No Triplet Found" << endl; 
} 
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.