Article #2 in a 9-part series.

In the previous problem , we looked at anagrams for fun and practice. In this post we search for the sum-zero triplet. Given an array of integers, find three integers with a sum of zero. I encountered this problem during a phone interview and asked to write the code live in collabedit . My first thought was to do some sort of mapping, but later I realized I could sort the array in order to break from a loop early. If you’re practicing for an interview, try writing your solution in a text editor rather than an IDE. At the bottom you’ll find two variations to my solution written in C# and a sample written in Java.

observations
The array must have at least three integers since the problem specifically asks for three, not three or fewer. Three zeros would do it, otherwise there needs to be at least one negative. Sorting an array allows us to use BinarySearch, direct our search for a third integer based on a starting pair, or break early realizing the lowest value is positive.

program
The first step is to check our parameter for at least three integers. The first variation below uses BinarySearch and is the answer I submitted. After some thought, I came up with the second variation looking for the answer based on the previous sum to squeeze towards the answer. Both solutions are exponential in performance.

C#: find sum-zero triplet variation 1 /// adds a pair and uses BinarySearch to find 3rd

/// <param name="numbers"></param>

static List < int > FindThreeNumbersSumZero ( int [] numbers )

List < int > result = new List < int >();

if ( numbers != null && numbers . Length > 2 )

// must be at least a negative or 3 zeros.

if ( numbers [ 0 ] > 0 ) return result ;

// for every summed pair, look for a number that negates

for ( int i = 0 ; i < numbers . Length - 1 ; ++ i )

for ( int j = i + 1 ; j < numbers . Length ; ++ j )

int sumOfPair = numbers [ i ] + numbers [ j ];

int numToFind = - 1 * sumOfPair ;

int index = Array . BinarySearch ( numbers , numToFind );

result . Add ( numbers [ index ]);

This second variation is a complete program. Sum integers from both ends of a sorted function and squeeze towards the answer, if any.

C#: find sum-zero triplet variation 2 static void Main ( string [] args )

int [] numArray1 = { 0 , 5 , - 2 , 2 , - 3 , 42 , 10 };

int [] numArray2 = { 1 , 4 , 0 , 7 , 3 };

int [] numArray3 = { 10 , 4 , - 4 , 8 , 0 };

int [] testArray = { - 2 , - 1 , - 3 , 4 , - 5 , 6 };

performTestOnArray ( numArray1 );

performTestOnArray ( numArray2 );

performTestOnArray ( numArray3 );

performTestOnArray ( testArray );

static void performTestOnArray ( int [] testArray )

System . Console . Write ( "test numbers: " );

System . Console . WriteLine ( "[{0}]" , string . Join ( ", " , testArray ));

List < int > sumsZeroList = FindTripletSumZero ( testArray );

if ( sumsZeroList . Count > 0 )

System . Console . Write ( "sums to zero with triplets: " );

System . Console . WriteLine ( "[{0}]" , string . Join ( ", " , sumsZeroList ));

System . Console . WriteLine ( "has no triplets sum zero" );

/// use the squeeze approach on sorted array

/// <param name="numbers"></param>

static List < int > FindTripletSumZero ( int [] numbers )

List < int > result = new List < int >();

if ( numbers != null && numbers . Length > 2 )

// all positives never sum to zero

if ( numbers [ 0 ] > 0 ) return result ;

// check from each end and adjust according to sorted order

for ( int i = 0 ; i < numbers . Length - 2 ; ++ i )

int left = i + 1 ; // begin after i

int right = numbers . Length - 1 ; // begin at end

// squeeze until right crosses paths with left

int sum = numbers [ i ] + numbers [ left ] + numbers [ right ];

result . Add ( numbers [ left ]);

result . Add ( numbers [ right ]);

// squeeze towards left to find closer match

// squeeze to right to find closer match

Java solution using the squeeze approach.

Java find sum-zero triplet public class TestQuestions

