Two Sum: Easy

Problem

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example

Given nums = [2, 7, 11, 15], target = 18,

Because nums[1] + nums[2] = 7 + 11 = 18,
return [1, 2].

Conceptual Overview

Before we get to the solution lets think about this conceptually. Looking at the array from our example we would need to find the pair of indices that add up to 18.

Possible Solution #1

One way of finding the indices would be to iterate through the array with two for-loops. Create a for-loop that will traverse the array and nest a second for-loop that will traverse the rest of the array at an index of +1 to the first loop.

Time & Space Complexity

O(n^2) Time & O(1) | Two for loops with a constant lookup

Possible Solution #2

A solution that is faster but will require more space will be making use of hash tables or more simply using an object.

When we use a hash table to store values we have access to constant lookup which makes this solution much quicker than the first. So as we iterate through the array we will be checking the hash table to see if it has the value we are looking for that adds up to target. Let's write some arithmetic

X1 + X2 = target
Where:
target = 18
X1 = current value in for-loop
Find X2
X2 = target - X1

So as we loop through the array we are storing values to the hash table and checking to see if X2 exists in the has table. If X2 exists then we return indices of [X1, X2]

Time & Space Complexity

O(n) Time & O(n) Space | One for-loop and storing data to a hash table iterating through the array once

Solutions

Solution #1 O(n^2) Time & O(1) Space

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
let twoSum = (nums, target) => {
    for (let i = 0; i < nums.length; i++) {
        for (let j = i + 1; j < nums.length; j++) {
            if (nums[i] + nums[j] === target) return [i, j]
        }
    }

    return []
}

Solution #2 O(n) Time & O(n) Space

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
let twoSum = (nums, target) => {
    const hash = {}

    for (let i = 0; i < nums.length; i++) {
        if (hash[target - nums[i]] !== undefined) {
            return [hash[target - nums[i]], i]
        }

        hash[nums[i]] = i
    }

    return []
}

And there you have it! A couple of solutions for Two Sum. I would love to see what solutions you all came up with. See you all in the discussions :D