LESSON 238 OF 347 · HASH TABLE

Two Sum in C#: 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 C#, explained

Problem overview

The method TwoSum receives an int[] nums and an int target. It must return the indices of two numbers in the array that add up to target, as an int[] of length 2. There is at most one solution, the same index can't be used twice, and when nothing matches the method returns [-1, -1].

For nums = [2, 7, 11, 15] and target = 9, the numbers 2 and 7 at indices 0 and 1 add up to 9. This version builds its answer as the later index followed by the earlier one, so it returns [1, 0], which names the same two positions. The statement asks for O(n) time and O(n) space.

Approach: remember what you have seen

The brute force tries every pair of indices with two nested loops, which is O(n²). To get to O(n) you can afford only one loop, so the search for the partner must take constant time.

Fix the current index i and treat nums[i] as the second number of the pair. Its partner must equal target - nums[i], and it must sit to the left of i, because the loop has not reached anything to the right yet. A hash table can answer "have I seen this value, and where?" in constant time on average. So keep a dictionary indexOfValue from each value seen so far to its index:

If target - nums[i] is a key, the partner's index is the stored value, and the pair is complete.
Otherwise, record nums[i] with its index and move on.

Every pair is found when the loop reaches its right member, so one pass is enough. For the example, at i = 0 the needed partner is 7, which is not stored, so 2 is recorded. At i = 1 the needed partner is 2, which is stored at index 0, so the method returns indices 1 and 0.

Step by step

Create the dictionary. indexOfValue is a Dictionary<int, int> that maps a number to the index where it was seen.
Loop over every index. A for loop runs i from 0 to nums.Length - 1. Each nums[i] is tried as the second element of the pair.
Look for the complement. ContainsKey(target - nums[i]) says whether the partner appeared earlier. If it did, return a new array holding i and the index stored under that key. The check comes before the read because indexing a missing key would throw.
Record the current number. After the check, assign indexOfValue[nums[i]] = i. The indexer adds the key or overwrites an old value. Because this happens after the check, an element is never paired with itself.
Report failure. If the loop ends without returning, no pair adds up to the target, so return {-1, -1}.

The solution in C#

class Solution {
    public int[] TwoSum(int[] nums, int target) {
        Dictionary<int, int> indexOfValue = new Dictionary<int, int>();
        for (int i = 0; i < nums.Length; ++i) {
            if (indexOfValue.ContainsKey(target - nums[i])) {
                return new int[]{i, indexOfValue[target - nums[i]]};
            }
            indexOfValue[nums[i]] = i;
        }
        return new int[]{-1, -1};
    }
}

Some C# details:

Returning an array. new int[]{i, j} creates an array with those two elements. Arrays have a fixed length, which suits a pair.
The indexer throws on missing keys. indexOfValue[x] is safe here only because ContainsKey was true just before. TryGetValue would do the check and the read in a single lookup.
Overwriting duplicates. If a number appears twice, indexOfValue[nums[i]] = i replaces the earlier index with the later one. Either index is a valid partner, since the values are equal, and the method returns as soon as a match appears.
int arithmetic wraps silently. target - nums[i] does not throw when the result is outside the int range, it wraps around. The values in this lesson are small, so this does not arise.

Complexity

Time: O(n). The loop runs at most n times, and each iteration does a fixed number of dictionary operations, each O(1) on average.

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

Edge cases and common mistakes

Equal values. For [3, 3] and target 6, the first 3 is recorded at index 0, and at i = 1 the complement 3 is found. The method returns [1, 0].
Pairing an element with itself. For [3, 4] and target 6, the answer is [-1, -1]. Recording nums[i] before checking would let the first 3 match itself.
No solution or empty input. For an empty array the loop never runs and the method returns [-1, -1].
Negative numbers and zero. The method works unchanged: for [-3, 4, 3, 90] and target 0, the result is [2, 0].
Index order. This version always puts the later index first, as in the [1, 0] for the example. Returning [indexOfValue[...], i] would give the earlier index first instead.
Reading before checking. Using the indexer without ContainsKey or TryGetValue throws KeyNotFoundException on the first miss.
Overflow at the extremes. Because int subtraction wraps, a target near int.MinValue combined with a number near int.MaxValue can produce a match that does not add up mathematically. For example, [int.MaxValue, 1] with int.MinValue returns [1, 0]. Do the arithmetic in long if such inputs are possible.

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

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

Start learning free