Juan Alvarez

I wanted to dust off two of my beloved hobbies: programming and blogging. I found a good way to do so by working through some of the most interesting problems on LeetCode and publishing my solutions on my personal blog.

The first interesting exercise is Two Sum. One of the easiest and introductory problems in the DSA (Data Structures and Algorithms) world. The prompt is simple:

You are 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].

This problem is interesting because it has two usual solutions with different time complexities: O(n^2) and O(n). First, let's look at the "brute force" solution.

Forcing a solution - O(n^2)

To find a solution, we can define a clear answer: `target = head + neededValue`. Thanks to it, we can create a quick assumption: let's iterate each item in the array, make that item the head, and then evaluate the equation to "brute force" the solution.

function twoSum(nums: number[], target: number): number[] {
    const maxLen = nums.length - 1
    for (let i = 0; i <= maxLen; i++) {
        const head = nums[i];
        for (let j = i + 1; j <= maxLen; j++) {
            const tail = nums[j]
            if (head + tail === target) return [i, j]
        }
    }
};

Why is it O(n^2)? Simple: to get the value we are looking for, in the worst case, we potentially look through the rest of the array for each element in the array. This makes the time required to go through a huge array very slow. The solution seems simple and elegant (and for most cases, you can stop here). However, there is a nicer and simpler way to approach this problem thanks to a different Data Structure.

Bringing the big guns: a Map

A Map is a data structure that saves key-value pairs. Why are Maps so useful for this scenario? Well, they share a particularity with native JS objects: constant-time lookup. This allows us to create a new condition where we can use a unique loop to find the answer.

Let's get back to our formula: `target = head + neededValue`. If we have our target (provided by the function definition) and our head (the i element in the loop), we only need to find the neededValue. Before, we needed to check the remaining items in the array. Thanks to the map, we can store the array's items (and their indices) to verify IF we have already encountered a value that fulfills this condition.

function twoSum(nums: number[], target: number): number[] {
    const maxLen = nums.length - 1
    const lookup = new Map()

    for (let i = 0; i <= maxLen; i++) {
        const head = nums[i]
        const nextTarget = target - head

        if (lookup.has(nextTarget)) return [lookup.get(nextTarget), i]
        else lookup.set(head, i)
    }
};

In common words, we are saying: for this particular head (nums[i]), is there an item in the array that we have already seen that fulfills the target when we sum them? If yes, there is your answer. Else, add this head to the lookup table for the next head to compare to.

This is O(n) because the worst-case scenario is evaluating the end of the array. It's a better, trickier solution to a simple problem: Two Sum.

I hope you found this interesting. This blog is part of a new series. I'll cover more LeetCode exercises and their solution with my spin on writing.

Next up: Valid Anagram.