Two Sum

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.

My Solution

The first solution that may come to mind is to check every pair of integers in the array and see if it sums to the target value.

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

        // We will never get here
        return out;
    }
}

However, since we have two nested for loops, the algorithmic time complexity for this would be O(n²). We use constant extra space, so the algorithmic space complexity would be O(1). The key to improving our solution is to see if we can tradeoff space complexity for time complexity. In other words, we can use extra space to bring our time complexity down.

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int n = nums.length;
        int[] out = new int[2];
        Map<Integer,Integer> comp = new HashMap<>();
        for (int i = 0; i < n; i++) {
            if (comp.containsKey(target - nums[i])) {
                out[0] = comp.get(target - nums[i]);
                out[1] = i;
                return out;
            }

            comp.put(nums[i], i);
        }

        // We shouldn't get here
        return out;
    }
}

Since we have only one for loop that iterates through the array, algorithmic time complexity would just be O(n). Since we use a HashMap that stores n elements in the worst case, where n is the size of the array, space complexity would also be O(n). So here we have effectively made a tradeoff between space and time. This is the accepted solution.