Two Sum

The solution to the Two Sum problem in Java

Nov 1, 20213 min read

Overview:

Two Sum is a programming problem where you are given an array and a target value and you have to find the indices of the elements in the array that add up to the target value. This is an “easy” level problem in LeetCode. In this article, we will attempt to solve this problem and then optimize the solution for faster runtime.

Question:

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to _target_. You may assume that each input would have exactly one solution, and you may not use the same element twice. You can return the answer in any order.

For example, for a given input nums = [3, 5, 6, 2] and target = 7, the output will be [1, 3] where nums[1] + nums[3] = target.

Brute Force:

The brute force solution to this problem requires two loops, one inside the other. The outer loop will loop over the array, and for each element visited, the inner loop will loop over the remaining elements in the array and check if the two elements add up to the target value.

Solution 1

Once we have the two values that add up to the target value, we simply return the two indices of the array with those values. Since the question specifies that there will be exactly one solution, we do not have to worry about edge cases.

class Solution {
  public int[] twoSum(int[] nums, int target) {
    int ans[] = new int[2];
    for(int i = 0; i < nums.length - 1; i++) {
      for(int j = i + 1; j < nums.length; j++) {
        if(nums[i] + nums[j] == target) {
          ans[0] = i;
          ans[1] = j;
          return ans;
        }
      }
    }
    return ans;
  }
}

One concern with this solution is that its runtime complexity is O(n²). This means that the runtime of the program is directly proportional to the square of the input size and is not optimal for larger arrays.

One way to reduce the runtime complexity is to increase the space complexity. This can be achieved by using a HashMap.

HashMap:

The hashmap solution to this problem requires only one loop to go over every element in the array. It also needs a hashmap to store all the elements of the array we visit. Storing the elements in a hashmap allows us to compare the value of the currently visited element of the array with an already visited element from the hashmap. Since the lookup time for a hashmap is a constant O(1), the total time complexity of the program is now O(n).

Solution 2

Since we are looking for the sum of two numbers in the array that add up to the target value, we can simply check if the difference of the target value and the currently visited element of the array exists in the hashmap. We will store the value of the element as the key of the map and the index of the element as the value of the map. This lets us look up the value and retrieve the index if the value exists in the map.

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

Notice that the hashmap should already be populated with at least the first element of the array and the loop should start with the second element. This lets us have at least one value from the hashmap to compare with the current element of the array. Although the hashmap takes more space in the memory than the brute force solution, it definitely finishes running significantly faster.

In a nutshell:

Two Sum is one of the first problems you come across when you’re on Leetcode. For the brute force solution to the problem, you simply need a loop inside of another loop and compare the values until you find the two numbers that add up to the target value. Although the brute force solution is quite intuitive, you compromise on runtime if you go with it. The hashmap solution significantly improves your runtime complexity, however, is a tradeoff for extra space in your memory.

Happy Programming!