NUHMAN.com

Introduction

The "Two Sum" problem is one of the most frequently asked coding interview questions. It tests your ability to think efficiently about searching and indexing problems. In this article, we will solve LeetCode Problem 1: Two Sum using Go (Golang) with a step-by-step explanation and optimized approach.

Problem Statement

Given an array of integers nums and an integer target, return the indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

Example

go

Input: nums = [2, 7, 11, 15], target = 9  
Output: [0, 1]

Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Brute Force Approach (Not Recommended)

We can use two loops to check every pair of numbers, but this takes O(n²) time. It works, but it's not efficient for large inputs.

go

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
}

Optimized Approach using Hash Map (Recommended)

To achieve O(n) time complexity, we can use a hash map to store the numbers we've already seen and their indices.

Algorithm Explanation:

1. Create an empty map seen to store number → index pairs.
2. Loop through the array:

• For each element num, compute its complement: target - num.
• Check if the complement exists in the map.
• If it does, return the current index and the index of the complement.
• If not, store num and its index in the map.

1. Return an empty array if no solution is found (though per problem statement, there is always one).

Go Implementation

go

package main

import (
    "fmt"
)

func twoSum(nums []int, target int) []int {
    seen := make(map[int]int) // value -> index

    for i, num := range nums {
        complement := target - num
        if index, found := seen[complement]; found {
            return []int{index, i}
        }
        seen[num] = i
    }

    return nil
}

func main() {
    nums := []int{2, 7, 11, 15}
    target := 9
    result := twoSum(nums, target)
    fmt.Println("Indices:", result)
}

Time and Space Complexity

• Time Complexity: O(n) — We traverse the list only once.
• Space Complexity: O(n) — At most, we store all n elements in the hash map.

Key Takeaways

• Using a hash map makes it easy to look up previously seen numbers in constant time.
• This approach is optimal for this problem and commonly used in interviews.
• Understanding the "Two Sum" problem helps in solving more complex variations such as "3Sum", "4Sum", etc.