Two Sum: From Brute Force to a Hash Map
Improve Two Sum from nested loops to a single pass using a dictionary, with C#, Go, and Python 3 examples.
- Algorithms
- Hash Maps
Problem
Given an array of integers nums and an integer target, return the indexes of two numbers whose sum equals target.
Each input has exactly one solution. You cannot use the same element twice, and you can return the indexes in any order.
Example 1
Input: nums = [2, 10, 6, 18], target = 8
Output: [0, 2]Because nums[0] + nums[2] == 8, we return [0, 2].
Example 2
Input: nums = [3, 5, 4], target = 9
Output: [1, 2]Example 3
Input: nums = [4, 4], target = 8
Output: [0, 1]Solution
Brute force
You can solve this with brute force using two nested loops. For each number, check the numbers after it until you find a pair that adds up to the target. This takes O(n²) time and O(1) extra space.
using System;
public static class Solution
{
public static int[] TwoSum(int[] nums, int target)
{
for (int i = 0; i < nums.Length; i++)
{
for (int j = i + 1; j < nums.Length; j++)
{
if (nums[i] + nums[j] == target)
return new[] { i, j };
}
}
return Array.Empty<int>();
}
}func TwoSum(nums []int, target int) []int {
for i := 0; i < len(nums); i++ {
for j := i + 1; j < len(nums); j++ {
if nums[i]+nums[j] == target {
return []int{i, j}
}
}
}
return nil
}def two_sum(nums: list[int], target: int) -> list[int]:
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
if nums[i] + nums[j] == target:
return [i, j]
return []First improvement: two passes
Key idea
Why we decided to use HashMap here to improve? Because once you choose a number, its partner must be target - number. A hash map turns finding that exact partner into a lookup instead of another scan.
Look up the missing partner before storing the current number, then return both indexes.
A dictionary (hash map) lets you look up the complement in O(1) time on average. Store each number with its index, because we need to return indexes; a hash set alone is not enough.
In the first loop, store each number and its index in the dictionary. In the second loop, look for each number’s complement. Before returning a pair, check that the stored index is different from the current index so you do not reuse the same element.
using System;
using System.Collections.Generic;
public static class Solution
{
public static int[] TwoSum(int[] nums, int target)
{
var indexes = new Dictionary<int, int>();
for (int i = 0; i < nums.Length; i++)
indexes[nums[i]] = i;
for (int i = 0; i < nums.Length; i++)
{
int complement = target - nums[i];
if (indexes.TryGetValue(complement, out int otherIndex) && otherIndex != i)
return new[] { i, otherIndex };
}
return Array.Empty<int>();
}
}func TwoSum(nums []int, target int) []int {
indexes := make(map[int]int)
for i, number := range nums {
indexes[number] = i
}
for i, number := range nums {
complement := target - number
if otherIndex, found := indexes[complement]; found && otherIndex != i {
return []int{i, otherIndex}
}
}
return nil
}def two_sum(nums: list[int], target: int) -> list[int]:
indexes = {}
for i, number in enumerate(nums):
indexes[number] = i
for i, number in enumerate(nums):
complement = target - number
if complement in indexes and indexes[complement] != i:
return [i, indexes[complement]]
return []This takes O(n) time on average and O(n) extra space.
One pass
You can combine these steps into one loop. Check whether the complement is already in the dictionary. If it is, return both indexes. Otherwise, store the current number and its index, then continue.
Check before inserting the current number. This prevents using the same element twice and still handles duplicates such as [4, 4]: the second 4 finds the first one.
using System;
using System.Collections.Generic;
public static class Solution
{
public static int[] TwoSum(int[] nums, int target)
{
var seen = new Dictionary<int, int>();
for (int i = 0; i < nums.Length; i++)
{
int complement = target - nums[i];
if (seen.TryGetValue(complement, out int previousIndex))
return new[] { previousIndex, i };
seen[nums[i]] = i;
}
return Array.Empty<int>();
}
}func TwoSum(nums []int, target int) []int {
seen := make(map[int]int)
for i, number := range nums {
complement := target - number
if previousIndex, found := seen[complement]; found {
return []int{previousIndex, i}
}
seen[number] = i
}
return nil
}def two_sum(nums: list[int], target: int) -> list[int]:
seen = {}
for i, number in enumerate(nums):
complement = target - number
if complement in seen:
return [seen[complement], i]
seen[number] = i
return []The complexity is still O(n) time on average and O(n) extra space, but we only traverse the array once.
Up next
Data Structures & Algorithms · Problem Solving
Number of Islands: Exploring a Grid with Depth-First Search
Count connected regions of land with iterative depth-first search, track visited cells, and implement Number of Islands in C#, Go, and Python 3.
- Graphs
- Depth-First Search
- Grids
Data Structures & Algorithms · Problem Solving
Reverse Integer: Reversing Digits Without Overflow
Reverse a signed integer one digit at a time, detect 32-bit overflow before it happens, and handle negative numbers in C#, Go, and Python 3.
- Integers
- Overflow
- Problem Solving
Comments
No comments yet
Log in to join the conversation. Members comment with a username; your email is never shown. Read the community rules.