LeetCode Solution: 1. Two Sum

#leetcode #dsa #programming #tutorial

Your First LeetCode Victory: Cracking "Two Sum" with Python!

Hey there, aspiring coders and LeetCode adventurers! 👋 Welcome to your first step into the exciting world of algorithmic problem-solving. Today, we're tackling a true classic, often the very first problem many developers encounter: "Two Sum".

Don't let the "LeetCode" name intimidate you! We'll break it down step-by-step, uncover the magic behind the solution, and get you confident in your coding journey. Think of this as your friendly guide to an "aha!" moment. ✨

🧐 The Problem: What Are We Looking For?

Imagine you're given a list of numbers, like a shuffled deck of cards, and a specific "target" number. Your mission, should you choose to accept it, is to find two different numbers in that list that, when added together, perfectly equal your target.

But there's a twist! Instead of just saying "Found them!", you need to tell us where they are in the list – their positions, or indices.

Here's the official breakdown:

Given:

An array (list) of integers called nums.
An integer called target.

Return:

The indices of the two numbers that add up to target.

Important Guarantees (to make our lives easier!):

There will always be exactly one pair of numbers that sum to the target. No need to worry about multiple solutions or no solutions.
You cannot use the same number twice (even if it appears multiple times in the list, you pick two distinct positions).
You can return the indices in any order.

Let's look at some examples to make it super clear:

Example 1:

nums = [2, 7, 11, 15]
target = 9
Output: [0, 1]
Why? Because nums[0] (which is 2) + nums[1] (which is 7) = 9. We return their positions: 0 and 1.

Example 2:

nums = [3, 2, 4]
target = 6
Output: [1, 2]
Why? Because nums[1] (which is 2) + nums[2] (which is 4) = 6.

See? Not so scary, right? Now, let's figure out how to solve it!

🤔 Intuition: How Would You Find It?

Before jumping to code, let's think like a human.

The "Brute Force" Way (Our first thought):
If you had nums = [2, 7, 11, 15] and target = 9, you might do this:

