#1: Two Sum

Problem

Find the indices of two elements in an integer array whose sum is equal to the given target, assuming there is only one such solution.

Example

target = 9
array = [3, 5, 7, 1, 6, 10]
answer = [0, 4]
Explanation: array[0] + array[4] = 3 + 6 = 9 = target

Hint

There are roughly C(n, 2) possible sums in the array, one of which equals the target value. In other words, you’ll need to check every possible sum and see if it matches the target value.
O(n²) Time: For every element, check every subsequent element and see if they add to give the sum.
O(n) Time: Create a memo of every element you’ve visited. At every visit, see if the memo contains the value you need for sum = target.

Planet Boom: A teeny separator between the hint and the solution. And of course, for your visual pleasure :)

Solution

O(n²) Time: Use a nested for-loop to iterate through the array for every element.

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[i] + nums[j] == target)
                return new int[]{i, j};
        }
    }
        
    return new int[]{-1, -1};   // could not find target
}

O(n) Time: Use a Hash Map to memoize each element in the array. At every index in the array, see if the array contains (target - array[index]).

int[] twoSum(int[] nums, int target) {
    HashMap<Integer, Integer> memo = new HashMap<>();
        
    for (int i = 0; i < nums.length; i++) {
        if (memo.containsKey(target - nums[i]))
            return new int[]{memo.get(target - nums[i]), i};
            
        memo.put(nums[i], i);
    }
        
    return new int[]{-1, -1};    // could not find target
}

This solution is O(n) because of the O(1) insertion and look-up times in Hash Maps. So you visit each element in the array at most once (n time), each time checking the Hash Map for (target - array[index]) (constant time).

Java HashMap equivalents in some other languages:
• C++: Unordered Maps (std::unordered_map, C++ 11)
• Python: Dictionaries (dict)
• JavaScript: Map object

Day: 1
Problem Track: ▶ The Only Living Boy in New York | Simon & Garfunkel