Problem Statement

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

This is actually a problem I got during a job interview back in my first or second year of CS. When I came across it again, I instantly recognized it. Although this specific question is a little different, as I’m supposed to return the indices of the two numbers, whereas during my interview, I had to return the numbers themselves. Still, it’s basically the same question.

Example

  • Given nums = [2, 7, 11, 15], target = 9,
  • Because nums[0] + nums[1] = 2 + 7 = 9,
  • return [0, 1].

Crappy (initial) solution

So I mentioned that I got this problem before during an interview, I actually solved it and came to a solution back then, and while I don’t remember my exact code or thought process, I do remember that my approach was to just use two loops.

public static int[] twoSumShitty(int[] nums, int target) {

    for (int i = 0; i < nums.length; i++) {
		for (int j = i + 1; j < nums.length; j++) {
			System.out.println("Comparing " + i + " to " + j + " => " + nums[i] + " + " + nums[j]);
			if (nums[i] + nums[j] == target) {
				System.out.println(Arrays.toString(new int[] { i, j }));
				return new int[] { i, j };
			}
		}
	}
		
	System.out.println("NOT FOUND.");
	return new int[] { -1, -1 };
}

I added some extra printlns just to illusrate what’s happening. We’re bruteforcing and comparing every value within the array, which has a time-complexity of O(n^2).

In a random 50-element array with values between 0-50, and a target value of 15, we get the following output:

bsearch0

3 + 11 = 15, so we are returned the indices of 3 and 11, which happen to be 0 and 8. This works, but like my interviewer back then told me, is not even close to the most efficient solution. Believe me, we got lucky here with the input.

Better (but still crappy) solution

After some prodding and tips from the interviewer, I came to a solution that was similar to this, which involves sorting the array, this means we don’t need as many comparisons. This solution’s runtime is bound by Arrays.sort(), O(logn)

public static int[] twoSumSlightlyLessShitty(int[] nums, int target) {
    Arrays.sort(nums);
    System.out.println("Sorted array: " + Arrays.toString(nums));

    int i = 0;
    int j = nums.length - 1;

    while (i != j) {
        System.out.println("Comparing " + i + " to " + j + " => " + nums[i] + " + " + nums[j]);
        if (nums[i] + nums[j] == target) {
            System.out.println(Arrays.toString(new int[] { i, j }));
            return new int[] { i, j };
        } else if (nums[i] + nums[j] < target) {
            i++;
        } else if (nums[i] + nums[j] > target) {
            j--;
        }
    }
    
    System.out.println("NOT FOUND.");
    return new int[] { -1, -1 };
}

Okay so, quick disclaimer: the best way of solving this problem is to use hash tables, likely the solution my interviwer was looking for.

That’s simple enough, but a much cooler solution is to use binary search. Why? Because I learned binary-search in school and WANT TO ACTUALLY USE IT FOR SOMETHING DAMNIT! So here it is! Again, I added some extra printlns to show the number of b-searches done and to show what’s happening.

Solved with b-search:

public static int[] twoSum(int[] nums, int target) { // uses bSearch

    // sort the damn thing first
    Arrays.sort(nums);
    System.out.println("Sorted array: " + Arrays.toString(nums));

    // these represent indices
    int low = 0;
    int high = nums.length - 1;
    int c = 0; // b-search counter
    
    for (int i = 0; i < nums.length; i++) {
        int s = target - nums[i];

        int index = bSearch(nums, s);
        c++;

        if (index > 0) {
            System.out.println("Number of b-searches performed: " + c);
            System.out.println(Arrays.toString(new int[] { i, index }));
            return new int[] { i, index };
        }

    }
    
    System.out.println("NOT FOUND.");
    return new int[] { -1, -1 };
}

public static int bSearch(int[] numbers, int val) {
    // these represent indices
    int low = 0;
    int high = numbers.length - 1;

    while (low <= high) {

        int mid = ((high + low) / 2);

        // System.out.println("Mid = " + mid + "\nLow = " + low + "\nHigh =
        // " + high + "\n");

        if (numbers[mid] == val) {
            // System.out.println("Index of " + val + " is: " + mid);
            return mid;
        }

        else if (numbers[mid] > val) {
            high = mid - 1;
        }

        else if (numbers[mid] < val) {
            low = mid + 1;
        }

    }

    return -1;
}

What’s happening here is we perform a binary search for the target value minus the current value we’re at in the array. If we cannot find it, then we move to the next element in the array and try again.