Burak Dede's Blog

Two Sum Problem - Leetcode

Problem

This is my approach to the solution of two sum problem from Leetcode. https://leetcode.com/problems/two-sum/description/

Solution #1 - No extra memory

If we can not use extra memory first solution would be for each element in the array find complement (which is target - current element) and check if complement exist in the array.

This would take be O(N^2) time and O(1) space complexity.

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

Solution #2 - Extra memory with hashmap

Brute force approach may not be the best solution when we need lower bound than O(N^2). Better to ask if we are allowed to use extra memory. If we can quickly lookup for the complement element, we can easily decrease the time complexity to linear time.

public static int[] twoSumFast(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();
    int[] indices = new int[2];
    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i];
        if (map.containsKey(complement)) {
            indices[0] = map.get(complement);
            indices[1] = i;
            return indices;
        }
        map.put(nums[i], i);
    }
    return indices;
}

Time complexity for this approach is O(n) and space complexity is O(n) (probably stop when we found complement but at worst case this will be the all elements - case when first and last element will be the complement).

Sorting would be another way but we need indices of elements so sorting would break that requirement.

Submitted both and looked like they both passes the test cases.