Solving the "Two Sum" Problem: Brute Force, Better, and Optimal Solutions in Python

The "Two Sum" problem is a classic coding interview question frequently encountered in technical interviews. It tests your ability to find two numbers in an array that add up to a specific target. In this blog post, we'll explore three different approaches to solving this problem in Python: the brute force solution, a better solution using hash table, and an optimal solution when the input array is sorted. We'll also discuss their time and space complexities, intuition, and more.

Problem Overview

Given an array of integers nums and an integer target, you need to return the indices of the two numbers in nums 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.

Example 1:

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

• Output: [0, 1]

• Explanation: In this case, the two numbers at indices 0 and 1 (2 and 7) add up to the target value of 9.

Example 2:

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

• Output: [1, 2]

Example 3:

• Input: nums = [3, 3], target = 6

• Output: [0, 1]

Brute Force: Exploring Every Possibility

Overview: The brute force approach involves checking every possible pair of numbers in the array to see if they add up to the target.

Algorithm:

1. Use two nested loops to iterate through the array.

2. The outer loop iterates through each element in the array.

3. The inner loop iterates through the remaining elements to find a pair.

4. Calculate the sum of the current pair of elements.

5. If the sum equals the target, return the indices of the pair.

6. Continue iterating until a valid pair is found or all possibilities are exhausted.

7. If no valid pair is found, return an empty list.

def twoSumBruteForce(nums, target):
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] + nums[j] == target:
                return [i, j]
    return []

Intuition: This approach exhaustively explores all possible pairs of numbers to find the desired sum, much like searching for a needle in a haystack. By systematically checking each pair, we ensure that we don't miss any potential solutions. However, this method can be inefficient for large arrays due to its quadratic time complexity.

Time Complexity: O(n^2) - We have two nested loops that iterate over the entire array, resulting in a quadratic time complexity.

Space Complexity: O(1) - We use a constant amount of space for variables.

Better Solution: Leveraging Hash Table

Two-Pass Hash Table Approach

Overview: In the two-pass hash table approach, we first create a hash table (dictionary) to store the values and their corresponding indices in the input array. Then, we iterate through the array again to check for the existence of the complement (target - current number) in the hash table. This reduces the time complexity to O(n).

Algorithm:

1. Create an empty dictionary (hash table) num_dict to store the numbers and their indices.

2. In the first pass, iterate through the array and add each number to num_dict along with its index.

3. In the second pass, iterate through the array again and for each number, calculate its complement (target - current number).

4. Check if the complement exists in num_dict and ensure it's not the same index as the current number.

5. If the complement is found, return the indices of the pair.

def twoSumTwoPassHashtable(nums, target):
    num_dict = {}

    # First pass: Populate the hashtable with numbers and indices.
    for i, num in enumerate(nums):
        num_dict[num] = i

    # Second pass: Check for complements.
    for i, num in enumerate(nums):
        complement = target - num
        if complement in num_dict and num_dict[complement] != i:
            return [i, num_dict[complement]]

    return []

Intuition: This approach involves two systematic passes through the array. In the first pass, it meticulously records numbers and their positions, building a comprehensive map. In the second pass, it efficiently uses this map to identify pairs, much like preparing for a treasure hunt by marking key locations before swiftly finding the treasure. This approach optimizes time complexity to linear while using additional memory.

Time Complexity: O(n) - We perform two passes through the array, each with a linear time complexity.

Space Complexity: O(n) - In the worst case, we may need to store all elements of the array in the dictionary.

One-Pass Hash Table Approach

Overview: The one-pass hash table approach improves upon the two-pass approach by performing both steps (adding to the hash table and checking for complements) in a single pass through the array.

Algorithm:

1. Initialize an empty dictionary num_dict.

2. Iterate through the array once.

3. For each element, calculate its complement with respect to the target.

4. Check if the complement exists in num_dict.

5. If it does, return the indices of the pair.

6. If not, add the current element to num_dict.

7. If no valid pair is found, return an empty list.

def twoSumOnePassHashtable(nums, target):
    num_dict = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in num_dict:
            return [num_dict[complement], i]
        num_dict[num] = i
    return []

