LeetCode Two Sum Problem Solution in C++ and Go

Problem Overview

The Two Sum problem on LeetCode is one of the most popular beginner-friendly problems. It asks us to find two distinct indices in an array such that the numbers at those indices add up to a given target.

You are given:

• An integer array nums.
• An integer target representing the desired sum.

The task is to return the indices of the two numbers in nums that add up to target. You may assume that exactly one valid solution exists and that the same element cannot be used twice.

This problem is often used to introduce key ideas like hash maps (dictionaries) for constant-time lookups, and it is an excellent exercise in thinking about both brute-force and optimized solutions.

Problem Difficulty & Tags

On LeetCode, the Two Sum problem is marked as Easy. Even though it’s considered a beginner-level challenge, it’s incredibly valuable because it introduces the idea of using a hash map (or dictionary) to achieve efficient lookups.

From my perspective at Solviyo, I often recommend this problem as a starting point for anyone who is beginning their journey with LeetCode or competitive programming. It builds the foundation for more advanced problems where similar optimization ideas are applied.

Here are the common tags associated with this problem:

• Array
• Hash Map / Dictionary
• Brute Force vs. Optimization

If you are working through coding interview prep, you will notice that Two Sum (and its variations like 3Sum and 4Sum) are interview favorites. Mastering this one is a must.

Understanding the Problem

At first glance, the Two Sum problem looks straightforward: we need to find two numbers in an array that add up to a given target. But to really understand it, let’s break it down step by step.

Suppose we are given an array nums and a number target. The goal is to return the indices of the two numbers such that:

nums[i] + nums[j] = target, where i ≠ j

Key points to keep in mind:

• There will always be exactly one solution. That means we don’t need to handle cases where no solution exists.
• The same element cannot be reused. So if target is 10 and there’s only one 5 in the array, we can’t count it twice.
• We need to return the indices, not the actual numbers. This makes it slightly trickier than just checking sums.

Understanding these details is important, because it influences the approach we take. A brute force solution might check all possible pairs, but that’s not efficient. With a bit of optimization, we can solve this in linear time.

Approach / Logic Explanation

When I first explain this problem at Solviyo, I like to start with the brute force approach, and then move toward the optimized version. This way, the logic feels natural and easy to follow.

Brute Force Approach

The most straightforward way is to check every possible pair (i, j) in the array and see if their sum equals the target. While this works, the time complexity is O(n²), which becomes very slow when the array is large.

Optimized Approach using Hash Map

To do better, we can use a hash map (dictionary) to store numbers we’ve already seen, along with their indices. The idea is simple:

1. Iterate through the array one element at a time.
2. For the current number x, calculate its complement as target - x.
3. Check if the complement already exists in the hash map:
   • If yes, we found our answer: the current index and the stored index of the complement.
   • If no, add the current number with its index to the map and move on.

This way, we only need one pass through the array, and each lookup in the hash map is O(1). So the overall time complexity becomes O(n), which is optimal.

This logic is exactly what I’ve applied in the C++ and Go solutions below. Both languages handle hash maps differently, but the underlying idea remains the same.

Solution Code

Below are the clean implementations of the Two Sum problem using C++ and Go. Both follow the same optimized hash map approach discussed earlier.

C++ Solution

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    vector twoSum(vector &nums, int tar) {
        unordered_map mp;
        int sz = nums.size();
        vector v;
        for(int i = 0; i < sz; i++) {
            if(mp.find(nums[i]) != mp.end()) {
                v.clear();
                v.push_back(mp[nums[i]]);
                v.push_back(i);
            } else {
                mp[tar - nums[i]] = i;
            }
        }
        return v;
    }
};
  

Go Solution

package main

import "fmt"

func twoSum(nums []int, target int) []int {
    mp := map[int]int{}
    res := []int{}

    // First pass: store numbers with their indices
    for i := 0; i < len(nums); i++ {
        mp[nums[i]] = i
    }

    // Second pass: check complements
    for i := 0; i < len(nums); i++ {
        comp := target - nums[i]
        value, exists := mp[comp]

        if exists && value != i {
            res = []int{i, value}
            fmt.Println(res)
            return res
        }
    }

    return nil
}
  

Step-by-Step Walkthrough

Let’s go through your Two Sum solution step by step, to understand exactly how it works in both C++ and Go.

Step 1: Initialize the Hash Map

In both implementations, we use a hash map (or dictionary) to store numbers and their corresponding indices. This allows us to quickly check if a complement of the current number exists in the array.

• C++: unordered_map mp;
• Go: mp := map[int]int{}

Step 2: Iterate Over the Array

We loop through each element in nums. For each number, we do two main things:

1. Check if the current number exists in the map (meaning we’ve already stored its complement).
2. If not, store its complement (target - current number) along with the current index.

Step 3: Finding the Pair

When the current number exists in the map, it means we previously stored its complement. Therefore, we have found the two indices whose values sum up to the target:

• C++: v.push_back(mp[nums[i]]); v.push_back(i);
• Go: res = []int{i, value}

After finding the pair, the function returns the indices immediately. In Go, we also print them for clarity.

Step 4: Returning the Result

Finally, after the iteration, the function returns a vector (C++) or slice (Go) containing the two indices. Since the problem guarantees exactly one solution, we don’t need to worry about multiple pairs.

Key Observations

• Storing the complement in the map is a clever trick. It ensures that we can find the solution in O(n) time.
• Checking value != i in Go ensures we do not use the same element twice.
• Using a hash map allows constant-time lookups, which is why this approach is much faster than brute force.

Sample Input & Output

Here are some examples to illustrate the input and expected output for the Two Sum problem:

Time & Space Complexity Analysis

Analyzing the efficiency of our solution is important, especially when dealing with large arrays. Let’s break down the complexities for the C++ and Go implementations.

Time Complexity

• We iterate through the array once (or twice in the Go implementation), performing constant-time operations for each element.
• Each hash map lookup and insertion takes O(1) on average.
• Therefore, the overall time complexity is O(n), where n is the number of elements in nums.

Space Complexity

• We use a hash map to store numbers and their indices.
• The size of the map grows linearly with the number of elements, so space complexity is O(n).
• Other than the map and the result vector/slice, no additional memory is used.

Summary: By using a hash map, we achieve a fast linear-time solution with additional linear space. This makes the solution highly efficient for typical coding interview and LeetCode constraints.

Mistakes to Avoid & Tips

Related Problems

If you enjoyed solving Two Sum, here are some similar problems to practice and strengthen your array and hash map skills:

• 3Sum – LeetCode
• 4Sum – LeetCode
• Two Sum II (Input Array Is Sorted) – LeetCode

Conclusion

The Two Sum problem is a classic exercise that teaches an essential technique for efficiently handling arrays and hash maps. By understanding how to track complements using a hash map, you can solve this problem in linear time, which is optimal.

From my experience at Solviyo, mastering this problem is a big step toward tackling more complex challenges like 3Sum, 4Sum, or variations that appear frequently in coding interviews.

Always remember to consider edge cases, check for duplicates, and ensure you are not using the same element twice. Keep practicing, and soon these patterns will become second nature in your problem-solving toolkit.

Every problem you solve adds to your confidence and understanding, so stay curious, experiment with different approaches, and enjoy the learning journey!