# 1. Two Sum

🟩 Easy

Given an array of integers `nums` and an integer `target`, return *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 1

> **Input**: nums = \[2,7,11,15], target = 9\
> **Output**: \[0,1]\
> **Explanation**: Because nums\[0] + nums\[1] == 9, we return \[0, 1].

## Example 2

> **Input**: nums = \[3,2,4], target = 6\
> **Output**: \[1,2]

## Example 3

> **Input**: nums = \[3,3], target = 6\
> **Output**: \[0,1]

## Constraints

* `2 <= nums.length <= 10^4`
* `-10^9 <= nums[i] <= 10^9`
* `-10^9 <= target <= 10^9`
* **Only one valid answer exists.**

## Hint-1

> A really brute force way would be to search for all possible pairs of numbers but that would be too slow. Again, it's best to try out brute force solutions for just for completeness. It is from these brute force solutions that you can come up with optimizations.

## Hint-2

> So, if we fix one of the numbers, say `x`, we have to scan the entire array to find the next number `y` which is `value - x` where value is the input parameter. Can we change our array somehow so that this search becomes faster?

## Hint-3

> The second train of thought is, without changing the array, can we use additional space somehow? Like maybe a hash map to speed up the search?

**Follow-up:** Can you come up with an algorithm that is less than `O(n2)` time complexity?

## Solution

My Solution

```go
func twoSum(nums []int, target int) []int {
    m := map[int]int{}

    for i:=0; i<len(nums); i++ {
        if j,ok := m[target - nums[i]]; ok {
            return []int{j,i}
        }

        m[nums[i]]=i
    }

    return []int{}
}
```

Optimal Solution (One-Pass Hash Table)

```go
func twoSum(nums []int, target int) []int {
    // Map to store complement -> index
    seen := make(map[int]int, len(nums))
    
    // Single pass through array
    for i, num := range nums {
        // Check if complement exists
        if j, exists := seen[target-num]; exists {
            return []int{j, i}
        }
        // Store current number and index
        seen[num] = i
    }
    
    // No solution found (shouldn't happen given problem constraints)
    return nil
}
```

### Approach

This solution uses a hash table to achieve O(n) time complexity:

1. Key Insight:
   * For each number x, we need to find y where x + y = target
   * Therefore, y = target - x (the complement)
   * Hash table gives O(1) lookup for complement
2. Implementation Strategy:
   * Use map to store number -> index mapping
   * For each number, check if its complement exists
   * Store current number after checking
3. Processing Rules:
   * Check complement before storing current number
   * Return immediately when pair found
   * Given constraints guarantee a solution exists

### Complexity Analysis

#### Time Complexity: O(n)

* Single pass through the array
* Hash table operations are O(1)
* Each number processed exactly once
* Early return when solution found

#### Space Complexity: O(n)

* Hash table stores at most n elements
* Each entry stores:
  * Key: number (integer)
  * Value: index (integer)
* No other significant space used

### Why it works

* Mathematical Property:
  * If x + y = target
  * Then y = target - x
  * Only need to find one valid pair
* Hash Table Benefits:
  * O(1) lookups
  * O(1) insertions
  * Stores history of seen numbers
* Optimization Details:
  * Pre-allocate map capacity
  * Check before insert pattern
  * Early return on match
  * No need for second pass
* Edge Cases Handled:
  * Two same numbers summing to target
  * Negative numbers
  * Zero as target or number
  * Large numbers (within int range)

![result](/files/SRJSIJHLCF0K6zrYyB9M)

Leetcode: [link](https://leetcode.com/problems/two-sum/description/)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://leetcode.realtemirov.uz/problems/1.-two-sum.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.