In the world of computer science and algorithm design, one common problem is finding pairs of numbers in a list that add up to a given sum. This is a quintessential problem that tests the foundational understanding of algorithmic efficiency and data structures. In this article, we will dive deep into one particular algorithm designed to solve this problem efficiently.

Problem Definition

Given a list of integers, nums , and an integer target , return indices of the two numbers such that they add up to the target.

Constraints

1. Each input list will have exactly one solution.
2. You may not use the same element twice.
3. Return the answer in any order.

Algorithm

We'll review a commonly used algorithm that achieves this task with an optimal time complexity.

Approach: Hash

Map

The hash map (or dictionary in Python) offers an optimal solution to find the pair of sums. Here's how the algorithm works:

1. Initialization: Create an empty hash map (dictionary) to store the elements of the list and their respective indices.
2. Iterate through nums: For each element, num :
   • Calculate the complement as target - num .
   • Check if the complement exists in the hash map.
   • If it does, we found our two numbers, and we can return their indices.
   • If not, store the current num along with its index in the hash map.

By leveraging the hash map, we achieve an average time complexity of $O(n)$ due to the constant-time average complexity of hash table operations like insertions and lookups.

Example of the Approach

Consider the list nums = [2, 7, 11, 15] and target = 9 . Here's how the algorithm proceeds:

• Initialize an empty hash map: \{\}
• Iteration 1: num = 2
  • complement = 9 - 2 = 7
  • Hash map: \{\}
  • 7 is not in the hash map.
  • Insert 2 into the hash map with index 0 : \{2: 0\}
• Iteration 2: num = 7
  • complement = 9 - 7 = 2
  • Hash map: \{2: 0\}
  • 2 is in the hash map with index 0 .
  • Return [0, 1] .

The result is the indices of 2 and 7 , which add up to 9 .

Algorithm Implementation

Here is a Python implementation of the above algorithm:

• Space Complexity: O(n) — We use a hash map to store elements, which can hold up to n elements in the worst-case scenario.
• Time Complexity: O(n) — We traverse the list once, and each lookup in the hash map is, on average, $O(1)$.