Two Sum

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

Problem Link : https://leetcode.com/problems/two-sum

• A naive solution would be to have two for loops and then loop over the array and check if arr[i]+arr[j] == target.

• Solution in Java: https://leetcode.com/problems/two-sum/submissions/1207732956/

Time complexity : O(n) Space Complexity : O(n)

class Solution {
    public int[] twoSum(int[] nums, int target) {
        //Stores value, index
        Map<Integer,Integer> indexMap = new HashMap<>();
        for(int idx=0;idx<nums.length;idx++)
        {
            int compliment = target - nums[idx];
            if(indexMap.containsKey(compliment)) return new int[]{indexMap.get(compliment),idx};

            indexMap.put(nums[idx],idx);
        }
        return new int[] {};
    }
}

• If we have to return the elements themselves (Python solution):

def twoNumberSum(array, targetSum):
    # Write your code here.
    result = set([])
    for item in array:
        temp = targetSum - item
        if temp in array and temp != item:
            result.add(temp)
            result.add(item)
    return list(result)

Time complexity : O(n) Space Complexity : O(n)