The Two Sum Problem

Problem Statement: Two Sum

The Two Sum problem is a popular question in coding interviews and foundational in learning hash maps.

Problem

Given an array of integers, return indices of the two numbers that add up to a specific target.

Example

Input: arr = [2, 7, 11, 15], target = 9
Output: [0, 1]
Explanation: arr[0] + arr[1] = 2 + 7 = 9

You can find the detailed question description here:
LeetCode — Two Sum

Brute Force Approach

The simplest way to solve this problem is to check every pair of numbers in the array.

Implementation

// Brute force - Time Complexity: O(n^2), Space Complexity: O(1)
func twoSum() []int {
    arr := []int{2, 7, 11, 15}
    target := 9
    for index1, i := range arr {
        for index2, j := range arr {
            if i+j == target {
                return []int{index1, index2}
            }
        }
    }
    return nil
}

Explanation

1. Use nested loops to iterate through all pairs of numbers.

2. Check if the sum of two numbers equals the target.

3. If it does, return their indices.

Complexity Analysis

• Time Complexity: O(n²), as we are iterating through pairs of elements.

• Space Complexity: O(1), as no additional data structures are used.

Optimised Approach

We can improve the solution using a hash map to store the numbers and their indices.

Implementation

// Optimized approach - Time Complexity: O(n), Space Complexity: O(n)
func twoSum() []int {
    arr := []int{2, 7, 11, 15}
    target := 9
    hm := make(map[int]int) 
    for index, value := range arr {
        numberToFind := target - value
        if indexFound, ok := hm[numberToFind]; ok {
            return []int{indexFound, index}
        }
        hm[value] = index
    }
    return nil
}

Explanation

1. Use a hash map to store each number and its index.

2. For each number, calculate the complement (target - current number) (i.e value in above solution).

3. Check if the complement exists in the hash map.

4. If it does, return the indices.

Complexity Analysis

• Time Complexity: O(n), as we iterate through the array once.

• Space Complexity: O(n), as we store elements in a hash map.

Code and Repository

You can find the complete code for this solution and follow my progress solving LeetCode 75 questions in Golang on GitHub:

• GitHub Repository: DSA-Golang

• Solution Code: Two Sum Solution

Let’s Connect!

I’m documenting my journey to master DSA with Golang. If you’re on a similar path or just want to connect, feel free to reach out:

• LinkedIn: Salil Luley

• My Website: salilluley.vercel.app

Stay tuned for more solutions and insights as we tackle LeetCode 75 together. Happy coding!