Two Sum Problem: A Straightforward Guide

Are you just starting out on your coding interview journey? One classic problem you might come across is the Two Sum problem. In this post, I’ll break it down for you in a way that even new coders, like me, can grasp.

Problem Statement

Given an array of integers and a target integer, your task is to return the indices of two numbers in the array that add up to the target.

Example:

Input: nums = [2, 7, 11, 15], target = 9
Output: [0, 1]
Explanation: nums[0] + nums[1] = 2 + 7 = 9
Note: you can return the indices in any order and there is only one answer.

Leet code will give you the input and output most of the time, but it's a good idea to make sure that you can note those pieces of information before you start coding interviews, they won't always be given.

The Intuitive (But Less Optimal) Approach

You might think, hmmm, I could use a nested loop to check every combination of two numbers. Although this would work, its time complexity would be O(n^2), which isn’t optimal.

The Efficient Approach: Enter Hashmaps!

Hashmaps (or objects in JavaScript) can work wonders here. They allow us to remember the numbers we’ve seen and retrieve them in constant time, leading to a solution with O(n) time complexity.

Here’s the Plan:

1. Traverse the list once.
2. For each number, calculate its complement(target-current number).
3. Check if this complement exists in our hashmap.
4. If it doesn’t, store the current number with its index.
5. If it does, return the current index and the stored index from the hashmap.

Let’s Dive into the Code

The code above implements our master plan, its a good thing we wrote it out so beautifully! We iterate through the array only once, making our solution efficient and elegant.

Wrap Up

By using hashmaps and understanding what the problem is asking, we’ve transformed the two-sum problem from a potentially not-so-beautiful and clean O(n^2) solution to a sleek O(n) one.

Remember, coding interviews are not just about getting the answer right every time. They are about being able to communicate well and show a clear understanding of data structures and their applications.

Go forth and code!