Given an array of numbers, find out if 3 of them add up to 0
algorithm
Solution
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.
Problem
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?