DEV Community

Aryan Subudhi
Aryan Subudhi

Posted on

LeetCode Solution: 1. Two Sum

#leetcode #dsa #programming #tutorial

Cracking LeetCode 1: Two Sum - Your First Step into Algorithm Mastery!

Hey everyone! 👋 aryan-subudhi here, ready to dive into what's often the very first problem many of us encounter on our LeetCode journey: Two Sum. Don't let its "easy" tag fool you; this problem is a fantastic introduction to fundamental algorithmic thinking, data structures, and the crucial concept of time complexity. If you're just starting out, you're in for a treat!

2. Problem Explanation: The Mission, Should You Choose To Accept It!

Imagine you're given a list of numbers, let's call it nums, and a specific target number, target. Your mission, should you choose to accept it, is to find two different numbers within that nums list that add up precisely to target. Once you find them, you don't return the numbers themselves, but their positions (indices) in the original list.

Here's the lowdown:

  • Input:
    • nums: An array (or list in Python) of integers.
    • target: A single integer.
  • Output:
    • A list (or array) of two integers, representing the indices of the two numbers that sum up to target.
  • Key Guarantees/Constraints:
    • There will always be exactly one valid solution. No need to worry about multiple pairs or no pairs at all!
    • You can't use the same number twice (i.e., you need two distinct elements from the array).
    • The answer can be returned in any order (e.g., [0, 1] or [1, 0] are both fine).

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

Example 1:

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

We need to find two numbers in [2, 7, 11, 15] that sum to 9.

  • 2 + 7 = 9 Bingo!
  • 2 is at index 0.
  • 7 is at index 1.
  • So, the output is [0, 1]. Simple, right?

3. Intuition: Thinking Through the Problem (From Simple to Smart!)

Okay, so we need to find two numbers. How would a human do it? You'd probably start picking numbers and seeing if their partners exist.

The "Brute Force" Idea (Our First Thought):

Let's try every possible pair!

  1. Pick the first number (e.g., 2).
  2. Then, go through all the other numbers to see if any of them, when added to 2, equal target (which is 9).
    • 2 + 7 = 9 (Found it!)
    • If not, you'd continue: 2 + 11 = 13 (No), 2 + 15 = 17 (No).
  3. If you didn't find it with 2, you'd move to the next number, 7.
  4. Then, you'd go through all the numbers after 7 (because 7 + 2 is the same as 2 + 7, and we don't want to recheck or use the same element twice).
    • 7 + 11 = 18 (No)
    • 7 + 15 = 22 (No)
  5. And so on...

This approach definitely works! You're guaranteed to find the pair because you check every single combination.

The Catch: While correct, this isn't very efficient for large lists. If nums has N numbers, you're essentially doing N checks for the first number, N-1 for the second, and so on. This looks like N * N operations in the worst case, which we call O(N^2) complexity. For N = 10,000, N^2 is 100,000,000 — that's a lot of operations! Our follow-up question specifically asks for something better than O(N^2).

Towards a Smarter Idea:

Can we be faster? When we pick a number, say num, we know what its "partner" or "complement" should be to reach the target.
complement = target - num

Instead of searching through the rest of the list for this complement (which takes time), what if we could instantly know if we've seen this complement before? This is where a hash map (or dictionary in Python) shines!

4. Approach: The Hash Map Magic! ✨

The optimized approach uses a hash map (often called a dictionary in Python) to store numbers we've seen so far, along with their indices. This allows for very fast lookups.