Take 2 (at index 0).
- Pair it with 7 (at index 1): 2 + 7 = 9. Aha! Found it!
- (If not, you'd continue: 2 + 11 = 13 (no), 2 + 15 = 17 (no)).
Then you'd move to 7 (at index 1).
- Pair it with 11 (at index 2): 7 + 11 = 18 (no).
- Pair it with 15 (at index 3): 7 + 15 = 22 (no).
...and so on.

This approach works! You're checking every possible pair. But imagine a list with thousands of numbers. Checking every number with every other number would take a very long time. This is what we call an O(n^2) solution (quadratic time complexity), which means the time it takes grows very quickly as the list gets larger. Can we do better?

The "Aha!" Moment (The Smart Way):
Let's rethink. We're looking for num1 + num2 = target.
This can be rewritten as num2 = target - num1.

So, as we look at num1, we immediately know exactly what num2 we need.
Instead of blindly searching for num2 by checking every subsequent number, what if we could instantly ask: "Hey, have I already seen the num2 I need among the numbers I've processed so far?"

If we have a super-fast way to remember numbers we've seen and their positions, we could find the num2 instantly! This "super-fast way to remember and look up" is exactly what a hash map (or a dictionary in Python) is for!

🚶 The Approach: Step-by-Step with a Hash Map

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

Initialize an empty hash map (dictionary): We'll call it seen_numbers. This map will store key-value pairs where the key is a number we've encountered, and the value is its index in the nums array.
- Example: {number: index}
Iterate through the nums array: Go through each number one by one. For each number, we'll keep track of its actual value and its index.
For each num at index:
a. Calculate the complement: This is the number we need to find to make the sum equal to target.
complement = target - num
b. Check if complement is in seen_numbers:
* IF YES: Fantastic! We've found our pair. The complement is in our hash map, and its index is seen_numbers[complement]. The current num is what we're looking at right now, and its index is i. We return [seen_numbers[complement], i]. We're done!
* IF NO: No worries! The complement isn't among the numbers we've seen yet. So, we add the current number (num) and its index (i) to our seen_numbers map. This way, if a future number needs num as its complement, it can find it quickly. seen_numbers[num] = i

Since the problem guarantees there's exactly one solution, our loop will always find a pair and return it.

Let's trace nums = [2, 7, 11, 15], target = 9:

`i`	`num`	`complement = 9 - num`	`complement` in `seen_numbers`?	Action	`seen_numbers`
0	2	`9 - 2 = 7`	No (map is empty)	Add `2: 0` to `seen_numbers`	`{2: 0}`
1	7	`9 - 7 = 2`	Yes (2 is in map, at index 0)	Return `[seen_numbers[2], 1]` which is `[0, 1]`	(Function exits)

Boom! We found it on the second step. Much faster than checking 2 with 7, 11, 15 and then 7 with 11, 15, etc.

💻 The Code

Here's the Python implementation of our approach:

from typing import List

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        # Initialize an empty hash map (Python dictionary)
        # It will store numbers we've seen and their indices: {number: index}
        hashmap = {} 

        # Iterate through the array 'nums' along with their indices
        for i, num in enumerate(nums):
            # Calculate the 'complement' needed to reach the target
            complement = target - num

            # Check if this 'complement' is already in our hash map
            if complement in hashmap:
                # If yes, we found the pair!
                # The index of the complement is hashmap[complement]
                # The index of the current number is 'i'
                return [hashmap[complement], i]

            # If the complement was NOT found, it means the current 'num'
            # is not the second part of a pair with any number we've seen yet.
            # So, we add the current 'num' and its 'index' to the hash map,
            # so future numbers can check against it.
            hashmap[num] = i

        # This line is technically unreachable due to the problem constraint
        # "Only one valid answer exists." meaning we'll always return inside the loop.
        # However, for completeness in a real-world scenario, you might raise an error
        # or return an empty list if no solution were guaranteed.
        return []

⏱️ Time & Space Complexity Analysis

Understanding how efficient our code is crucial for competitive programming and good software design.

Time Complexity: O(N)
- We iterate through the nums array once.
- Inside the loop, operations like calculating the complement, checking if an element in a hash map, and adding an element to a hash map (hashmap[num] = i) all take, on average, constant time (O(1)).
- Since we do a constant amount of work for each of the N elements, the total time complexity is O(N). This is fantastic! It means if the list doubles in size, the time to solve it roughly doubles, which is very efficient.
Space Complexity: O(N)
- In the worst-case scenario, our hash map hashmap might end up storing almost all the numbers from the nums array and their indices. This would happen if the two numbers that sum to the target are the very last two numbers in the array.
- Therefore, the space used by the hash map grows proportionally to the number of elements in nums. So, the space complexity is O(N).

This O(N) time and O(N) space solution is a significant improvement over the brute-force O(N^2) time complexity!

🎯 Key Takeaways

Hash Maps are Your Friends: When you need to quickly check if an element exists or retrieve its associated value (like an index), hash maps (dictionaries in Python) are incredibly powerful. They offer average O(1) lookups and insertions.
The "Complement" Pattern: For problems asking you to find pairs that sum to a target, thinking about the complement (target - current_number) can often lead to an efficient solution using a hash map.
Optimize Beyond Brute Force: Always consider simpler, less efficient solutions first (like brute force) to understand the problem, then challenge yourself to find more optimized approaches. O(N^2) often becomes O(N) with the right data structure.
Read Constraints Carefully: "Exactly one solution" and "cannot use the same element twice" simplify the problem by removing edge cases you might otherwise need to handle.

Congratulations! You've just conquered LeetCode's "Two Sum" problem using an efficient, industry-standard approach. This problem is a foundational building block, and mastering it sets you up for success in many more algorithmic challenges. Keep practicing, keep learning, and happy coding! 🚀

Author Account: NavyaSree_14
Time Published: 2026-05-16 16:21:00