Vansh Aggarwal

Posted on May 17

LeetCode Solution: 1. Two Sum

#leetcode #dsa #programming #tutorial

Two Sum: Your First Step into LeetCode Magic! ✨

Hey there, future coding superstar! 👋 Welcome to your very first LeetCode adventure! If you're just starting your journey into algorithms and data structures, you've landed in the perfect place. We're going to tackle a legendary problem today: Two Sum. It's often the first problem many programmers encounter, and it's a fantastic way to learn about efficiency and the power of data structures.

Ready to unlock some coding magic? Let's dive in!

🧐 Problem Explanation: What are we trying to do?

Imagine you have a list of numbers, like [2, 7, 11, 15]. And you're given 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 your target.

Once you find them, you don't return the numbers themselves, but their positions (indices) in the original list.

Let's look at our example:

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

Can you spot the pair?

2 is at index 0.
7 is at index 1.
And hey, 2 + 7 = 9! Bingo!
So, our answer would be [0, 1].

A few ground rules to keep in mind:

One Solution, Guaranteed: You'll always find exactly one pair that works. No need to worry about multiple answers or no answer at all.
No Reusing: You can't use the same number twice. If nums = [3, 3] and target = 6, you use the 3 at index 0 and the 3 at index 1 (they're distinct elements, even if their values are the same).
Order Doesn't Matter: Returning [0, 1] or [1, 0] is perfectly fine.

🤔 Intuition: The "Aha!" Moment

When you first hear this problem, your brain probably jumps to the most straightforward solution: "I'll just try every single combination of two numbers until I find the pair!"

This is a totally natural and valid starting point! It's called the brute-force approach. Think of it like rummaging through a messy drawer, picking one sock, and then trying to find its matching pair by looking at every other sock.

But here's the thing about competitive programming and real-world coding: we often want the fastest and most efficient way to solve a problem. Is there a shortcut to finding that second sock? What if you had an ultra-organized sock drawer where you could instantly find any sock you needed?

The "aha!" moment for Two Sum comes when you realize that instead of constantly re-scanning the list for the second number, you could remember the numbers you've already seen and their positions. This way, when you're looking for a complement (the number that adds up to the target), you can "ask" your memory if you've already seen it.

🚀 Approach: Step-by-Step Logic

Let's break down how we can solve this problem, starting with the simpler (but less efficient) way, then moving to a much smarter solution!

1. The Brute-Force (Nested Loops) Approach

This is your first instinct, and it's essential to understand it before optimizing!

