LeetCode | 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]
Output: 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 <= 103
• -109 <= nums[i] <= 109
• -109 <= target <= 109
• Only one valid answer exists.

Solution

Points to Think and Clarify:-

1. Will array be sorted - if yes, we can use the two-pointer approach and achieve a Time Complexity of O(n) & Space Complexity of O(1).
2. Will there be duplicate items in the array - if yes we need to make sure that we don't consider the same index twice.

Approaches:-

1. Brute Force - loop through all the items in the array for each item in the array and check if the target sum is met. Time Complexity O(n^2) & Space Complexity O(1).
2. Better - Sort the array and use a two-pointer approach, one on the first/left/smallest element and one on the last/right/largest element. if the sum is equal to the target return both the index, if the sum is more than target then move the right pointer to the left by 1 index and if it is less than the target then move the left pointer to the right by 1 index and continue this process until you find a sum that matches the target. Time Complexity O(nlog(n)) & Space Complexity O(n).
3. Optimal - loop through the array for each item save the (target - item) in the hashMap as a key along with index as value. now loop again through the array and see if the current item value is present in the hashMap or not if yes return the current index and the index saved in the hashMap for that item value. Also, make sure that the index that you get from the hashMap is different from the current index. Time Complexity O(n) & Space Complexity O(n).

Code:-

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    const hashMap = new Map();

    // setting the hashMap with (target - currentIndexData) and the index
    for (let i = 0; i < nums.length; i++) {
        hashMap.set(target - nums[i], i);
    }

    // search if the value exists in the hashMap and check if its on a differnt index 
    for (let i = 0; i < nums.length; i++) {
        if (hashMap.has(nums[i]) && hashMap.get(nums[i]) !== i) {
            return [hashMap.get(nums[i]), i];
        }
    }

    return [];
};