# Two Sum

- **Canonical ID**: `two-sum`
- **Canonical URL**: https://dsacheatsheet.com/problems/two-sum
- **Difficulty**: easy
- **Patterns**: Arrays & Hashing
- **Version**: 1.0.0 (verified 2026-11-11T21:00:00Z)
- **Original Problem**: https://leetcode.com/problems/two-sum/

## 1. Core Invariant / The Trick

Store `{ value: index }` in a map as you iterate. Before inserting `nums[i]`, check whether `target - nums[i]` is already present.

## 2. Complexity Bounds & Proof

- **Time Complexity**: `O(N)`
- **Space Complexity**: `O(N)`
- **Proof**: One scan performs O(1) expected hash lookup and insertion per element.

## 3. Minimal Idiomatic Code

### Python
```python
def twoSum(nums: list[int], target: int) -> list[int]:
    seen = {}
    for i, x in enumerate(nums):
        if target - x in seen:
            return [seen[target - x], i]
        seen[x] = i
    return []
```

### TypeScript
```typescript
export function twoSum(nums: number[], target: number): number[] {
  const seen = new Map<number, number>();
  for (let i = 0; i < nums.length; i++) {
    const comp = target - nums[i];
    if (seen.has(comp)) return [seen.get(comp)!, i];
    seen.set(nums[i], i);
  }
  return [];
}
```

### C++
```cpp
vector<int> twoSum(vector<int>& nums, int target) {
    unordered_map<int, int> seen;
    for (int i = 0; i < (int)nums.size(); ++i) {
        if (seen.count(target - nums[i])) return {seen[target - nums[i]], i};
        seen[nums[i]] = i;
    }
    return {};
}
```

### Java
```java
int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> seen = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        if (seen.containsKey(target - nums[i])) return new int[]{seen.get(target - nums[i]), i};
        seen.put(nums[i], i);
    }
    return new int[]{};
}
```

### Go
```go
func twoSum(nums []int, target int) []int {
    seen := make(map[int]int)
    for i, x := range nums {
        if j, ok := seen[target-x]; ok { return []int{j, i} }
        seen[x] = i
    }
    return nil
}
```

## 4. Failure Modes & Interview Follow-ups

### Pitfalls
- Inserting `nums[i]` before checking `target - nums[i]` reuses the same index when `target == 2 * nums[i]`.

### Follow-ups
- If input is sorted, use Two Pointers in O(1) space.