Vansh Aggarwal

Posted on May 16

LeetCode Solution: 1. Two Sum

#leetcode #dsa #programming #tutorial

Your First LeetCode Journey: Conquering the Classic Two Sum Problem!

Hey everyone! 👋 NavyaSree_14 here, excited to kick off our coding adventure with LeetCode's most famous warm-up challenge: Two Sum. If you've just started your DSA journey, this problem is a fantastic stepping stone. It's simple to understand, yet introduces a powerful optimization technique that's vital for competitive programming and interviews.

Let's dive in!

Problem Explanation

Imagine you're at a treasure hunt. You have a list of numbers, let's call it nums, and a specific "target" number you're looking for. Your mission? Find two different numbers in nums that add up exactly to target. Once you find them, you need to tell us their positions (their "indices") in the original list.

Important Notes:

There will always be exactly one pair of numbers that sums to the target. No need to worry about multiple answers or no answer!
You can't use the same number twice. If nums[0] is part of the pair, you can't use nums[0] again as the second number.
The order of the indices you return doesn't matter. [0, 1] is the same as [1, 0].

Let's look at some examples:

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 indices: 0 and 1.

Example 2:

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

See? Simple enough!

Intuition: The "Aha!" Moment 💡

How would you solve this manually? You'd probably pick a number, say 2, and then look through the rest of the list for 7 (because 9 - 2 = 7). If you find 7, great! If not, you move to the next number, say 7, and look for 2 (9 - 7 = 2), and so on.

This "pick one, then search the rest" approach works, but it can be slow if the list is very long. For every number you pick, you might have to scan almost the entire remaining list. This is what we call a brute-force approach, and its time complexity is O(n²), which isn't ideal for large inputs.

The "aha!" moment comes when you realize: Can I avoid repeatedly scanning the list?

Instead of searching for the complement (the target - current_num) in the rest of the array, what if I could instantly know if I've seen that complement before, and if so, what its index was?

This is where hashmaps (or dictionaries in Python) shine! A hashmap lets you store key-value pairs and quickly check if a key exists, and retrieve its value, usually in O(1) (constant) time on average.

So, the new intuition is: As I iterate through the numbers, for each number, I calculate what its "partner" (complement) would need to be. Then, I quickly check if I've already encountered that partner in my journey so far.

Approach: Step-by-Step Logic

We'll use a single pass through the array, leveraging a hashmap (dictionary in Python) to keep track of numbers we've already processed and their indices.

Initialize an empty hashmap: Let's call it num_map. This map will store numbers as keys and their indices as values. hashmap = {number: index}.
Iterate through the nums array: We need both the index (i) and the value (num) of each element.
For each num:
- Calculate the complement: This is the value we need to find to sum up to target. So, complement = target - num.
- Check if the complement is already in our num_map:
  - If YES: Fantastic! We've found our pair! The complement was encountered earlier, and its index is num_map[complement]. The current number's index is i. We return [num_map[complement], i].
  - If NO: The complement isn't in our num_map yet. This means the current num doesn't form a pair with any number we've seen so far. So, we add the current num and its index i to num_map. This way, num can act as a complement for a future number we encounter. num_map[num] = i.
Why does this work? Because we are guaranteed exactly one solution. Once we find the pair, we return immediately.

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

Iteration	`i`	`num`	`complement` (`target - num`)	`num_map` (before check)	`complement` in `num_map`?	Action	`num_map` (after action)	Output
1	0	2	7	`{}`	No	Add `2:0`	`{2:0}`
2	1	7	2	`{2:0}`	Yes	Return `[num_map[2], 1]`		`[0,1]`

Boom! We found it in just two steps.

Code

from typing import List

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

        # Iterate through the input list 'nums' using enumerate
        # to get both the index 'i' and the value 'num'
        for i, num in enumerate(nums):
            # Calculate the 'complement' needed to reach the target
            # complement = target - current_num
            complement = target - num

            # Check if this 'complement' already exists in our hashmap.
            # If it does, it means we've seen its partner before!
            if complement in hashmap:
                # We found the two numbers!
                # The index of the 'complement' is stored in hashmap[complement]
                # The index of the current 'num' is 'i'
                return [hashmap[complement], i]

            # If the complement is NOT in the hashmap,
            # it means the current 'num' doesn't form a pair with any
            # number encountered *so far*.
            # So, we add the current 'num' and its index to the hashmap.
            # This makes it available as a 'complement' for future numbers.
            hashmap[num] = i

        # The problem guarantees that exactly one solution exists,
        # so this line will theoretically never be reached.
        # However, for completeness in a real-world scenario, you might
        # raise an error or return an empty list if no solution was found.
        # return []

Time & Space Complexity Analysis

Understanding how efficient your solution is, is crucial!

Time Complexity: O(n)

We iterate through the nums list exactly once.
Inside the loop, operations like calculating the complement, checking if an element is in the hashmap, and adding an element to the hashmap (hashmap[num] = i) all take, on average, O(1) (constant) time.
Since we perform these O(1) operations n times (where n is the length of nums), the total time complexity is n * O(1), which simplifies to O(n).
This is a significant improvement over the brute-force O(n^2) approach!

Space Complexity: O(n)

In the worst-case scenario, we might have to store all n elements from the nums array into our hashmap. This happens if the target pair is at the very end of the array, or if the complement is always found after the current num is added.
Therefore, the space required by the hashmap can grow up to n elements, making the space complexity O(n).

This is a classic time-space trade-off: we use extra space (the hashmap) to achieve a much faster time complexity.

Key Takeaways

Hashmaps are your friends! They are incredibly powerful data structures for quick lookups and can often transform O(n^2) problems into O(n) problems.
Think about complements: Many "find a pair" or "find a sum" problems can be reframed as finding a complement.
One pass is often better than two: If you can achieve the result in a single iteration by storing necessary information, it's usually more efficient.
LeetCode #1 is foundational: Master this concept, and you're well on your way to tackling more complex problems!

Keep practicing, and don't be afraid to experiment with different approaches. Happy coding!

Author Account: NavyaSree_14 | Published: 2026-05-16 16:37:57

DEV Community