Start learning free

LESSON 239 OF 348 · HASH TABLE

Two Sum in TypeScript: O(n) with a Hash Map

Practice O(n) Read the full explanation

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 will have at most one solution, and you may not use the same index twice.

In case no solution exists, return [-1, -1]

Example:

Input: nums = [2, 7, 11, 15], target = 9
Output: [0, 1]
Explanation: nums[0] + nums[1] = 2 + 7 = 9

Note:

Your algorithm should run in O(n) time and use O(n) space.


Hints:

This the type of problem where we optimize the brute force approach to get the optimal one. The brute force approach took O(n^2) time because we had two nested for loops, one for i and another one j. In order to get O(n), we have to reduce this to only one for loop, so we should fix only one index, let it be j, the index of the second number. We will try out each possible j, and for each of them we should check if there is an index i < j such that nums[i] + nums[j] == target: 
for each j : 0 -> n - 1:
	// We know nums[j]. Find some index i < j such that nums[i] + nums[j] == target.
How can we find that index in O(1)?

nums[i] + nums[j] == target <=> nums[i] == target - nums[j]. So for each j, we should look for an element equal to target - nums[j] from the left of j. Is there a data structure that allows us to look for an element in a collection in constant time? How can we use it here?

That data structure is the Hash Map. We can have a Hash Map where we insert all the elements nums[j] we iterate on during the for loop. In this way, for each j, we can look in the Hash Map to see if there is some element of value target - nums[j] and if so, we found a solution: 
for each j : 0 -> n - 1:
	- Look for target - nums[j] in the Hash Map. If there exists, we found the solution.
	- Otherwise, insert nums[j] into the Hash Map and continue with the for loop.
I know the code above is not perfect. Hash Maps work with pairs (key => value), we cannot just insert a nums[j] into a Hash Map. What should we actually insert in this hash map? What are the keys and what are the values?

The problem with the code above is that we just check if there is an element equal to target - nums[j]. If so, we have a solution, but that's not enough. The problem asks us to return the indices of those elements and we only know of them: j. Can we adapt the solution such that if for some j there is an element equal to target - nums[j], we can also get its index?

The pairs in the Hash Map should be nums[j] => j so that for each element we insert, we can also get its index: 
for each j : 0 -> n - 1:
	if target - nums[j] in indexOfValue:
		return [indexOfValue[target - nums[j]], j]
	indexOfValue[nums[j]] = j
return [-1, -1]

STEP 1 OF 5
    Ctrl + Enter to check

    TYPESCRIPT · HASH TABLE

    Two Sum in TypeScript, explained

    Problem overview

    The method twoSum receives an array of numbers, nums, and a target. It returns the indices of two different positions whose values add up to target, or [-1, -1] when there is no such pair. There is at most one solution, and the same index can't be used twice, although two equal values at different indices are fine.

    In the example, nums = [2, 7, 11, 15] and target = 9. The values 2 and 7, at indices 0 and 1, add up to 9.

    This time the statement asks for O(n) time and O(n) space.

    Approach: remember what you have seen

    The brute-force solution tries every pair of indices with two nested loops, which is O(n²). Sorting plus two pointers brings it to O(n log n). A hash map brings it down to a single pass.

    The key is the complement. If the current element is nums[i], its partner must be exactly target - nums[i]. Treat nums[i] as the second element of the pair, so the partner must already have been seen at an earlier index. Looking up whether a value has been seen is exactly what a hash map does in constant time.

    A set of seen values would answer yes or no, but the task wants the partner's index. So the map stores each value together with its index: value → index. For each element:

    1. Look up target - nums[i] in the map. If it is there, the pair is the stored index and i.
    2. Otherwise store nums[i] with index i and move on.

    On [2, 7, 11, 15] with target 9: at index 0 the complement is 7, which isn't stored yet, so 2 is stored. At index 1 the complement is 2, which is stored with index 0, so the method returns a pair made of 1 and 0.

    Step by step

    1. Create the map. Declare indexOfValue with const as an empty object typed { [key: number]: number }, an index signature from numbers to numbers. const only fixes the variable, so entries can still be added.
    2. Loop over the array with an index i from 0 to nums.length - 1. Each nums[i] is tried as the second element of the pair.
    3. Check for the partner. Test whether target - nums[i] is a key of indexOfValue with the in operator. If it is, it appeared to the left of i, so return i together with the stored index, read with square brackets.
    4. Store the current element. After the if, still inside the loop, set indexOfValue[nums[i]] = i. Doing this after the check means an element can't be paired with itself.
    5. Return [-1, -1] after the loop, for the case where no pair was found.

    The solution in TypeScript

    class Solution {
    twoSum(nums: number[], target: number): number[] {
        const indexOfValue: { [key: number]: number } = {};
        for (let i = 0; i < nums.length; i++) {
            if (target - nums[i] in indexOfValue) {
                return [i, indexOfValue[target - nums[i]]];
            }
            indexOfValue[nums[i]] = i;
        }
        return [-1, -1];
    }
}

    The TypeScript details worth a closer look:

    • An object as a hash map. The type { [key: number]: number } describes an object whose number keys map to number values. It exists only at compile time. At run time the object is a plain JavaScript object, empty until entries are added.
    • Keys are strings underneath. JavaScript converts the number 7 to the string "7" when it is used as a key. Reading, writing and in all apply the same conversion, so negative numbers and zero work too.
    • The in operator tests whether a key exists, even if its stored value is 0. That matters here, because index 0 is a legitimate stored value. A check like if (indexOfValue[x]) would treat index 0 as "not found".
    • Precedence. In target - nums[i] in indexOfValue, the subtraction is evaluated first, so the left side of in is the complement.
    • The return order. The method returns the current index first and the earlier index second. For the example it returns [1, 0]: the same two positions as [0, 1], in the opposite order.
    • Overwriting entries. When a value occurs twice, the second store replaces the first index. This is safe, because if the duplicate were part of a solution (for example [3, 3] with target 6), the pair would already have been found before the overwrite.

    Complexity

    Time: O(n). The loop visits each element once, and each in test, read and write on the object takes constant time on average.

    Space: O(n). In the worst case, when no pair exists, the object stores every element.

    Edge cases and common mistakes

    • Same element twice. [3, 4] with target 6 gives [-1, -1]. The 3 is stored only after the check, so it is never its own partner.
    • Duplicates that form the answer. [3, 3] with target 6 gives [1, 0]. The first 3 is stored, and the second finds it.
    • Zero and negatives. [0, 4, 0] with target 0 gives [2, 0], and [-1, -2, -3] with target -5 gives [2, 1].
    • Short input. An empty array, or an array with a single element, has no pair, so the loop ends without a match and the method returns [-1, -1].
    • Storing before checking. Putting indexOfValue[nums[i]] = i above the if lets an element match itself, for example 3 with target 6.
    • Testing the stored index for truthiness. Index 0 is falsy, so a partner at position 0 would be missed. The in operator avoids this.
    • Storing the index as the key. The map must go from value to index, because the lookup starts from the complement value.

    Testing

    • nums = [2, 7, 11, 15], target = 9 gives [1, 0].
    • nums = [3, 2, 4], target = 6 gives [2, 1].
    • nums = [3, 3], target = 6 gives [1, 0].
    • nums = [3, 4], target = 6 gives [-1, -1].
    • nums = [1, 2, 3], target = 100 gives [-1, -1].
    Keep going with TypeScriptAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free