Two Sum Leetcode problem using Typescript

Question

I've recently gotten into Typescript and I'm solving some Leetcodes to learn.

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.

Constraints:

• 2 <= nums.length <= 104
• \$-10^9\$ <= nums[i] <= \$10^9\$
• \$-10^9\$ <= target <= \$10^9\$
• Only one valid answer exists.

I wrote this:

function twoSum(nums: number[], target: number): number[] {

    let map: Entry[] = [];
    
    type Entry = {
        readonly index: number, 
        readonly value: number, 
    }; 

    let result: number[] = []; 
    let test: any = nums.map((elem, index) => {
        let map_search = map.find((entry) => entry.value === target - elem); 
        if(map_search) {
            // contains suitable index
            result.push(index, map_search.index);
        } else {
            let new_entry: Entry = {
                index: index, 
                value: elem, 
            };
            map.push(new_entry);
        }
    })
    
    if(result) {
        return result;
    } else {
        return [];
    }
};

My solution works, but it feels a bit messy and inefficient in places. I feel like I'm not doing things in the proper Typescript way. Are there any suggestions for improvement?

Answer 1

I'll start with the simple ones.

Use const instead of let when possible. It prevent accidental overwrites and it also better comunicates the intent. In fact, in your code, const is suitable in every single instance.

The test variable is unused and in fact, you should not call map at all if you're not mapping the array. You just wanna "forEach" the array or simply loop it using for.

Avoid using any type unless really necesary and it should stand for "any type is suitable here". If you just don't know what the type, better to use unknown.

Since result can only be Array, asking if (result) is meaningless because it will always be true.

No need to write semicolons in ts/js. At least you're consistent in using them, but it's very easy to go inconsistent without noticing. Most professionals probably use a linter configured to disallow them.

I would also change the return type if nothing is found to null rather then empty array and actually instead of number[] your can return [number, number] since it will always have two elements. If we were not constrained to exactly one solution, it would make sense to return [number,number][] and then empty array for "not found any solution" would fit.

Now for the performance. Time complexity of your solution is O(n^2).

From specification

each input would have exactly one solution

We can return as soon as we find it.

We can also infer that each element of nums array is unique. And so we can construct an inverted map and use it to better the algorithm time complexity into O(n). However we sacrficice O(n) extra memory for the Map (although your solution does that too).

function twoSum(nums: number[], target: number): [number, number] | null {
    const visitedIndicesByValue = new Map<number, number>()

    for (let i = 0; i < nums.length; ++i) {
        const diff = target - nums[i]
        if (visitedIndicesByValue.has(diff)) {
           return [visitedIndicesByValue.get(diff), i]
        } else {
           visitedIndicesByValue.set(nums[i], i)
        }
    }

    return null
}