Link Search Menu Expand Document

A Deeper Look into TwoSum

Table of contents

  1. Problem
  2. Code
  3. Full Runtime Analysis

Problem

Recall that an algorithm for TwoSum takes in an array of integers and a target number. It’ll return the indicies of distinct integers within the array that sum up to the target. If it can’t find two such integers, it’ll return -1, -1.

For example:

  int[] example = new int[] {1, 9, 3, 0, 8, 5};

  // Should output {1, 5} (arr[1] + arr[5] = 9 + 5 = 14
  System.out.println(Arrays.toString(twoSumSlow(example, 14)));

  // Should output {-1, -1}
  System.out.println(Arrays.toString(twoSumSlow(example, 42)));

Code

Here’s the code for the “slow” version of TwoSum:

  public static int[] twoSumSlow(int[] arr, int target) {
    for (int i = 0; i < arr.length; i++) {
      for (int j = i+1; j < arr.length; j++) {
        if (arr[i] + arr[j] == target) {
          return new int[] {i, j};
        }
      }
    }
    return new int[] {-1, -1};
  }

Full Runtime Analysis

In order to find the runtime of twoSumSlow, let’s count every step of the code as a function of N, where N is the size of the array.

First off, we have the outer for loop:

    for (int i = 0; i < arr.length; i++) {

This line takes one step for int i = 0;, N steps for each check against the length of the array, and N steps for the increment, for a total of 2N + 1. Note that when we looked at this for loop, we added up all the checks that we we would make while we iterate through the length of the array.

      for (int j = i+1; j < arr.length; j++) {

The inner for loop is a bit more challenging. We have two steps for int j = i+1; (addition, then assignment), We do roughly N/2 checks on average every time we’re checking the length of the array, and another N/2 for the increment. Total, this comes out to N+2 per iteration. Since we execute the inner for loop N times, the overall cost is N2 + 2N.

Now how did we get N/2 on average? Since j depends on i, we have the following relationship while iterating through the array:

ij# of j++
01N - 1
12N - 2
23N - 3
N-2N-11
N-1N0

Observe that there’s an inverse relationship between i/j, and the number of times j++ gets called in each inner for loop (as i and j go up, the number of times j++ gets called during that iteration goes down.)

Since we have N different js (1, 2, .., N-1, N), the number of increments on average is approximately N/2 (actually N/2 - 1/2, but let’s fudge it for simplicity.)

Now all that’s left is the if check and the return:

        if (arr[i] + arr[j] == target) {
          return new int[] {i, j};
        }

The if will take 4 steps each time (2 array lookups, one addition, one equality check). We’ll run the if roughly N2/2times since it’s inside both for loops for a total of 4N2/2 = 2N2.

Since we only return once, we’ll only need to add two steps for creating a new array and returning it. Likewise, we don’t need to add any more steps to count the return new int[] {-1, -1} since we will only either return inside the if, or at the end.

All in all, here’s our total number of steps in terms of N, the length of the array:

2N + 1 N2 + 2N + 2N2 + 2
= 3N2 + 4N + 3

Finally, since we’re able to use Big-O notation, we can ignore the smaller terms (4N + 3) and the multiplcative constants (the 3 in front of the N2) and say twoSumSlow ∈ O(N2) where N is the length of the input array.