Introduction

The 2-SUM problem is a classical problem in computer science and algorithm design which involves finding two numbers in a list that add up to a given target sum. This problem has applications in various domains, including cryptography, hashing, and computational geometry. While a naive approach can solve the problem in quadratic time, more efficient algorithms can achieve a linear time complexity under certain conditions.

This article focuses on a linear time algorithm for solving the 2-SUM problem, illustrating how hash tables can be exploited to reduce computational complexity and speed up operations.

Problem Definition

Given an array of integers `nums` and an integer `target`, the objective of the 2-SUM problem is to find indices `i` and `j` such that:

$$\text{nums}[i] + \text{nums}[j] = \text{target}$$

Where `i != j`.

Naive Approach

The most straightforward way to solve the 2-SUM problem is using a brute-force method:

1. For each element `nums[i]` in the array, iterate through every other element `nums[j]`.
2. Check if the sum of the current pair equals the `target`.
3. Return the indices `[i, j]` if a match is found.

This approach has a time complexity of $O(n^2)$ due to the nested iteration over the array elements.

Linear Time Algorithm

Overview

To improve efficiency, we can use a hash table (or dictionary) to store complements of the elements as we iterate through the list. The hash table allows constant time complexity for both checking membership and inserting new elements.

Algorithm

1. Initialize a `Hash` Table: Create an empty hash table (or dictionary) to store visited numbers and their indices.
2. Iterate Over the Array: Traverse each element in the `nums` array.
3. Calculate Complement: For each element, compute its complement with respect to the target, i.e., `complement = target - nums[i]`.
4. Check `Hash` Table: • If the complement is found in the hash table, it indicates that the pair exists and their sum is equal to the target. Thus, return the indices. • If the complement is not found, store the current number and its index in the hash table.
5. Repeat Until Solution is Found or List is Exhausted.

Example Implementation in Python

• Iteration 1: Current number is `2`. Its complement is `9 - 2 = 7`. Store `2` in hash table: `{2: 0}`. • Iteration 2: Current number is `7`. Complement `2` is in hash table. Return indices `[0, 1]`.