Problem: Two Sum

Hello everyone, today we are going to solve one of the popular problem "Two Sum". I pick this question from LeetCode. The following description is below

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.

Example 1
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: 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]

Constraints:
2 <= nums.length <= 10^4
-10^9 <= nums[i] <= 10^9
-10^9 <= target <= 10^9
Only one valid answer exists.

There are common two solutions for this problem.

[1] Brute Force This is the most simple and straightforward. We compare one by one elements in the input array to find the sum of those two are equal to target number. The outer loop is the 1st element and the inner loop is 2nd element which is next to 1st element. While we are looping if we found two numbers that sum to be target number, we return the output array. Otherwise go to next round. The code is shown below

public int[] twoSum(int[] nums, int target) {
    for (int i = 0; i < nums.length - 1; i++) {
        for (int j = i + 1; j < nums.length; j++) {
            if (nums[j] + nums[i] == target) {
                return new int[] { i, j };
            }
        }
    }
    return null; // We can return null because there is always only one answer.
}

Time complexity: O(n^2)
Space complexity: O(1)

It's working but in term of time complexity it's not good much because we are using nested-loop which is turn to be O(n^2). How do we improve the algorithm to be more faster?

[2] One-pass Hash Table The idea of this solution is that we fix the 1st number in each round and trying to find 2nd number that sum each other to be equal to target number. We start by creating empty hash map and loop each element in the input array by thinking about this hypothesis

current number + answer = target number

We are finding what the value of answer so we change a little bit of equation to be

answer = target number - current number

Then we check if there is answer key is stored in hash map (The indice and value that we have seen in each round of loop) We can return the output array of current index and the value of answer stored in hash map. Otherwise we just update hash map to store the current value and its index. The code is shown below

public int[] twoSum(int[] nums, int target) {
    HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();

    for (int i = 0; i < nums.length; i++) {
        int cur = nums[i];
        int x = target - cur;

        if (map.containsKey(x)) {
            return new int[] { map.get(x), i };
        }

        map.put(cur, i);
    }

    return null; // We can return null because there is always only one answer.
}

Time complexity: O(n)
Space complexity: O(n) (we store value in hash map)

Although space complexity is increased from O(1) to O(n) but most of the time we care about time complexity more than space complexity which is reduced from O(n^2) to O(n)

So, the second solution is more appropriate than the first solution.

Thank you for your time. If you enjoy my sharing daily problem solving solution feel free to comment, like, subscribe and share so the others could get benefit from this. See you again later. ʕ •ᴥ•ʔ

Reference: https://leetcode.com/problems/two-sum/