LeetCode 1: Two Sum Solution in Python – A Step-by-Step Guide

What Is LeetCode 1: Two Sum?

LeetCode 1 challenges you to find two numbers in an array (nums) that add up to a given target number and return their indices (their positions in the array). There’s exactly one pair that works, and you can’t use the same number twice. It’s like searching a list of prices to find two items that exactly match your budget, then noting where they’re located.

Problem Statement

You’re given: 1. nums: A list of integers (e.g., [2, 7, 11, 15]). 2. target: An integer (the sum you need, e.g., 9).

You return: 1. A list of two integers [i, j] where i and j are the indices in nums such that nums[i] + nums[j] = target (e.g., [0, 1]).

Constraints: 1. The array has at least 2 numbers and up to 10,000 (2 <= nums.length <= 10^4). 2. Numbers can be positive, negative, or zero (-10^9 <= nums[i] <= 10^9). 3. The target can be positive, negative, or zero (-10^9 <= target <= 10^9). 4. There’s exactly one valid solution. 5. You can’t use the same number twice (i != j).

Operation Rules

1. What you can do:

• Select any two numbers from nums.
• Check if their sum equals target.
• Return their indices (positions in the array).

2. What you’re looking for:

• Indices i and j where nums[i] + nums[j] = target.
• For example, if nums[0] + nums[1] = target, return [0, 1].

3. Rules to follow:

• Use each number once.
• Indices must be different.
• Only one pair works.

4. Goal:

• Find the indices as efficiently as possible.

Examples

Let’s look at some examples to set the stage:

Example 1:

• Input: nums = [2, 7, 11, 15], target = 9
• Output: [0, 1]
• Explanation:
• We need nums[i] + nums[j] = 9.
• nums[0] = 2, nums[1] = 7.
• 2 + 7 = 9, so return [0, 1].

Example 2:

• Input: nums = [3, 2, 4], target = 6
• Output: [1, 2]
• Explanation:
• We need nums[i] + nums[j] = 6.
• nums[1] = 2, nums[2] = 4.
• 2 + 4 = 6, so return [1, 2].

Example 3:

• Input: nums = [3, 3], target = 6
• Output: [0, 1]
• Explanation:
• We need nums[i] + nums[j] = 6.
• nums[0] = 3, nums[1] = 3.
• 3 + 3 = 6, so return [0, 1].

These examples show we’re hunting for a pair of numbers and their positions. Let’s solve it with the best approach!

Understanding the Problem: Find the Pair

To solve LeetCode 1 in Python, we need to: 1. Locate two numbers:

• Their sum must equal target.

2. Return their indices:

• We need the positions in nums, not the numbers themselves.

3. Follow constraints:

• Array size can be up to 10,000.
• Numbers and target can be positive, negative, or zero.
• Exactly one solution exists.
• Different indices required.

4. Be efficient:

• We want a fast solution for large arrays.

5. Output a list:

• [i, j] where nums[i] + nums[j] = target.

Checking every pair of numbers would work, but it’s like searching a huge library by picking up every book and pairing it with every other book—way too slow. Instead, we’ll use a hash table (a Python dictionary) to make it quick, like having a catalog that tells us instantly if the book we need is on the shelf. Our focus is the hash table solution, which is the best way to go.

Best Solution: Optimized Hash Table Approach

Why This Is the Best Solution

The hash table approach is the best because it solves the problem in O(n) time—we only need to look at each number in the array once. It uses a dictionary to store numbers we’ve seen along with their indices, letting us check for the number we need in a split second. It’s like being a librarian with a magical catalog: as you pick up a book, you instantly know if the other book you need is already listed. This is way faster than checking pairs, especially for big arrays, and it’s still simple once we break it down.

What We’re Doing (Big Picture)

We’re going to walk through the array, number by number, like checking books on a shelf. For each number:

• We figure out what other number we need to hit target.
• We check our “catalog” (dictionary) to see if we’ve already seen that other number.
• If we have, we’ve found the pair and can return their indices.
• If not, we add the current number to the catalog and keep going.