public static void main ( String [] args ) {

int [] testArray1 = {- 2 , - 1 , - 3 , 4 , - 5 , 6 };

int [] testArray2 = {- 5 , 5 , 6 , - 8 , 42 };

int [] testArray3 = { 1 , 4 , 8 , 10 , 15 };

int [] testArray4 = { 10 , 5 , - 5 , - 2 , - 8 , 12 , 16 , - 10 , 5 };

performTestOnArray ( testArray1 );

performTestOnArray ( testArray2 );

performTestOnArray ( testArray3 );

performTestOnArray ( testArray4 );

public static void performTestOnArray ( int [] testArray )

System . out . println ( "Test Array: " + Arrays . toString ( testArray ));

List < Integer > sumZero = SumZeroProblem . findTripletSumZero ( testArray );

if ( sumZero != null && sumZero . size () > 0 ) {

System . out . println ( " contains triplet sum zero: " + sumZero );

System . out . println ( " does not contain a triplet that sums to zero" );

public class SumZeroProblem

public static List < Integer > findTripletSumZero ( int [] numbers )

List < Integer > result = new ArrayList < Integer >();

// check argument: must have at least 3 elements

if ( numbers != null && numbers . length > 2 ) {

// all positives never sum to zero

if ( numbers [ 0 ] > 0 ) return result ;

// check starting from each end and

// squeeze according to sorted order

for ( int i = 0 ; i < numbers . length - 2 ; ++ i ) {

int left = i + 1 ; // begin after i

int right = numbers . length - 1 ; // begin at right end

// squeeze until right and left indexes cross paths

int sum = numbers [ i ] + numbers [ left ] + numbers [ right ];

result . add ( numbers [ left ]);

result . add ( numbers [ right ]);

// too big: squeeze towards left

// too small: squeeze right

Swift 2.1: try in a Playground

Swift 2.1: find sum-zero triplet let numArray1 = [ 0 , 5 , - 2 , 2 , - 3 , 42 , 10 ];

let numArray2 = [ 1 , 4 , 0 , 7 , 3 ];

let numArray3 = [ 10 , 4 , - 4 , 8 , 0 ];

let testArray = [ - 2 , - 1 , - 3 , 4 , - 5 , 6 ];

func findTripletSumZero ( inIntegers intArray : [ Int ]) -> ( Int , Int , Int ) ?

let sortedArray = intArray . sort ()

// all positives never sum zero

// check from each end and adjust according to sorted order

for i in 0 .. < sortedArray . count

var right = sortedArray . count - 1

// squeeze until right crosses paths with left

let sum = sortedArray [ i ] + sortedArray [ left ] + sortedArray [ right ]

return ( sortedArray [ i ], sortedArray [ left ], sortedArray [ right ])

func performTest ( inIntegers intArray : [ Int ])

let test = findTripletSumZero ( inIntegers : intArray )

print ( "Array \(intArray) has no triplet which sum zero." )

print ( "Array \(intArray) has zero-sum triplet: (\(firstInt),\(secondInt),\(thirdInt))." )

performTest ( inIntegers : testArray )

performTest ( inIntegers : numArray1 )

performTest ( inIntegers : numArray2 )

performTest ( inIntegers : numArray3 )

Swift 3

Swift 3: find sum-zero triplet let numArray1 = [ 0 , 5 , - 2 , 2 , - 3 , 42 , 10 ];

let numArray2 = [ 1 , 4 , 0 , 7 , 3 ];

let numArray3 = [ 10 , 4 , - 4 , 8 , 0 ];

let testArray = [ - 2 , - 1 , - 3 , 4 , - 5 , 6 ];

func findTripletSumZero ( inIntegers intArray : [ Int ]) -> ( Int , Int , Int ) ?

let sortedArray = intArray . sorted ()

// all positives never sum zero

// check from each end and adjust according to sorted order

for i in 0 .. < sortedArray . count

var right = sortedArray . count - 1

// squeeze until right crosses paths with left

let sum = sortedArray [ i ] + sortedArray [ left ] + sortedArray [ right ]

return ( sortedArray [ i ], sortedArray [ left ], sortedArray [ right ])

func performTest ( inIntegers intArray : [ Int ])

let test = findTripletSumZero ( inIntegers : intArray )

print ( "Array \(intArray) has no triplet which sum zero." )

print ( "Array \(intArray) has zero-sum triplet: (\(firstInt),\(secondInt),\(thirdInt))." )

performTest ( inIntegers : testArray )

performTest ( inIntegers : numArray1 )

performTest ( inIntegers : numArray2 )

performTest ( inIntegers : numArray3 )

Article #2 in a 9-part series.