# 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](https://leetcode.com/problems/two-sum/description/)

## **Brute Force Approach**

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

## **Implementation**

```go
// 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**

```go
// 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](https://github.com/SalilLuley/DSA-Golang?tab=readme-ov-file)
    
* **Solution Code**: [Two Sum Solution](https://github.com/SalilLuley/DSA-Golang/blob/develop/leetcode_75/two_sum.go)
    

## **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](https://www.linkedin.com/in/salil-luley/)
    
* **My Website**: [salilluley.vercel.app](https://salilluley.vercel.app/)
    

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