LeetCode Solution: 1. Two Sum

#leetcode #dsa #programming #tutorial

Conquering Your First LeetCode Challenge: Two Sum Demystified!

Hey there, aspiring coder! 👋 Ever heard of LeetCode? It's a fantastic platform to sharpen your problem-solving skills, and we're about to tackle one of its most famous (and foundational!) problems: Two Sum. Don't let the number "1" fool you; while it's often the first problem people encounter, it's packed with key concepts that will serve you well in your coding journey.

Let's dive in and unravel this classic together!

The Problem: Finding Our Pair

Imagine you have a list of numbers, like [2, 7, 11, 15], and a specific target number, say 9. Your mission, should you choose to accept it, is to find two different numbers in that list that add up to the target. Once you find them, you need to tell us their positions (their "indices") in the original list.

Here's the official breakdown:

Given:

An array of integers nums (e.g., [2, 7, 11, 15])
An integer target (e.g., 9)

Goal:

Return the indices of the two numbers in nums that sum up to target.

Key Assumptions:

There will always be exactly one pair that solves the problem.
You cannot use the same number twice (meaning, the two numbers must come from different positions in the array).
The order of the returned indices doesn't matter.

Let's look at an example to make it crystal clear:

Example 1:

nums = [2, 7, 11, 15]
target = 9

Thinking Process:

We look at 2. What number do we need to add to 2 to get 9? We need 7 (9 - 2 = 7).
Is 7 in our nums array? Yes, it is!
The index of 2 is 0.
The index of 7 is 1.
Since nums[0] + nums[1] == 9, we found our pair!

Output: [0, 1]

See? Not so scary, right?

The "Aha!" Moment: Beyond Brute Force

When you first encounter a problem like this, a common initial thought (and a totally valid one!) is to try every single combination. You might think:

"Let's take the first number (2).
- Add it to the second (7): 2 + 7 = 9. Bingo!
- (If not found, try 2 + 11, 2 + 15, etc.)"
"Then take the second number (7).
- Add it to the third (11): 7 + 11 = 18. No.
- (And so on...)"

This approach, known as brute force, involves using nested loops to check every possible pair. It works, but for very large lists, it can be slow. Imagine a list with 10,000 numbers! You'd be doing tens of millions of checks! 😵

So, the "aha!" moment comes when you realize: instead of searching for the other_number, what if we could instantly know if it exists and where it is?

This is where a super-powered data structure comes into play: the Hash Map (or Dictionary in Python, HashMap in Java/JavaScript, etc.).

If we know we need complement = target - current_number, and we want to find complement fast, a hash map is our best friend. It lets us store values (like numbers from our list) and retrieve their associated information (like their index) almost instantly!

Our Smart Approach: The Hash Map Helper

Here's how we can use a hash map to solve Two Sum efficiently:

Step 1: Build a Map of Numbers to Their Indices

First, we'll iterate through our nums array once. As we go, we'll build a hash map where:

Keys are the numbers from nums.
Values are their corresponding indices.

Why do this? Because it gives us a quick way to ask, "Hey, does the number X exist in nums, and if so, what's its index?"

Let's use nums = [2, 7, 11, 15] and target = 9 again:

Iteration	`nums[i]`	`i`	`hashmap` after adding `nums[i]: i`
1	2	0	`{2: 0}`
2	7	1	`{2: 0, 7: 1}`
3	11	2	`{2: 0, 7: 1, 11: 2}`
4	15	3	`{2: 0, 7: 1, 11: 2, 15: 3}`

Step 2: Find the Complement

Now that our hash map is fully built, we iterate through nums again. For each number nums[i]:

Calculate the complement: This is the number we need to find to reach our target. complement = target - nums[i].
Check the hash map: Does our complement exist as a key in the hashmap?
Crucial Check: If it does exist, we also need to make sure that the index stored for the complement (hashmap[complement]) is not the same as our current index i. Remember, we can't use the same element twice!
Found It!: If both conditions are true, we've found our pair! We return [i, hashmap[complement]].

Let's trace this step with our example: nums = [2, 7, 11, 15], target = 9, hashmap = {2: 0, 7: 1, 11: 2, 15: 3}.

`i`	`nums[i]`	`complement = target - nums[i]`	`complement` in `hashmap`?	`hashmap[complement]`	`hashmap[complement] != i`?	Action
0	2	`9 - 2 = 7`	Yes	1	`1 != 0` (True)	Return `[0, 1]`

And just like that, we found our solution efficiently!

The Code: Python Magic ✨

from typing import List

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        # Step 1: Build the hash map
        # Stores {number: index}
        hashmap = {} 
        for i in range(len(nums)):
            hashmap[nums[i]] = i

        # Step 2: Iterate again to find the complement
        for i in range(len(nums)):
            complement = target - nums[i]

            # Check if the complement exists in our hashmap
            # AND make sure its index isn't the same as our current 'i'
            if complement in hashmap and hashmap[complement] != i:
                return [i, hashmap[complement]]

        # This line should technically not be reached given the problem constraints
        # ("exactly one solution exists"), but it's good practice for robust code.
        return []

The Nitty-Gritty: Time & Space Complexity

Understanding how efficient your code is (or isn't!) is a fundamental skill. We measure this using Time Complexity (how execution time grows with input size) and Space Complexity (how memory usage grows).

Time Complexity: O(n)
- Explanation: We iterate through the nums array twice.
  - The first loop builds the hash map, doing n operations (each insertion into a hash map takes, on average, O(1) time). So, O(n) for the first loop.
  - The second loop performs n lookups (each complement in hashmap and hashmap[complement] takes, on average, O(1) time). So, O(n) for the second loop.
- Adding these up, O(n) + O(n) simplifies to O(n). This is considered very efficient!
- (Remember the follow-up question? "Can you come up with an algorithm that is less than O(n^2) time complexity?" We did it! Brute force would have been O(n^2).)
Space Complexity: O(n)
- Explanation: We create a hash map to store elements from the nums array. In the worst case (all numbers are unique), the hash map will store n key-value pairs. Therefore, the space required grows linearly with the input size n.

Key Takeaways for Your Coding Journey

Hash Maps are Powerful: They excel at fast lookups. Whenever you need to quickly check if an item exists or retrieve its associated data, think hash map!
The "Complement" Idea: Many problems can be reframed by thinking, "What X do I need to reach Y?" (i.e., X = Y - current_item). This is a common pattern in competitive programming.
Optimize Beyond Brute Force: While brute force is a great starting point to understand a problem, always challenge yourself to find more efficient solutions, especially when dealing with larger inputs. O(n) is often a significant upgrade from O(n^2).
Understand Constraints: The problem statement's constraints and assumptions (like "exactly one solution" and "cannot use the same element twice") are vital. They guide your solution and help you avoid unnecessary checks or edge cases.

And there you have it! You've successfully navigated LeetCode's Problem #1, "Two Sum," armed with the power of hash maps. This problem is a gateway to many more exciting algorithmic challenges. Keep practicing, keep learning, and happy coding!

Author: p1Hzd8mRM8
Published: 2026-05-16 20:53:55