Two Sum

Two sum is one of the first questions on leetcode. Let's see how we can solve this problem.

Description

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Output: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]

Example 3:

Input: nums = [3,3], target = 6
Output: [0,1]

Approach - 1: Brute Force

Now the brute force solution is to check every pair to see if it sums up to target and if so return the corresponding indices. Let's check the code for this approach.

// TC: O(n^2), SC: O(1)
public int[] twoSum_BruteForce(int[] nums, int target) {
    for (int i = 0; i < nums.length - 1; i++) {
        for (int j = i + 1; j < nums.length; j++) {
            if (nums[i] + nums[j] == target) return new int[]{i, j};
        }
    }
    return new int[0];
}

Since we have nested for loops, time complexity for this approach is O(n^2) while space complexity is O(1) since we are not using any extra space.

⚠ Note the usage of j = i + 1 in the second for loop. You can have the same code with j = 0 as well, but you would need to also check i != j or else we would consider the same number while adding.

Approach - 2: Using Hashmap

In the previous approach when i = 0, we iterate the entire array, but when i = 1, we iterate the array all over again. This is duplicate, unnecessary work that we were doing before which led us to having a poor algorithm with time complexity of O(n^2). Instead what if we could replace the inner for loop with hashmap?

That is as we iterate the array, we ask to see if we have found our complementary number. Consider that the target needed is 10. And the current number is 6. Then the complementary number that we would need is 4 since 6 + 4 = 10. Therefore while we are standing on 6, we ask if a complementary number was already found and if so we can get its index and return the current number's index as well. And the way to find out complementary number is to simply subtract current number from target i.e., complementary number = target - current.

Now let's check the solution for this:

// TC: O(n), SC: O(n)
public int[] twoSum_HashMap(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i];
        if (map.containsKey(complement)) return new int[]{map.get(complement), i};
        else map.put(nums[i], i);
    }
    return new int[2];
}

The above solution has a time complexity of just O(n) since we have a single for loop. And the space complexity would also be O(n), since in worst case we will store all numbers in the hashmap and hit the last line which is return new int[2].

Approach 3: Using Sorting + Two Pointers

There is another approach using sorting. This approach is very useful when you solve problems that are derived from Two Sum like Three Sum, Four Sum etc.

First step is to sort the array. Second step is to have two pointers with one pointing to the left most index of the sorted array while another pointer pointing to the right most index of the sorted array.

Then you check the sum of values pointed to by these two pointers and there can be three cases.

• Case 1: If sum is equal to the target, you have found your answer.
• Case 2: If sum less than the target, then it means that the sum which you just calculated was small and therefore you need to increase this sum. And how does one increase this sum in a sorted array? You just move your left pointer rightward. Why not right pointer? Well remember that this is a sorted array, and moving the right pointer leftward would mean that we are reducing this sum.
• Case 3: If sum is greater than the target, then it means that sum was too large and you need to reduce it. And just like in case 2, in order to reduce the sum, you will move the right pointer leftward.

Now let's check the code for this approach.

// TC: O(nlogn), SC: O(n)
public int[] twoSum_Sort(int[] nums, int target) {
    List<Pair> pairs = new ArrayList<>();
    for (int i = 0; i < nums.length; i++) pairs.add(new Pair(nums[i], i));

    pairs.sort(Comparator.comparingInt(a -> a.num));

    int i = 0, j = pairs.size() - 1;
    while (i < j) {
        int currentSum = pairs.get(i).num + pairs.get(j).num;
        if (currentSum == target) {
            return new int[]{pairs.get(i).index, pairs.get(j).index};
        } else if (currentSum < target) i++;
        else j--;
    }
    return new int[2];
}

static class Pair {
    int num, index;

    Pair(int num, int index) {
        this.num = num;
        this.index = index;
    }
}

The time complexity for the above solution would be O(nlogn) since we are sorting the array initially. And after that the while loop is just O(n). The space complexity is O(1) since no extra space was needed.