Two Sum

Merge Intervals

Find the indices of two distinct values whose sum matches a target.

Given an integer array `nums` and an integer `target`, return the indices of two distinct elements whose values add up to `target`. Exactly one valid pair exists. Return the lower index first.

**Input / output**
- Input: `nums: integer[]`, `target: integer`
- Output: `[leftIndex, rightIndex]`

**Examples**
1. `nums = [2, 7, 11, 15], target = 9` returns `[0, 1]` because `2 + 7 = 9`.
2. `nums = [3, 2, 4], target = 6` returns `[1, 2]`.

**Constraints**
- `2 <= nums.length <= 10,000`
- `-1,000,000 <= nums[i], target <= 1,000,000`
- Do not reuse the same array element.

**Follow-up**
Can you solve it in linear time with a single pass and explain the memory tradeoff?

- You are given an array of integers and a target sum.
- The task is to find two distinct numbers in the array that add up to the target.
- You should return their indices as a result.

Understanding the Problem

- Start by considering a brute force approach where you check every possible pair.
- For each number, iterate through the remaining numbers and check if they add up to the target.
- This approach has O(n²) time complexity.

Brute Force Approach (Inefficient)

- The core operation is checking whether two numbers in the array add up to the target.
- For each number `num`, check if there’s another number `complement` such that:
  `num + complement = target`
- The complement can be calculated as `complement = target - num`.

Identifying the Core Operation

- Searching through the array takes O(n) time if done linearly. To make this faster, you can use a hash map (dictionary).
- A hash map allows for constant-time lookups (O(1)), so you can check if the complement exists as you iterate through the array.

Using a Hash Map for Efficient Lookup

- Create an empty hash map to store numbers and their indices as you iterate through the array.

Initializing the Hash Map

- Loop through the array.
- For each number, calculate its complement (the difference between the target and the current number).
- The complement is calculated as `target - num`.

Iterate Through the Array and Calculate Complement

- For each number, check if the complement exists in the hash map.
- If the complement is already in the hash map, it means you’ve found two numbers that add up to the target.
- Return the indices of the current number and its complement.

Check if the Complement Exists in the Hash Map

- If the complement is not found in the hash map, store the current number and its index in the hash map.
- This ensures that it can be checked as a complement for future numbers.

Store the Current Number in the Hash Map

Trace `nums = [3, 2, 4]`, `target = 6`. Store only numbers that appear before the current index.

| i | num | needed complement | map before check | action |
|---|---:|---:|---|---|
| 0 | 3 | 3 | `{}` | `3` is not present; store `{3: 0}` |
| 1 | 2 | 4 | `{3: 0}` | `4` is not present; store `{3: 0, 2: 1}` |
| 2 | 4 | 2 | `{3: 0, 2: 1}` | `2` is present at index `1`; return `[1, 2]` |

The invariant prevents using the same element twice because the current `4` is checked before it is inserted.

Dry run / state trace

- Returning the two values instead of their indices; the judge expects positions.
- Inserting the current value before checking its complement, which can reuse the same element when `target = 2 * num`.
- Assuming the input is sorted and using two pointers without preserving original indices.
- Overwriting duplicate values too early in a two-pass map; the one-pass version avoids this by checking first.
- Follow-ups: how would you return all pairs, handle no guaranteed solution, or reduce memory if the array were sorted?

Recommended next problem in this pattern: **Valid Anagram**, which uses a hash map for frequency balance instead of complement lookup.

Common mistakes & interviewer follow-ups

- Ensure that the input array has at least two numbers.
- Return `None` if no solution is found.