Here's the game plan:

  1. Initialize an empty hash map (dictionary): Let's call it seen. This seen map will store (number: index) pairs.
  2. Iterate through the nums array: For each num and its index (let's call it i): a. Calculate the complement: complement = target - num. This is the number we need to find to hit our target. b. Check if complement is in seen: * If complement is in seen, it means we've previously encountered the number that, when added to our current num, gives us target. We've found our pair! * The index of the complement is seen[complement], and the index of our current num is i. We return [seen[complement], i]. c. If complement is NOT in seen: This means our current num doesn't complete a pair with any number we've seen so far. So, we add our current num and its index (i) to our seen map: seen[num] = i. This way, if a future number needs this num as its complement, it will find it quickly.
  3. Since the problem guarantees exactly one solution, we know our loop will always find a pair and return.

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

  • seen = {} (empty dictionary)

  1. i = 0, num = 2:

    • complement = target - num = 9 - 2 = 7.
    • Is 7 in seen? No, seen is empty.
    • Add num to seen: seen = {2: 0}.

  2. i = 1, num = 7:

    • complement = target - num = 9 - 7 = 2.
    • Is 2 in seen? YES! seen[2] is 0.
    • We found our pair! The indices are seen[2] (which is 0) and our current i (which is 1).
    • Return [0, 1].

And we're done! Notice how much faster that was than checking every single pair. We only made one pass through the list.

5. Code: The Solution in Action 

class Solution:
    def twoSum(self, nums, target):
        # Initialize an empty hash map (dictionary in Python)
        # to store numbers we've seen and their indices.
        seen = {} 

        # Iterate through the array `nums` with both index `i` and value `num`.
        for i, num in enumerate(nums):
            # Calculate the complement needed to reach the target.
            complement = target - num

            # Check if this complement already exists in our `seen` map.
            # If it does, we've found our pair!
            if complement in seen:
                # Return the index of the complement (from `seen`) and the current index `i`.
                return [seen[complement], i]

            # If the complement wasn't found, store the current number and its index
            # in the `seen` map for future lookups.
            seen[num] = i
Enter fullscreen mode Exit fullscreen mode

6. Time & Space Complexity Analysis: Getting Technical!

Understanding how efficient your code is, is crucial for competitive programming and real-world applications.

Brute Force (Nested Loops) Approach:

  • Time Complexity: O(N^2)
    • We have two nested loops. The outer loop runs N times (for each number). The inner loop runs up to N times for each iteration of the outer loop. This results in approximately N * N operations.
  • Space Complexity: O(1)
    • We don't use any additional data structures that grow with the input size, just a few variables.

Hash Map (Dictionary) Approach:

  • Time Complexity: O(N)
    • We iterate through the nums array exactly once.
    • Inside the loop, calculating the complement is O(1).
    • Checking if a key (complement) exists in a hash map (dictionary) is, on average, O(1).
    • Adding a key-value pair (num: i) to a hash map is, on average, O(1).
    • Since all operations inside the loop are constant time on average, the total time complexity is proportional to the number of elements N, making it O(N). This is significantly better than O(N^2) for large inputs!
  • Space Complexity: O(N)
    • In the worst case, we might need to store all N numbers and their indices in our seen hash map before finding the pair (e.g., if the pair is the last two elements).
    • Therefore, the space used grows linearly with the input size N.

The hash map approach effectively trades space complexity (O(N)) for significantly improved time complexity (O(N)). This is a very common and powerful optimization technique in algorithms!

7. Key Takeaways: What We Learned!

  1. Don't Settle for Brute Force (Always!): While often the easiest to think of, the most straightforward approach isn't always the most efficient. Always consider if there's a faster way.
  2. The Power of Hash Maps: Hash maps (dictionaries) are your best friends for problems requiring fast lookups. They allow you to check for the existence of an element in (average) constant time, O(1), making algorithms much faster.
  3. The Complement Strategy: Many "find a pair" problems can be simplified by thinking about what complement you need for a given num to reach the target.
  4. Time-Space Trade-off: Often, you can improve the time complexity of an algorithm by using extra space (like our hash map). This is a fundamental concept in algorithm design.
  5. Understanding enumerate: In Python, enumerate(nums) is a neat way to get both the index (i) and the value (num) when iterating through a list.

8. Submission Details

Author Account: aryan-subudhi
Publishing Time: 2026-05-25 23:11:39
Title: 1. Two Sum

That's it for Two Sum! I hope this deep dive was helpful and clarified why this seemingly simple problem is so foundational. Keep practicing, and happy coding! 🚀

Top comments (0)