LeetCode 1. Two Sums

If you prefer a visual explanation, please check out my video here, although bare in mind this is the first video I’ve recorded so the mic settings weren’t great so it might be easier for you to read the solution here.

TLDR

Source code for my O(N) TypeScript solution using a hashmap

The problem

We have two params, an array of numbers and a target.

The goal here is to find which two numbers in the array sum up to the target and output their indexes.

An example here:

let nums = [2, 7, 13, 5, 8, 11, 1, 4];
let target = 10;

// Output [0, 4]
nums[0] + nums[4] === 10 // 2 + 8 = 10

Brute force solution

The easiest way to solve this would be to loop through our nums array and for every number, check if that number + any other number in the array matches our target.

Here’s a draw up of our algorithm

If it does, return the two indexes that made up our sum.

function twoSum(nums: number[], target: number): number[] {
    for (let i = 0; i < nums.length; i++) {
        for (let j = 0; j < nums.length; j++) {
            // Can't use the same idx twice
            if (i === j) {
                continue
            }
            if (nums[i] + nums[j] === target) {
                return [i, j];
            }
        }
    }
};

Efficiency

This solution runs in O(N^2) as it runs through our input twice.

Hash Table Solution

We can store the result of each sum in a hash table and check if the hash table includes the sum of the current array number in our iteration - the target.

If it is, that means we can reach the target with the number in our hash table and the current number we’re iterating through.

A draw up of the solution

function twoSum(nums: number[], target: number): number[] {
    const sumResults = {}; // Our hash table
    for (let i = 0; i < nums.length; i++) {
        let tempSum = target - nums[i];
        if (sumResults.hasOwnProperty(target - tempSum)) {
            return [sumResults[target - tempSum], i]
        }
        sumResults[tempSum] = i;
    }

};

Efficiency

This solution will run in O(N) time complexity as we only iterate through our number’s array once. It does also have an O(N) space complexity too as we’re creating a hash table that can in the worst case store our entire input too

Thanks for reading!

Feel free to checkout some of my most recent posts

LeetCode 1. Two Sums

A TypeScript solution to the Two Sums problem, an efficient algorithm using a hashmap that runs in O(N) time

April 26 2024

Surviving the Redundancy: My Journey of Reclaiming My Job

The company I used to work for was a tiny family-run business based in the middle of nowhere in the British countryside. It was a great operation where everyone made a real impact....

January 24 2024

The 1,000 most common Indonesian Words

A collection of the top 1,000 most used Indonesian words and phrases to help boost your language learning

August 28 2022

Or navigate back to the rest of the posts