Programming Problem: Sum-Zero Triplet
Article #2 in a 9-part series.
- 1 - Programming Problem: Determine if Two Strings Are Anagrams
- 2 - this article
- 3 - Programming Problem: Palindromes
- 4 - Problem: Validate a Phone Number
- 5 - Programming Problem: Single-Edit Difference
- 6 - Prime Factors Problem 1: LCM
- 7 - Prime Factors Problem 2: Largest Prime Factor
- 8 - How-To: Substrings in Swift
- 9 - Programming Problem: Pangram
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.
/// <summary>
/// adds a pair and uses BinarySearch to find 3rd
/// </summary>
/// <param name="numbers"></param>
/// <returns></returns>
static List<int> FindThreeNumbersSumZero(int[] numbers)
{
List<int> result = new List<int>();
if (numbers != null && numbers.Length > 2)
{
Array.Sort(numbers);
// 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);
if (index >= 0)
{
result.Add(numbers[i]);
result.Add(numbers[j]);
result.Add(numbers[index]);
return result;
}
}
}
}
return result;
}This second variation is a complete program. Sum integers from both ends of a sorted function and squeeze towards the answer, if any.
namespace SumZeroProblem
{
class Program
{
static void Main(string[] args)
{
// some arrays to test
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));
}
else
{
System.Console.WriteLine("has no triplets sum zero");
}
}
/// <summary>
/// use the squeeze approach on sorted array
/// </summary>
/// <param name="numbers"></param>
/// <returns></returns>
static List<int> FindTripletSumZero(int[] numbers)
{
List<int> result = new List<int>();
// check our argument
if (numbers != null && numbers.Length > 2)
{
Array.Sort(numbers);
// 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
while (right > left)
{
int sum = numbers[i] + numbers[left] + numbers[right];
if (sum == 0)
{
// done
result.Add(numbers[i]);
result.Add(numbers[left]);
result.Add(numbers[right]);
return result;
}
else if (sum > 0)
{
// squeeze towards left to find closer match
right--;
}
else
{
// squeeze to right to find closer match
left++;
}
}
}
}
return result;
}
}
}Java solution using the squeeze approach.
import java.util.*;
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);
}
else {
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) {
// sort
Arrays.sort(numbers);
// 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
while (right > left) {
int sum = numbers[i] + numbers[left] + numbers[right];
if (sum == 0) {
// we're done
result.add(numbers[i]);
result.add(numbers[left]);
result.add(numbers[right]);
return result;
}
else if (sum > 0) {
// too big: squeeze towards left
right--;
}
else {
// too small: squeeze right
left++;
}
}
}
}
return result;
}
}Swift 2.1: try in a Playground
import Cocoa
// test numbers
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)?
{
if intArray.count < 3 {
return nil
}
let sortedArray = intArray.sort()
// all positives never sum zero
if sortedArray[0] > 0 {
return nil
}
// check from each end and adjust according to sorted order
for i in 0 ..< sortedArray.count
{
var left = i + 1;
var right = sortedArray.count - 1
// squeeze until right crosses paths with left
while right > left
{
let sum = sortedArray[i] + sortedArray[left] + sortedArray[right]
if sum == 0
{
return (sortedArray[i], sortedArray[left], sortedArray[right])
}
else if sum > 0 {
right -= 1
}
else {
left += 1
}
}
}
return nil
}
func performTest(inIntegers intArray: [Int])
{
let test = findTripletSumZero(inIntegers: intArray)
if (test == nil) {
print("Array \(intArray) has no triplet which sum zero.")
}
else {
let firstInt = test!.0
let secondInt = test!.1
let thirdInt = test!.2
print("Array \(intArray) has zero-sum triplet: (\(firstInt),\(secondInt),\(thirdInt)).")
}
}
performTest(inIntegers: testArray)
performTest(inIntegers: numArray1)
performTest(inIntegers: numArray2)
performTest(inIntegers: numArray3)Swift 3
import Cocoa
// test numbers
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)?
{
if intArray.count < 3 {
return nil
}
let sortedArray = intArray.sorted()
// all positives never sum zero
if sortedArray[0] > 0 {
return nil
}
// check from each end and adjust according to sorted order
for i in 0 ..< sortedArray.count
{
var left = i + 1;
var right = sortedArray.count - 1
// squeeze until right crosses paths with left
while right > left
{
let sum = sortedArray[i] + sortedArray[left] + sortedArray[right]
if sum == 0
{
return (sortedArray[i], sortedArray[left], sortedArray[right])
}
else if sum > 0 {
right -= 1
}
else {
left += 1
}
}
}
return nil
}
func performTest(inIntegers intArray: [Int])
{
let test = findTripletSumZero(inIntegers: intArray)
if (test == nil) {
print("Array \(intArray) has no triplet which sum zero.")
}
else {
let firstInt = test!.0
let secondInt = test!.1
let thirdInt = test!.2
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.
- 1 - Programming Problem: Determine if Two Strings Are Anagrams
- 2 - this article
- 3 - Programming Problem: Palindromes
- 4 - Problem: Validate a Phone Number
- 5 - Programming Problem: Single-Edit Difference
- 6 - Prime Factors Problem 1: LCM
- 7 - Prime Factors Problem 2: Largest Prime Factor
- 8 - How-To: Substrings in Swift
- 9 - Programming Problem: Pangram