Sum of two elements (2sum)

Photo: Two zebras
“Photo by Geran de Klerk on Unsplash

The two-sum puzzle

// input
int[] data = {1, 3, -1, 5, 8, 10};
int sum = 9;

// output
int[] solution = {0, 4};

Simplest solution

public static int[] findSumTwo(int[] data, int sum) {
// iterate until the next to last element
for (int i = 0; i < data.length-1; i++) {
// iterate to the last element, starting from the second element
for (int j = 1; i < data.length; j++) {
// (the double loop will start from the
// {0, 1} index pair and stop iterating at {n-1, n})

// if the elements add up, return their indices
if (data[i]+data[j] == sum) return new int[]{i,j};
}
}

// not found
return new int[]{-1};
}

A fast but costly solution

  • 9-1 = 8
  • 9-3 = 6
  • 9-(-1) = 10
  • 9-5 = 4
  • 9-8...
public static int[] findSumTwo(int[] data, int sum) {
// value->index map
Map<Integer, Integer> seen = new HashMap<>();

// iterate through the array once (O(N))
for (int pos=0; i < data.length; i++) {
// assigning the element for convenience
// because it reads better
int element = data[i];

// if we've already seen the current element
if (seen.containsKey(element)) {
// form a solution
return new int[]{seen.get(element), pos};
}

// otherwise mark its difference as 'seen'
seen.put(sum-element, i);
}

// not found
return new int[]{-1};
}

No extra space-complexity

public static int[] findSumTwo(int[] data, int sum) {
int left=0;
int right=data.length-1;

// only iterate until the positions are valid
// O(N)
while (left < right) {
int found = data[left] + data[right];

if (found == sum) {
// we have found a solution
return new int[]{left, right};
} else if (found < sum) {
// we need a larger number
left++;
} else {
// or a lower one
right--;
}
}

// not found
return new int[]{-1};
}
// most sorting algorithms run in O(N*lgN) time
Arrays.sort(data);

Edge cases

// empty input
int[] data = {};
int sum = /*irrelevant*/;

// null input
int[] data = null;
int sum = /*irrelevant*/;

// overflow
int[] data = {Integer.MAX_VALUE, Integer.MAX_VALUE};
int sum = -2; // doesn't seem correct, but it is given the Integer input

// not enough elements
int[] data = {9};
int sum = 9; // we need at least two elements for a valid solution

// equal elements
int[] data = {8,8};
int sum = 16; // this would cause the first solution to wrongly return {0,0}

// unsorted input
int[] data = {3,1};
int sum = 4; // the correct solution is {0,1}

// no solution
int[] data = {1,1};
int sum = 3; // no pair can sum up to 3
  • always assume the input can be tainted unless explicitly told otherwise
  • think of null values and how they can break the code
  • do not assume the input is sorted
  • clarify what the output should look like
  • avoid printing outputs — it’s hard to test and results in messy code
  • understand the consequences of making a choice (e.g., “if I need to sort the input, the time-cost is at least N*lgN)
  • explicitly state assumptions (e.g., “I assume the input is sorted”, or “I assume the input has a valid solution”)
  • show a good understanding of big-O notation and algorithmic performance

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Mihai Bojin

Mihai Bojin

Software Engineer at heart, Manager by day, Indie Hacker at night. Writing about DevOps, Software engineering, and Cloud computing. Opinions my own.