Intuition: This approach leverages a dictionary to keep track of numbers as we iterate through the array, allowing us to find pairs efficiently, similar to marking a trail to follow in a complex maze. This approach optimizes time complexity to linear while using additional memory.

Time Complexity: O(n) - We iterate through the array once, and each lookup or insertion in the dictionary is an O(1) operation on average.

Space Complexity: O(n) - In the worst case, we may need to store all elements of the array in the dictionary.

Optimal Solution: The Sorted Shortcut

Overview: In the world of sorted arrays, we bring out the big guns—a two-pointer approach! If the input array is sorted, we can achieve an even more efficient solution in O(n) time using two pointers.

Algorithm:

1. Initialize two pointers, left and right, at the start and end of the sorted array.

2. Use a while loop to compare the sum of elements pointed to by left and right with the target.

3. If the sum equals the target, return the indices of the pair.

4. If the sum is less than the target, increment left.

5. If the sum is greater than the target, decrement right.

6. Repeat steps 2-5 until a valid pair is found or the pointers meet.

7. If no valid pair is found, return an empty list.

def twoSumOptimal(nums, target):
    left, right = 0, len(nums) - 1
    while left < right:
        curr_sum = nums[left] + nums[right]
        if curr_sum == target:
            return [left, right]
        elif curr_sum < target:
            left += 1
        else:
            right -= 1
    return []

Intuition: This approach capitalizes on the array's sorted nature, efficiently narrowing down our search space, much like taking shortcuts on familiar paths. By using two pointers and adjusting their positions based on the sum of the elements they point to, we can rapidly converge on the correct pair. This approach offers the best time complexity of linear and uses minimal extra space.

Time Complexity: O(n) - We use a two-pointer approach that scans the array once.

Space Complexity: O(1) - We use a constant amount of space for variables.

Conclusion

In this blog post, we've explored three different solutions to the "Two Sum" problem: the brute force approach, a better solution using a hash table, and an optimal solution with sorted input. Each solution has its own time and space complexity characteristics, and understanding these trade-offs is crucial in solving similar coding interview problems.

Whether you're preparing for a technical interview or just looking to improve your problem-solving skills, these approaches provide valuable insights into solving the "Two Sum" problem efficiently. Practice these solutions and experiment with other problem-solving techniques to become a more proficient programmer.

We hope you found this blog post helpful. If you have any questions or comments, please feel free to leave them below. Don't forget to like and share this post if you found it useful, and subscribe for more coding tutorials and problem-solving strategies.

Happy coding!

Additional Information

Python 'dict': Is it a Hashtable or Hashmap?

In Python, the terms "hashtable" and "hashmap" are often used interchangeably because Python's built-in dictionary (dict) data structure is implemented using a hashtable. In other words, when you use a dict in Python, you are essentially using a hashtable.

So, whether you refer to it as a "hashtable" or a "hashmap" in the context of Python, you are talking about the same data structure. It's a key-value store that uses a hash function to map keys to their corresponding values, allowing for efficient lookups, insertions, deletions, and updates based on keys.

Python 'enumerate()'

In Python, the enumerate() function is a built-in function that allows you to iterate through an iterable (such as a list, tuple, or string) while keeping track of both the elements and their corresponding indices. It's a convenient way to loop through a sequence and access both the value and its position in the sequence.

Here's an example of how you can use the enumerate() function in the context of the "Two Sum" problem to illustrate its usage:

# Example: Using enumerate to find the indices of target elements in a list

def twoSum(nums, target):
    num_dict = {}

    # First, use enumerate to create a mapping of elements to their indices
    for i, num in enumerate(nums):
        num_dict[num] = i

    # Iterate through the list again to find the complement
    for i, num in enumerate(nums):
        complement = target - num
        if complement in num_dict and num_dict[complement] != i:
            return [i, num_dict[complement]]

    return []

# Example usage:
nums = [2, 7, 11, 15]
target = 9
result = twoSum(nums, target)
print(result)  # Output: [0, 1] (Indices of elements 2 and 7 that add up to the target 9)