Problem Definition

LeetCode Link: 1. Two Sum

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]

Example 3:

Input: nums = [3,3], target = 6
Output: [0,1]

Constraints:

  • 2 <= nums.length <= 104
  • -109 <= nums[i] <= 109
  • -109 <= target <= 109
  • Only one valid answer exists.

Thought Process

At first glance, a brute force solution might be the simplest to think of: try every pair of elements and check if they sum up to the target. However, that approach takes time proportional to O(n^2), which might be too slow for large arrays.

To solve the problem more efficiently, we must think about ways to quickly check if we have seen a number that can complement the current element to reach the target. Data structures like hash maps (in Python, dictionaries) and sets are excellent for constant-time lookups, allowing us to solve the problem in an average of O(n) time.

We’ll explore multiple approaches:

  1. Using a Dictionary (Hash Map): This is the most commonly known efficient solution.
  2. Using a Set: Similar idea, but slightly different mechanics.
  3. Using Two Pointers (after sorting): Useful if we can sort the array, though this changes the original indices.
  4. Brute Force: The simplest approach, mostly for understanding and completeness.

Solution 1: Using a Dictionary (Hash Map)

How It Works

  • We know target = x + y. For each element x, we check if y = target - x has already been seen.
  • As we iterate through the array, we store elements and their indices in a dictionary. The key is the element’s value, and the value is the element’s index.
  • Before inserting a new element, we check if target - current_element is in the dictionary. If it is, we’ve found our pair.

Code Explanation

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        records = dict()  # Dictionary to store {value: index}

        for index, value in enumerate(nums):
            # Check if the complement (target - value) exists in records
            complement = target - value
            if complement in records:
                # If it does, we have found our pair
                return [records[complement], index]
            
            # Otherwise, record the current element with its index
            records[value] = index

        return []

Step-by-Step:

  1. Initialize an empty dictionary records.
  2. Loop through the list with an index:
    • For each value, compute complement = target - value.
    • If complement is found in records, return [records[complement], current_index].
    • If not, add value to records with records[value] = current_index.
  3. If no pair found (though the problem guarantees one), return an empty list.

Complexity Analysis

  • Time Complexity: O(n), because each element is inserted and looked up in a dictionary once on average.
  • Space Complexity: O(n), for storing the dictionary of up to n elements.

Solution 2: Using a Set

How It Works

  • Instead of storing index-value pairs directly, we can start with a simpler structure: a set.
  • As we traverse the list, for each element x, we check if target - x is in the set.
  • If it is, we know we’ve found a pair that sums up to target.
  • One caveat: once we find a complement, we still need to return both indices. We handle this by using the index() method to find the positions after we confirm a match.

Code Explanation

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        seen = set()  # Will hold the values we have encountered

        for i, num in enumerate(nums):
            complement = target - num
            if complement in seen:
                # Find indices for the pair
                return [nums.index(complement), i]
            seen.add(num)

        return []

Step-by-Step:

  1. Create an empty set seen.
  2. Iterate through nums with index i and element num.
  3. Compute complement = target - num.
  4. Check if complement is in seen:
    • If yes, find the index of complement in nums using nums.index(complement) and return those two indices.
    • If not, add num to seen.

Note: This approach may have a slight performance drawback due to nums.index() calls, which are O(n). For large arrays, it’s less optimal than the dictionary approach that already stores indices.

Complexity Analysis

  • Time Complexity: O(n^2) in the worst case due to nums.index() inside the loop. If we rely solely on a set, we don’t directly store indices, causing an extra search.
  • Space Complexity: O(n) for the set.

Solution 3: Using Two Pointers (After Sorting)

How It Works

  • Sort the array while keeping track of the original indices (this requires storing pairs of (value, original_index)).
  • Use a left pointer at the start and a right pointer at the end of the sorted list.
  • If nums_sorted[left] + nums_sorted[right] == target, we’re done.
  • If the sum is less than target, move left pointer to the right (to increase the sum).
  • If the sum is greater than target, move right pointer to the left (to decrease the sum).
  • After we find the pair, we map back to the original indices.

Important Note: Sorting changes the original order. To return the correct original indices, you must store the original indices before sorting.

Code Explanation

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        # Pair each element with its index and then sort by the element value
        indexed_nums = list(enumerate(nums))
        indexed_nums.sort(key=lambda x: x[1])
        
        left = 0
        right = len(indexed_nums) - 1
        while left < right:
            current_sum = indexed_nums[left][1] + indexed_nums[right][1]
            if current_sum == target:
                return [indexed_nums[left][0], indexed_nums[right][0]]
            elif current_sum < target:
                left += 1
            else:
                right -= 1

        return []

Step-by-Step:

  1. Create a list of tuples (original_index, value) from nums.
  2. Sort this list by the value.
  3. Initialize two pointers, left at the start, right at the end.
  4. Compute current_sum.
    • If equal to target, return the original indices.
    • If less than target, move left forward.
    • If greater than target, move right backward.
  5. This approach avoids extra space for lookup but does require sorting.

Complexity Analysis

  • Time Complexity: O(n log n) due to sorting.
  • Space Complexity: O(n) for storing the paired list.

Additional Approach: Brute Force

How It Works

  • Check every pair of elements (i, j) to see if they sum to target.
  • Return [i, j] once you find a matching pair.

Code Explanation

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 []

Step-by-Step:

  1. Nested loops go through all possible pairs.
  2. If nums[i] + nums[j] == target, return [i, j].
  3. This ensures correctness but not efficiency.

Complexity Analysis

  • Time Complexity: O(n^2), checking all pairs.
  • Space Complexity: O(1), no extra storage needed.

Key Takeaways

  • Hash Maps (Dictionaries) Are Key: The dictionary-based approach is the most efficient (average O(n) time), making it a go-to solution.
  • Sets for Quick Lookups, But Caution on Indices: Sets allow quick existence checks but don’t store indices by default, forcing you to do extra work to find them later.
  • Two-Pointer Technique Requires Sorting: While elegant, sorting loses the original order, and you must keep track of indices before sorting.
  • Brute Force for Completeness: The brute force method is simple to understand but is inefficient for large inputs.

Overall, the dictionary (hash map) method is the optimal solution for the Two Sum problem in Python.