How to Solve the Two Sum Problem in Go
The Two Sum problem is a classic algorithmic challenge that frequently appears in coding interviews. The problem is simple: given an array of integers and a target sum, determine if there are two numbers in the array that add up to the target. If such numbers exist, return their indices; otherwise, return nil
.
In this post, we will explain how to solve the Two Sum problem in Go by covering several approaches and discussing their time and space complexities.
Problem Statement
You are given an array of integers nums
and an integer target
. Return the indices of the two numbers such that they add up to target
.
Example:
Input: nums = [2, 7, 11, 15], target = 9
Output: [0, 1]
Explanation: nums[0] + nums[1] = 2 + 7 = 9
Approach 1: Brute Force Solution
The simplest way to solve this problem is to check each pair of numbers in the array and see if they sum up to the target. This involves a nested loop where each element is paired with every other element.
Algorithm:
- Loop through each element in the array.
- For each element, loop through the remaining elements.
- If the sum of two elements equals the target, return their indices.
Code:
package main
import "fmt"
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
}
func main() {
nums := []int{2, 7, 11, 15}
target := 9
result := twoSum(nums, target)
fmt.Println(result) // Output: [0, 1]
}
Time Complexity:
- O(n²): For each element
i
, we loop over the remaining elementsj
, which results in quadratic time complexity. - Space Complexity: O(1), as we are not using any additional space.
Approach 2: Using a Hash Map (Optimal Solution)
The brute-force solution is inefficient for large arrays. We can improve the time complexity using a hash map (Go’s map
data structure), which allows us to check for the complement of each number in constant time.
Algorithm:
- Create a hash map (dictionary) to store each element's value and its index.
- Loop through the array, and for each element, compute the complement as
target - nums[i]
. - Check if the complement already exists in the hash map.
- If it exists, return the index of the current element and the index of the complement.
- If it does not exist, add the current element to the hash map.
Code:
package main
import "fmt"
func twoSum(nums []int, target int) []int {
// Create a hash map to store the numbers and their indices
numMap := make(map[int]int)
for i, num := range nums {
complement := target - num
// Check if the complement exists in the map
if index, found := numMap[complement]; found {
return []int{index, i}
}
// Otherwise, add the number to the map
numMap[num] = i
}
return nil
}
func main() {
nums := []int{2, 7, 11, 15}
target := 9
result := twoSum(nums, target)
fmt.Println(result) // Output: [0, 1]
}
Explanation:
- As we loop through the array, we check whether the complement of the current number (i.e.,
target - num
) exists in the hash map. - If it exists, it means that we have found two numbers that add up to the target, so we return their indices.
- If not, we store the current number and its index in the hash map and continue.
Time Complexity:
- O(n): We only loop through the array once, and each lookup or insertion in the hash map takes O(1) time.
- Space Complexity: O(n), where
n
is the number of elements in the array, due to the space required to store the hash map.
Edge Cases
While the problem guarantees exactly one solution, you should still account for various edge cases during implementation:
-
Negative and Positive Numbers:
The array may contain both negative and positive numbers. Ensure that the solution works for both.nums := []int{-3, 4, 3, 90} target := 0 result := twoSum(nums, target) fmt.Println(result) // Output: [0, 2]
-
Duplicate Values:
The array may contain duplicate values, and the solution should still return the correct indices.nums := []int{3, 3} target := 6 result := twoSum(nums, target) fmt.Println(result) // Output: [0, 1]
-
Array with Only Two Elements:
Since the problem guarantees at least two elements, the array can have exactly two elements, and the solution should still work.nums := []int{1, 4} target := 5 result := twoSum(nums, target) fmt.Println(result) // Output: [0, 1]
-
Zeros in the Array:
If the array contains zeros, the solution should correctly handle the target involving zero.nums := []int{0, 4, 3, 0} target := 0 result := twoSum(nums, target) fmt.Println(result) // Output: [0, 3]
-
Large Inputs:
If the array contains a large number of elements, the hash map approach ensures efficiency even with significant data size.nums := make([]int, 100000) for i := 0; i < 100000; i++ { nums[i] = i } target := 199999 result := twoSum(nums, target) fmt.Println(result) // Output: [99998, 99999]
Testing the Solution
To ensure that your solution works correctly, test it with various input arrays and targets.
func main() {
// Test case 1: Normal case
fmt.Println(twoSum([]int{2, 7, 11, 15}, 9)) // Output: [0, 1]
// Test case 2: No valid pair
fmt.Println(twoSum([]int{1, 2, 3}, 10)) // Output: nil
// Test case 3: Same element twice
fmt.Println(twoSum([]int{3, 3}, 6)) // Output: [0, 1]
// Test case 4: Multiple pairs
fmt.Println(twoSum([]int{3, 2, 4}, 6)) // Output: [1, 2]
// Test case 5: Larger array
fmt.Println(twoSum([]int{1, 4, 5, 8, 12, 19, 21}, 20)) // Output: [2, 3]
}
Conclusion
The Two Sum problem is a great way to practice basic algorithmic thinking and improve your understanding of hash maps in Go. The brute-force solution is simple but inefficient for large inputs, while the hash map solution optimizes the time complexity to O(n) by trading time for space.
With the optimal hash map solution, we can efficiently solve the Two Sum problem in linear time, making it suitable for large datasets. Understanding these different approaches prepares you for similar algorithmic challenges in Go.