1. Two Sum

 Two Sum

Problem Description

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

 

Follow-up: Can you come up with an algorithm that is less than O(n2) time complexity?

Approach 1) Brute Force

Idea:

• nums are the array of numbers and the target is the desired solution.
• I iterate over both arrays and check if the sum is the necessary value.
• However, as stated in the prompt, we should not use the same element twice.

Let`s Code It!

var twoSum = function(nums, target) {
    for (let i = 0; i < nums.length; i++) {
        for (let j = i + 1; j < nums.length; j++) {
            if (i == j)  continue;
            if (nums[i] + nums[j] == target) {
                return [i, j]
            }
        }
    }
};

So we can check if the iterations are on the same element and skip

if (i == j)  continue;

Approach 2: Two-pass Hash Table (JS object)

A much better solution would be searching for the target based on the current number. What does that mean?

For example, when you first start iterating over the array you know the exact number you’re looking for. The number you're looking for is the result of the subtraction of the target and the current iterated value.

Let's take our first array as an example.

first iteration

When we're on the first element 2 we know that we need to find 9 minus 2 is 7. But, we need a way to quickly re-access data of the array.

var twoSum = function(nums, target) {
    const indices = {};

    nums.forEach((item, index) => {
        indices[item] = index
    });

    for (let index = 0; index < nums.length; index++) {
        const complement = target - nums[index];

        if (indices[complement] !== undefined && indices[complement] !== index) {
            return [index, indices[complement]]
        }
    }
};

We now have a simplified way to check for previous values.
Going back to the code we first do a single iteration of the loop.
By subtracting the target value from the current index value num we can check if the remainder already exists.
If it doesn’t we just add the value we just tried to the map and move on.

So to reiterate

We loop over the array

We check if our current map of values has the subtraction of our target and the current value we are iterating over. If it does we return both the index of the current value and the index of the value in our map

If we don’t find a match we add it to our map and move on

Approach 3: One-pass Hash Table

var twoSum = function(nums, target) {
    const indices = new Map();

    for (let index = 0; index < nums.length; index++) {
        const complement = target - nums[index];

        if (indices.has(complement)) {
            return [indices.get(complement), index]
        }

        indices.set(nums[index], index)
    }
};

Conclusion

That’s all folks! In this post, we solved LeetCode problem #1. Two Sum

I hope you have enjoyed this post. Feel free to share your thoughts on this.

You can find the complete source code on my GitHub repository. If you like what you learn. feel free to fork 🔪 and star ⭐ it.

In this blog, I have tried to solve leetcode questions & present the most important points to consider when improving Data structure and logic,  feel free to add, edit, comment, or ask. For more information please reach me here
Happy coding!