Hommies

Posted on May 16

LeetCode Solution: 1. Two Sum

#leetcode #dsa #programming #tutorial

The OG LeetCode Challenge: Cracking Two Sum with Python!

Hey there, future coding rockstars! 👋

Ever wondered what the very first problem on LeetCode is? It's a true classic, a rite of passage for many, and a fantastic way to introduce fundamental data structures and algorithms. Today, we're diving into Two Sum! Don't let the "easy" tag fool you; mastering this problem helps build crucial problem-solving muscles.

Let's break it down together!

🧐 What's the Problem All About? (Problem Explanation)

Imagine you're given 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 your target.

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

Example Time!

Input: nums = [2, 7, 11, 15], target = 9
Think: Can we find two numbers that sum to 9?
- 2 + 7 = 9! Bingo!
Output: [0, 1] (Because 2 is at index 0, and 7 is at index 1)

Another Example:

Input: nums = [3, 2, 4], target = 6
Think:
- 3 + 2 = 5 (Nope)
- 3 + 4 = 7 (Nope)
- 2 + 4 = 6! Yes!
Output: [1, 2] (2 is at index 1, 4 is at index 2)

Key things to remember:

You'll always find exactly one solution.
You can't use the same number twice (e.g., if nums had 3 and target was 6, you couldn't use the same 3 to make 3+3). If there are two 3s, you use both distinct 3s.

🤔 Your "Aha!" Moment (Intuition)

How would you solve this as a human, without a computer?

You might pick the first number (2 from [2, 7, 11, 15]), then look at every other number to see if it adds up to 9.

2 + 7 = 9 (Found it!)
If not, you'd try 2 + 11, 2 + 15.
If 2 didn't work with any other number, you'd move to the next number (7) and repeat the process.

This is what we call a brute-force approach. It works, but it can be slow for very long lists. For every number, you're looking at almost all other numbers. If there are N numbers, you might do N * N (or N^2) checks in the worst case. Can we do better?

The Smarter Way: What are we really looking for?

Let's say we pick a number from our list, nums[i]. We know we need another number, let's call it complement, such that:

nums[i] + complement = target

This means complement = target - nums[i].

So, for each nums[i] we encounter, we don't need to try every other number. We just need to quickly check if its specific complement exists somewhere else in our list.

How do we check for existence super fast? With a hash map (or a dictionary in Python)! A hash map allows us to store key-value pairs and look up keys almost instantly.

🚀 The Game Plan (Approach)

We'll use a two-pass hash map approach. This means we'll go through our nums list twice.

First Pass: Build the Lookup Table
- We'll create an empty hashmap (a Python dictionary).
- We iterate through nums one time. For each number nums[i] we see, we'll store it in our hashmap along with its index i.
- So, our hashmap will look something like {number: index}.
  - Example nums = [2, 7, 11, 15]:
    - After this pass, hashmap might be: {2: 0, 7: 1, 11: 2, 15: 3}.
Second Pass: Find the Complement
- Now, we iterate through nums again.
- For each number nums[i]:
  - Calculate its complement: complement = target - nums[i].
  - Check if this complement exists as a key in our hashmap.
  - Crucially, we also need to make sure that the index associated with the complement in the hashmap is not the current index i. This prevents us from trying to use the same number twice.
  - If both conditions are met (complement found, and it's a different number), we've found our pair! Return [i, hashmap[complement]].

Because the problem guarantees exactly one solution, we know we'll find our answer and return from the function during this second pass.

💻 Let's Code!

Here's the Python solution implementing the two-pass hash map approach:

from typing import List

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        # Step 1: Initialize a hash map (Python dictionary) to store numbers and their indices
        hashmap = {} 

        # First Pass: Populate the hash map
        # We iterate through the array once to store each number and its index.
        # This makes subsequent lookups much faster.
        for i in range(len(nums)):
            hashmap[nums[i]] = i # Store: {number: index}

        # Second Pass: Find the complement
        # Now, we iterate through the array again. For each number, we calculate
        # what its 'complement' should be to reach the target.
        for i in range(len(nums)):
            complement = target - nums[i]

            # Check if the complement exists in our hash map:
            # - `complement in hashmap`: Is the required complement present in our stored numbers?
            # - `hashmap[complement] != i`: Is the complement not the current number itself (i.e., are their indices different)?
            #   This is important because we can't use the same element twice.
            if complement in hashmap and hashmap[complement] != i:
                # If both conditions are true, we found our pair!
                # Return the index of the current number (i) and the index of its complement.
                return [i, hashmap[complement]]

        # This line should ideally not be reached based on the problem constraints
        # (which state that exactly one solution exists).
        return []

⏰ Space and Time Efficiency (Complexity Analysis)

Understanding how efficient your code is, especially for large inputs, is a core skill!

Time Complexity: O(n)
- The first loop (for i in range(len(nums))) iterates n times to populate the hash map. On average, inserting an element into a hash map takes O(1) time. So, the first pass is O(n).
- The second loop (for i in range(len(nums))) also iterates n times. Inside this loop, calculating the complement is O(1), and looking up an element in a hash map takes O(1) time on average. So, the second pass is also O(n).
- Adding them up, O(n) + O(n) = O(2n), which simplifies to O(n). This is much faster than the O(n^2) brute-force approach!
Space Complexity: O(n)
- In the worst-case scenario, we might have to store all n numbers and their indices in our hashmap. Therefore, the space required grows linearly with the number of elements in the input array.

💡 Key Takeaways

Hash Maps are Your Friends: For problems involving quick lookups or checking for the existence of elements, hash maps (dictionaries) are incredibly powerful. They can transform a slow O(n) lookup into an average O(1) operation!
Think Complements: Many problems can be simplified by rephrasing what you're looking for. Instead of "find two numbers that sum to X", think "for each number, find its 'complement' (X - number)".
Optimize Iterations: While a brute-force approach (nested loops, O(n^2)) might be your first thought, always consider if you can reduce the number of passes or operations using a suitable data structure.

This problem, despite being "easy," introduces you to a fundamental pattern used in many more complex LeetCode challenges. Keep practicing, and you'll be solving harder problems in no time!

Happy coding! ✨

Author Account: p1Hzd8mRM8
Publishing Time: 2026-05-16 22:26:22

DEV Community