Why this makes sense:

• If we’re looking at a number nums[i] and want nums[i] + something = target, then something = target - nums[i].
• The dictionary acts like a memory bank: it remembers every number we’ve seen and where it was.
• Since there’s exactly one solution, we’ll find the pair before we reach the end of the array.
• By checking the dictionary before adding the current number, we avoid mistakes like pairing a number with itself.

How It Works (Detailed Logic)

Let’s imagine we’re librarians searching for two books whose page counts add to target. Here’s our plan: 1. Create a catalog:

• Start with an empty dictionary to store number: index pairs.
• For example, if we see 7 at index 1, we’ll store 7: 1.

2. Check each book:

• Go through the array one number at a time, keeping track of the index.

3. Find the missing book:

• For the current number nums[i], calculate complement = target - nums[i].
• This complement is the other number we need to make target.
• For example, if target = 9 and nums[i] = 2, we need 9 - 2 = 7.

4. Look in the catalog:

• Check if complement is in the dictionary.
• If it is, we’ve found the pair! The dictionary gives us the index of complement, and we have the current index i.

5. Update the catalog:

• If complement isn’t there, add nums[i]: i to the dictionary.
• This way, future numbers can find nums[i] if they need it.

6. Move to the next book:

• Go to the next number and repeat the process.

7. Return the shelf positions:

• When we find the pair, return [index_of_complement, i] as the answer.

Why we check before adding:

• Suppose target = 6 and nums[i] = 3. If we added 3: i first, we might think 3 pairs with itself, but we need another 3 at a different index.
• Checking first ensures we only pair nums[i] with a number we saw earlier, respecting the “different indices” rule.

Why it’s efficient:

• The dictionary is like a super-fast lookup system—it takes almost no time to check if a number exists.
• We only go through the array once, so even if there are 10,000 numbers, we’re not wasting effort.
• Since there’s one solution, we’ll find it without extra work.

Step-by-Step Example

Let’s solve nums = [2, 7, 11, 15], target = 9 together, like we’re librarians flipping through our catalog. We’ll go slow and explain every move.

1. Set up the catalog:

• Create an empty dictionary: seen = {}.
• This is our memory for numbers and their shelf positions (indices).
• Why: We need somewhere to store numbers we’ve seen to check them later.

2. First number (index 0):

• Look at nums[0] = 2.
• Calculate the number we need: complement = target - nums[0] = 9 - 2 = 7.
• Check the dictionary: Is 7 in seen?
• seen = {}, so no, we haven’t seen 7.
• Add the current number to the dictionary: seen[2] = 0.
• This means “number 2 is at index 0.”
• Now seen = {2: 0}.
• Why: We’re asking, “Have I seen a 7 that would pair with this 2?” Since we haven’t, we note down 2 for later numbers to find.

3. Second number (index 1):

• Look at nums[1] = 7.
• Calculate the number we need: complement = 9 - 7 = 2.
• Check the dictionary: Is 2 in seen?
• seen = {2: 0}, so yes! We found 2 at index 0.
• We’ve got the pair:
• nums[0] = 2 (at index 0, from seen[2]).
• nums[1] = 7 (at current index 1).
• Let’s verify: 2 + 7 = 9, which matches target.
• Return [seen[2], 1] = [0, 1].
• Why: Finding 2 in the dictionary means 2 + 7 = 9, and we know their positions: 2 at index 0, 7 at index 1.

4. Stop:

• We found the solution, so we don’t need to check nums[2] = 11 or nums[3] = 15.
• Output: [0, 1].
• Why: The problem guarantees one solution, and we found it, so we’re done.

Let’s try another: nums = [3, 2, 4], target = 6: 1. Initialize:

• seen = {}.
• Why: Start with a clean catalog.

2. Index 0: nums[0] = 3:

• complement = 6 - 3 = 3.
• Is 3 in seen? No (seen = {}).
• Add seen[3] = 0.
• Now seen = {3: 0}.
• Why: We need another 3, but haven’t seen it, so we record this 3.

