LESSON 263 OF 415 · HASH TABLE

Two Sum in Swift: O(n) with a Dictionary

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

Guided

Ctrl + Enter to check

Two Sum in Swift, explained

Problem overview

The method twoSum receives an array of integers, nums, and a target. It must return 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 at indices 0 and 1 are 2 and 7, and 2 + 7 = 9, so those are the two positions to report.

The statement asks for O(n) time and O(n) extra space. That rules out trying every pair of indices.

Approach: remember what you have seen

The brute-force solution uses two nested loops, one for each index of the pair, and costs O(n²). The faster idea comes from rewriting the condition. If nums[i] + nums[j] == target, then nums[i] == target - nums[j]. Once you fix the second element, its partner is a specific, known value.

So the loop fixes only the later index of the pair. For each element it asks one question: has the value target - nums[i] already appeared to the left? A dictionary answers that in constant time on average. The keys are the values seen so far, and each key maps to the index where that value was found. The index is the reason a plain set isn't enough: the answer needs positions, not just a yes or no.

Because the loop checks the dictionary before it stores the current element, an element can never be matched with itself. Every pair of positions has a later member, so the pair is found when the loop reaches that member.

Step by step

Declare the dictionary. indexOfValue is an empty [Int: Int] declared with var, because entries are added while the loop runs.
Loop over the indices with for i in 0..<nums.count. Each nums[i] is treated as the second element of a possible pair.
Look up the partner. Subscripting a dictionary returns an optional, nil when the key is missing. if let j = indexOfValue[target - nums[i]] runs its block only when the partner was seen, and binds its index to j. Inside, return [i, j].
Store the current element with indexOfValue[nums[i]] = i, after the check. Doing it afterwards is what prevents an element from pairing with itself.
Return [-1, -1] after the loop. Reaching that line means every element was tried and none had a partner on its left.

The solution in Swift

class Solution {
    func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
        var indexOfValue = [Int: Int]()
        for i in 0..<nums.count {
            if let j = indexOfValue[target - nums[i]] {
                return [i, j]
            }
            indexOfValue[nums[i]] = i
        }
        return [-1, -1]
    }
}

Swift details worth a closer look:

The result order. The method returns [i, j]: the current, later index first, then the earlier one. For the example it returns [1, 0], which names the same two positions as [0, 1].
Optionals. indexOfValue[key] has the type Int?. Swift won't let you use it as an Int until you unwrap it, and if let does that safely, so a missing key can't crash the program.
Dictionary literal. [Int: Int]() creates an empty dictionary. The same type can be written Dictionary<Int, Int>().
Value semantics. The dictionary is a value type, which is why it must be var: adding an entry changes it.
Ranges. 0..<nums.count excludes the upper bound, so i stops at the last valid index. For an empty array the range is empty and the loop body never runs.

Complexity

Time: O(n). The loop runs at most n times, and each lookup and insertion into the dictionary takes constant time on average.

Space: O(n). In the worst case, when no pair exists, the dictionary stores one entry per element.

Edge cases and common mistakes

Same value twice. [3, 3] with target 6 returns [1, 0]. The first 3 is stored, and the second finds it. If the dictionary were filled completely before the loop, the second 3 would overwrite the first and an element could match itself.
Pairing with itself. [3, 4] with target 6 returns [-1, -1]. The 3 is never compared with itself because it is stored only after its own lookup.
Empty array. [] returns [-1, -1], since the loop doesn't run.
Negative values. Nothing changes: the dictionary treats -2 as any other key.
Overflow. Int is 64 bits, so ordinary inputs are safe. But arithmetic that overflows traps at run time and crashes the program; it doesn't wrap. With values near Int.max or Int.min, the subtraction target - nums[i] can trap.
Force-unwrapping the lookup. Writing indexOfValue[target - nums[i]]! crashes whenever the partner hasn't been seen. Use if let.

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 = [], target = 5 gives [-1, -1].

Keep going with SwiftAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free