Solving the Two Sum Problem

As a computer science enthusiast, I often come across intriguing problems that not only challenge my coding skills but also enhance my problem-solving abilities. One such classic problem is the "Two Sum" problem, a common interview question and a great exercise for anyone looking to improve their programming acumen. In this post, I'll walk you through what the Two Sum problem is, why it's important, and how to solve it using JavaScript.

The Two Sum problem is simple in its statement: Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target. This problem tests your understanding of array manipulation and hashing concepts. It's a fundamental question in algorithm design, often used to gauge a candidate's ability to work with data structures.

Understanding the Problem

The key to solving the Two Sum problem lies in understanding how to efficiently find two numbers in the array that sum up to the target value. A brute force approach would involve checking each pair of numbers, but this is inefficient, especially for large arrays. A more efficient approach involves using a hash table to store and quickly look up the complement of each number.

The Solution

Here's a TypeScript function that solves the Two Sum problem:

Here's a JavaScript function that solves the Two Sum problem:

Breaking Down the Solution

Initialize a Hash Table: We create a hash table (or object in JavaScript) to store each number's index as we iterate through the array.

Iterate Through the Array: We loop through each element in the array.

Calculate the Difference: For each element, we calculate the difference between the target and the current element. This difference is the value we need to find in the array to get a pair that sums to the target.

Check the Hash Table: We check if this difference already exists in our hash table. If it does, it means we have found a pair that adds up to the target. We return the indices of these two elements.

Store in the Hash Table: If the difference is not in the hash table, we add the current element and its index to the hash table and continue the loop.

Return Empty if No Solution: If no pair adds up to the target, we return an empty array.

Rust Solution

Rust's HashMap<i32, i32> must annotate both key and value types up front, unlike the untyped JS Map, and it is declared let mut map because inserting into it mutates it. nums.iter().enumerate() yields index/value pairs, and the for (i, &num) pattern dereferences each borrowed element into a plain i32 so the arithmetic works on values, not references. The lookup map.get(&diff) borrows its argument and returns an option, so if let Some(&j) = map.get(&diff) matches the hit and unwraps the inner reference in a single step. enumerate counts in usize, hence the i as i32 cast needed to fit the Vec<i32> return type, and the miss path yields an empty vec![] rather than Go's nil.

Go Solution

The comma-ok form j, ok := m[target-num] is Go's idiom for map lookups: ok is false when the key is absent, which cleanly separates a missing key from one that legitimately maps to the zero value. for i, num := range nums hands back the index and a copy of each element, and the table itself is built with the literal map[int]int{}. On a hit it returns the slice literal []int{j, i}; on no match it uses return nil instead of an empty slice — a nil slice is still a valid, length-zero []int, so a caller can range over it without a guard.