> For the complete documentation index, see [llms.txt](https://tanias-workspace.gitbook.io/tanias-little-corner/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://tanias-workspace.gitbook.io/tanias-little-corner/problems/two-sum.md).

# Two Sum

<figure><img src="/files/pgQkF2SZvxIaKLwfqlZV" alt=""><figcaption></figcaption></figure>

## Intuition

The Two Sum problem requires us to identify two distinct numbers in an array that add up to a specified target. The solution should return the indices of these two numbers.

## Approach

A straightforward method is to examine every possible pair of elements in the array to see if their sum matches the target. This can be achieved using two nested loops: the outer loop starts from the first element and runs until the second-to-last, while the inner loop begins just after the current element in the outer loop and continues to the end of the array. Although this brute force approach is simple to implement, it has a time complexity of O(n²), making it inefficient for larger arrays.

<figure><img src="/files/Ccrkw4LtOo22dm3XIcXj" alt=""><figcaption></figcaption></figure>

## Explanation:

* **Outer loop**: Iterates over each element in the array.
* **Inner loop**: Checks the sum of the current element with every subsequent element.
* **If condition**: If a pair is found whose sum equals the target, their indices are returned.
* **Return**: If no valid pair is found, the function returns `{}`

## Solution 2: (One-pass Hash Table) <a href="#solution-3-one-pass-hash-table" id="solution-3-one-pass-hash-table"></a>

<figure><img src="/files/ffnNGtsdzyZTdh2iFrpF" alt=""><figcaption><p>Hash Table</p></figcaption></figure>

#### **Example Walkthrough**

Given `nums = [2, 7, 11, 15]` and `target = 9`:

1. **Iteration 1 (i = 0):**
   * `nums[i] = 2`
   * `result = 9 - 2 = 7`
   * The map is empty, so add `2` to the map: `map = {2: 0}`.
2. **Iteration 2 (i = 1):**
   * `nums[i] = 7`
   * `result = 9 - 7 = 2`
   * `result (2)` exists in the map at index `0`, so return `[0, 1]`.

This output `[0, 1]` indicates that `nums[0] + nums[1] = 2 + 7 = 9`, which satisfies the condition.

#### **Conclusion**

The `twoSum` function efficiently finds two indices in the array that sum to the target by leveraging a hash map to store and quickly look up complements, resulting in a time complexity of **O(n)**.