Start with the first number in the list (let's call it num1).
Then, take num1 and compare it with every other number in the rest of the list (let's call these num2).
If num1 + num2 equals your target, fantastic! You've found your pair. Return their indices.
If not, keep trying different num2s with the current num1.
If you've checked all possible num2s for the current num1, move to the next num1 in the original list and repeat the whole process.

Dry Run Example: nums = [2, 7, 11, 15], target = 9

Outer loop (i = 0, num1 = 2):
- Inner loop (j = 1, num2 = 7): Is 2 + 7 == 9? YES! Return [0, 1].

This works perfectly, but as the list nums gets bigger, this approach becomes very slow because of all the re-checking.

2. The Smarter Way: Using a Hash Map (Dictionary)

This is where the magic happens! A Hash Map (also known as a Dictionary in Python, HashMap in Java, or Hash Table) is a data structure that allows you to store key: value pairs and look up a key almost instantly! Think of it like a super-fast index for your numbers.

Here's the optimized strategy:

Create an empty Hash Map. We'll use it to store numbers we've already seen, along with their indices. The format will be {number: index}.
Go through the nums list one number at a time. For each number, let's call it current_num and its index i.
Calculate the complement: This is the number we need to find to hit our target.
- complement = target - current_num
- Example: If target = 9 and current_num = 2, we need complement = 9 - 2 = 7.
Check your Hash Map: Look if this complement is already a key in your Hash Map.
- If it IS in the map: Wow! You've found your pair! The complement is one number, and your current_num is the other.
  - Return the index stored with the complement (i.e., hashmap[complement]) and your current index i.
- If it's NOT in the map: No worries! It just means we haven't encountered its partner yet. Add your current_num and its index i to the Hash Map. This way, if a future number needs current_num as its complement, it will be found instantly.
Continue this process until you find the pair (which, remember, you're guaranteed to do!).

Dry Run Example: nums = [2, 7, 11, 15], target = 9

Current `i`	Current `num`	`complement = target - num`	Is `complement` in `hashmap`?	Action	`hashmap` (after action)
					`{}`
`0`	`2`	`9 - 2 = 7`	No	Add `2:0` to `hashmap`	`{2:0}`
`1`	`7`	`9 - 7 = 2`	Yes! (`2` is in `hashmap`)	Return `[hashmap[2], 1]` which is `[0, 1]`

And we found the answer much quicker!

💻 Code (Python)

Here's the Python code implementing the Hash Map approach:

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        # Initialize an empty hash map (dictionary in Python)
        # This map will store: {number_value: its_index}
        hashmap = {}

        # Iterate through the list of numbers.
        # 'enumerate' gives us both the index (i) and the value (num) at each step.
        for i, num in enumerate(nums):
            # Calculate the 'complement' needed.
            # If current 'num' is X and 'target' is T, we need T - X.
            complement = target - num

            # Check if this 'complement' is already a key in our hashmap.
            # This is a very fast O(1) average time operation!
            if complement in hashmap:
                # If found, we've got our pair!
                # Return the index of the complement (retrieved from the hashmap)
                # and the index of the current number (i).
                return [hashmap[complement], i]

            # If the complement isn't found, it means the current 'num'
            # hasn't found its partner yet. So, we add 'num' and its index 'i'
            # to the hashmap. This makes it available for future numbers
            # that might need 'num' as their complement.
            hashmap[num] = i

        # The problem guarantees exactly one solution, so this part of the code
        # should technically never be reached. However, in other scenarios,
        # you might raise an error or return an empty list if no solution is found.

⏱️ Time & Space Complexity Analysis

Understanding how efficient your code is is a crucial skill!

Brute-Force Approach (Nested Loops)

Time Complexity: O(n^2)
- We have two loops, one nested inside the other. If the list has n elements, the outer loop runs n times, and the inner loop runs up to n-1 times for each outer loop iteration. This results in approximately n * n = n^2 operations. As n grows, n^2 grows very quickly, making it inefficient for large lists.
Space Complexity: O(1)
- We're not using any additional data structures that scale with the input size, just a few variables.

Hash Map Approach

Time Complexity: O(n)
- We iterate through the list only once. For each number, we perform a constant number of operations: calculate the complement, check if it's in the hash map, and potentially add the current number to the hash map.
- Looking up an item in a hash map and inserting an item into it both take, on average, O(1) (constant) time.
- Therefore, n operations, each taking O(1) time, results in an overall O(n) time complexity. This is significantly faster than O(n^2) for larger inputs!
Space Complexity: O(n)
- In the worst case, we might have to add almost all n numbers and their indices to our hash map before finding the desired pair. This means the space used by the hash map grows proportionally with the number of elements in the input list.

🌟 Key Takeaways

Start Simple: Don't be afraid to think of the brute-force solution first. It helps you understand the problem thoroughly.
Hash Maps are Powerful: For problems that involve quick lookups, checking for existence, or mapping values to other values, Hash Maps (dictionaries) are incredibly efficient and often the key to optimizing your solution.
Think in Complements: Many "find a pair/sum" problems can be broken down into calculating what complement you need and then efficiently searching for it.
Time-Space Trade-off: We improved our time complexity from O(n^2) to O(n) by using more space (O(n) for the hash map). This is a very common and powerful trade-off in algorithm design!

Congratulations! You've just conquered your first LeetCode problem with an optimized solution. This foundational problem teaches you concepts that you'll apply to many more challenges down the road. Keep practicing, and happy coding!

Author: NavyaSree_14
Published: 2026-05-17 11:09:40

DEV Community