3. Index 1: nums[1] = 2:

• complement = 6 - 2 = 4.
• Is 4 in seen? No (seen = {3: 0}).
• Add seen[2] = 1.
• Now seen = {3: 0, 2: 1}.
• Why: We need a 4, but it’s not there, so we save 2.

4. Index 2: nums[2] = 4:

• complement = 6 - 4 = 2.
• Is 2 in seen? Yes (seen[2] = 1).
• Pair found:
• nums[1] = 2 (at index 1).
• nums[2] = 4 (at index 2).
• Verify: 2 + 4 = 6, which matches.
• Return [seen[2], 2] = [1, 2].
• Why: We found 2 in our catalog, meaning 2 + 4 = 6, and we have their indices.

5. Output: [1, 2].

One more for clarity: nums = [3, 3], target = 6: 1. Initialize: seen = {}. 2. Index 0: nums[0] = 3:

• complement = 6 - 3 = 3.
• Is 3 in seen? No.
• Add seen[3] = 0.
• seen = {3: 0}.

3. Index 1: nums[1] = 3:

• complement = 6 - 3 = 3.
• Is 3 in seen? Yes (seen[3] = 0).
• Pair found: nums[0] = 3, nums[1] = 3.
• Verify: 3 + 3 = 6.
• Return [0, 1].

4. Output: [0, 1].

Why this process clicks:

• Each number we see asks, “Have I seen the number that would complete the sum?”
• The dictionary answers instantly, like a librarian’s catalog.
• We build the catalog as we go, so we’re ready for future checks.
• The “check first, add later” rule prevents us from pairing a number with itself.

Code with Detailed Explanation

Here’s the Python code, with comments explaining every line so you know exactly what’s happening and why:

Copy codefrom typing import List

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        # Create an empty dictionary to store numbers and their indices
        # Why: It’s our catalog to quickly find numbers we’ve seen before
        seen = {}

        # Loop through the array, keeping track of each number’s index
        # Why: We need to check every number to find the pair
        for i in range(len(nums)):
            # Calculate the number we need to reach target
            # Why: If nums[i] + complement = target, complement is the other number
            complement = target - nums[i]

            # Check if we’ve seen the complement in our dictionary
            # Why: If it’s there, we’ve found the two numbers that sum to target
            if complement in seen:
                # Return the indices: complement’s index and current index
                # Why: seen[complement] gives the earlier number’s position
                return [seen[complement], i]

            # Add the current number and its index to the dictionary
            # Why: So future numbers can find nums[i] if they need it
            seen[nums[i]] = i

        # We don’t need a return here because the problem guarantees a solution

How to follow the code: 1. Set up:

• seen = {} is like opening a new notebook.

2. Loop:

• for i in range(len(nums)) goes through each “book” (number).

3. Calculate:

• complement = target - nums[i] asks, “What page count do I need?”

4. Check:

• if complement in seen looks in the notebook for that page count.

5. Return:

• return [seen[complement], i] gives the shelf positions if found.

6. Store:

• seen[nums[i]] = i writes down the current book’s details.

How to use it:

• Copy the code into a Python environment (e.g., LeetCode, VS\setminus Code).
• Test with nums = [2, 7, 11, 15], target = 9:
• It returns [0, 1], meaning nums[0] + nums[1] = 2 + 7 = 9.
• Try nums = [3, 2, 4], target = 6:
• Returns [1, 2] for 2 + 4 = 6.
• If you’re curious, add print(seen, complement, i) before the if to see each step:
• For [2, 7], target = 9:
• First: seen = {}, complement = 7, i = 0.
• Second: seen = {2: 0}, complement = 2, i = 1.

Why every line matters:

• Dictionary: Without seen, we’d have to search the array repeatedly.
• Complement: It’s the key to knowing what pairs with nums[i].
• Check first: Ensures we don’t use the same index, keeping i != j.
• Add later: Builds our catalog for future numbers.
• Loop: Covers all numbers until we find the pair.

