LeetCode 1 - Two Sum · codetosoul

The task is to pick two values from an array whose sum matches the target and return their indices. It is an Easy problem, but it is useful for comparing brute force pair checking with a hash map lookup for the needed value.

Problem link and explanation

Problem link: 1. Two Sum
Summary: Given an integer array nums and an integer target, return two indices whose values add up to target.

For example:

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

The values 2 and 7 add up to 9, so the answer is [0, 1]. The same element cannot be used twice, and the problem assumes that exactly one answer exists.

The most direct thought is to check every pair. Pick one value, compare it with the values after it, and return the pair when the sum matches the target. That works, but it repeats a lot of comparisons as the input grows. To reduce that repetition, I need a fast way to answer this question: have I already seen the other value I need?

Approach

1. Brute force pair search

The most direct solution is to use nested loops and check every possible pair. Fix the first index, scan the later indices, and check whether the two values add up to the target.

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]

        return []

This uses no additional data structure, so the space complexity is O(1). The cost is time. With n elements, the number of possible pairs can grow close to n², so the time complexity is O(n²).

Brute force comes to mind naturally because the condition is simple: check whether two values add up to the target. The implementation is immediate, but the approach remembers nothing useful from earlier comparisons, so it keeps scanning the array for the value it needs.

2. Two-pass hash map

To reduce the repeated search, I can store where each value appears. The first pass builds a hash map from value to index.

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        seen: dict[int, int] = {}

        for i in range(len(nums)):
            seen[nums[i]] = i

        for i in range(len(nums)):
            complement = target - nums[i]
            if complement in seen and i != seen[complement]:
                return [seen[complement], i]

        return []

The key idea is the complement. If the current value is nums[i], the value I need with it is target - nums[i]. If that value exists in the hash map, I can return the two indices immediately.

This scans the array twice, so the raw work is close to 2n. In Big-O notation, the constant factor is ignored, so the time complexity is still O(n). The trade-off is memory: the hash map stores values and indices, so the space complexity is O(n).

The condition that the same element cannot be used twice also matters. Even if the complement exists in the map, I still need to check that it is not the current index. That is what i != seen[complement] handles.

3. One-pass hash map

After writing the two-pass version, the next question is whether the separate build step is necessary. I can scan from left to right, check whether the complement has already appeared, and only then store the current value for future elements.

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        seen: dict[int, int] = {}

        for i in range(len(nums)):
            complement = target - nums[i]
            if complement in seen:
                return [seen[complement], i]

            seen[nums[i]] = i

        return []

This checks the complement before inserting the current value. Because of that order, the current index is not in seen yet, and seen only contains values from earlier positions. The same-index problem disappears without an explicit index comparison.

The time complexity is still O(n), and the space complexity is still O(n). Compared with the two-pass version, the Big-O result is the same, but the control flow is simpler because the search and insert happen in one pass.

Complexity analysis

1. Brute force

Time complexity: O(n²)
- It may check every pair of elements, so the number of comparisons grows quadratically.
Space complexity: O(1)
- It only uses index variables and no additional data structure.

2. Two-pass hash map

Time complexity: O(n)
- It scans the array twice, but 2n is simplified to O(n) in Big-O notation.
Space complexity: O(n)
- It stores values and indices in a hash map.

3. One-pass hash map

Time complexity: O(n)
- It handles complement lookup and insertion while scanning the array once.
Space complexity: O(n)
- In the worst case, it stores values seen so far before finding the answer.

Optimized code

The one-pass hash map version is the most natural final solution for this problem. It checks whether the needed complement has already appeared, and if not, stores the current value as a candidate for later elements.

from typing import List

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        seen: dict[int, int] = {}

        for i in range(len(nums)):
            complement = target - nums[i]
            if complement in seen:
                return [seen[complement], i]

            seen[nums[i]] = i

        return []

Summary and reflection

This problem is a good example of why a hash map is useful. Brute force is simple because it directly checks two values at a time, but it repeatedly searches for the value it needs. With a hash map, I can check the complement in average O(1) time and reduce the time complexity from O(n²) to O(n).

Moving from the two-pass version to the one-pass version changed more than the loop count. By checking the complement before storing the current value, the code naturally avoids using the same index twice. The core of the problem is not searching for both numbers from scratch, but keeping enough state so that once I see one number, I can find the other one quickly.