Leetcode 1 Two Sum

Leetcode 1 Two Sum

Edit Two Sum on GitHub

The problem description is as follow:

Given an array of integers, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution.

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

Super Naive Approach

Brute force is always helpful, at least a good start. Checking all the possible combinations will take O(n^2) time complexity.

public static int[] twoSum(int[] numbers, int target) {
  int[] result = new int[2];
  for (int i = 0; i < numbers.length; i++) {
    for (int j = i + 1; j < numbers.length; j++) {
      if (numbers[i] + numbers[j] == target) {
        result[0] = i + 1;
        result[1] = j + 1;
        return result;
      }
    }
  }
  return result;
}

Naive Approach

From the given example, you might assume that the input array is sorted in ascending order. We can improve a bit on the super naive approach base on this assumption.

If the input array is sorted in ascending order,   instead of checking all the possible combinations, we could have the following:

1. Assign a pointer pointing the first element (also the smallest) of the input array
2. Assign second pointer pointing the last element (also the largest) of the input array
3. Compare the target with the sum of the two numbers pointed and move either the first pointer or second pointer correspondingly

public class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int[] result = new int[2];
        int start = 0;
        int end = numbers.length-1;
        while(start<end){
            if(numbers[start]+numbers[end]<target){
                start++;
            }
            else if(numbers[start]+numbers[end]>target){
                end--;
            }
            else{
                result[0] = start+1;
                result[1] = end+1;
                break;
            }
        }
        return result;
    }
}

This method is traversing the input array from both ends to the middle, thus the time complexity is O(n).

However, what if the input array is not sorted? You might propose to use Arrays.sort() on the input array, which elevate the time complexity to O(nlogn). Besides, since the original problem is requiring indices of the two numbers, sorting won’t give the correct answer.

HashMap Approach 

There is no free lunch in the world. If we still want to keep the time complexity as O(n), we will have to trade with space. We use a HashMap to save the value we need.

public class Solution {
    public int[] twoSum(int[] numbers, int target) {
    HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
    int[] result = new int[2];
 
    for (int i = 0; i < numbers.length; i++) {
        if (map.containsKey(numbers[i])) {
            int index = map.get(numbers[i]);
            result[0] = index+1 ;
            result[1] = i+1;
            break;
        } else {
            map.put(target - numbers[i], i);
        }
    }
 
    return result;
    }
}

Since put and get operation in HashMap usually takes O(1), the time complexity will remains O(n).