• Time Complexity:
• We loop through n numbers once.
• Dictionary lookups and inserts are super fast (O(1) on average).
• Total: O(n), meaning it’s quick even for 10,000 numbers.
• Space Complexity:
• The dictionary might store up to n numbers (one per index).
• Total: O(n), a fair trade for speed.

Why It’s So Good

This solution shines because: 1. Speed: O(n) means we’re done in one pass, perfect for big arrays. 2. Clarity: The idea of “find the complement” is simple once you see it. 3. Flexibility: Works for positive, negative, zero, duplicates—everything. 4. Guaranteed: Since there’s one solution, we’ll find it efficiently.

Alternative Solution: Brute-Force Approach

Code

Copy codefrom typing import List

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i in range(len(nums)):
            for j in range(i + 1, len(nums)):
                if nums[i] + nums[j] == target:
                    return [i, j]

Explanation of Code

• Outer loop (for i):
• Iterates through each number in nums, selecting it as the first number.
• Inner loop (for j):
• Checks every number after index i to form a pair, avoiding duplicates (same index).
• Condition (if nums[i] + nums[j] == target):
• Tests if the two numbers add up to target.
• Return (return [i, j]):
• If a match is found, returns the indices of the two numbers.
• What it does:
• Tries every possible pair of numbers until it finds the one that sums to target.
• It’s slow (O(n²) time) because for each number, it checks almost all others, but it’s guaranteed to find the solution since one exists.

Additional Examples and Edge Cases

Let’s test the hash table approach with more cases to solidify it: 1. Duplicates:

• nums = [3, 3], target = 6:
• Index 0: 3, need 3, seen = {}, add seen[3] = 0.
• Index 1: 3, need 3, find seen[3] = 0, return [0, 1].
• Output: [0, 1].

2. Negative numbers:

• nums = [-1, -2, 3, 5], target = -3:
• Index 0: -1, need -2, add seen[-1] = 0.
• Index 1: -2, need -1, find seen[-1] = 0, return [0, 1].
• Output: [0, 1].

3. Zeros:

• nums = [0, 4, 0], target = 0:
• Index 0: 0, need 0, add seen[0] = 0.
• Index 1: 4, need -4, add seen[4] = 1.
• Index 2: 0, need 0, find seen[0] = 0, return [0, 2].
• Output: [0, 2].

4. Large target:

• nums = [1000, 999], target = 1999:
• Index 0: 1000, need 999, add seen[1000] = 0.
• Index 1: 999, need 1000, find seen[1000] = 0, return [0, 1].

The hash table handles all cases because it only cares about sums and indices, not the numbers’ values.

Complexity Breakdown

• Time: O(n):
• One loop through n numbers.
• Dictionary operations (check, add) are O(1).
• Space: O(n):
• Dictionary stores up to n key-value pairs.

Visualizing the Hash Table Approach

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

• Index 0: 2, need 7, catalog = {2: 0}.
• Index 1: 7, need 2, find 2 in catalog, return [0, 1].
• It’s like scanning a shelf and instantly knowing if the book you need is already cataloged.

Common Mistakes to Avoid

1. Pairing with self:

• Don’t add nums[i] to seen before checking complement, or you might match a number with itself.

2. Wrong complement:

• Always use target - nums[i], not something else like nums[i] - target.

3. Missing indices:

• Store indices in seen, not values, since we return positions.

4. Assuming order:

• The pair could be anywhere, so don’t stop early unless you find it.

Key Takeaways

1. Hash Table Power: Dictionaries make lookups lightning-fast.
2. Complement Key: target - nums[i] unlocks the pair.
3. One Pass: O(n) efficiency is perfect for big arrays.
4. Python Simplicity: Dictionaries are your friend—check Python Basics.

Final Thoughts: Find the Pair

LeetCode 1: Two Sum in Python is a delightful puzzle, like finding two books that perfectly match your page count goal. The hash table approach is your magical catalog, making the search quick and satisfying. Want more array adventures? Try LeetCode 15: 3Sum or LeetCode 167: Two Sum II. Ready to find some pairs? Head to LeetCode 1 and start today!