Solving the ‘Two Sum Problem’ on LeetCode — Python Solutions Walkthrough

Image Source

Introduction

In this post, we will delve into three diverse solutions to the Two Sum Problem in Python, thoroughly evaluating their time and space complexity to aid in comprehending the most optimal approach. A detailed, step-by-step explanation with commented code for each solution is provided to offer deeper insights and clarity after the conclusion. This guide ensures a robust understanding of the varied methods available, allowing for an informed and confident selection based on your specific needs and the nature of the dataset at hand.

Problem Description

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

Python Function Signature:

def twoSum(self, nums: List[int], target: int) -> List[int]:

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]

Solution 1: Brute Force Approach

Explanation

In this approach, we iterate through the entire list, and for each element, we iterate through the remaining elements to find a pair that sums up to the target.

Python Code:

class Solution(object):
  def twoSum(self, 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 []

Time Complexity: O(n²), In the brute force approach, there are two nested loops. The outer loop runs ’n’ times, and for each iteration of the outer loop, the inner loop runs ‘n-i’ times, where ‘i’ is the current iteration of the outer loop. This behavior results in a time complexity of O(n²), as each element is compared with every other element in the array.

Space Complexity: O(1), This approach does not require any additional data structures, so the space complexity is constant. The same input array is used for checking the elements, and no extra space that grows with input size is used.

Solution 2: Two-Pass Hash Table

Explanation

We use a dictionary to reduce the time complexity. First, we add each element and its index to a dictionary. Then, we iterate through the array again and check if each element’s complement (target — element) exists in the dictionary.

Python Code:

class Solution(object):
  def twoSum(self, nums, target):
    numMap = {}
    for i, num in enumerate(nums):
        numMap[num] = i
    for i, num in enumerate(nums):
        complement = target - num
        if complement in numMap and numMap[complement] != i:
            return [i, numMap[complement]]
    return []

Time Complexity: O(n), In the Two-Pass Hash Table Approach, the array is iterated over twice. In the first pass, each element is added to a hash map, taking O(n) time. In the second pass, for each element, it checks whether its complement exists in the hash map, also taking O(n) time. Even though the array is traversed twice, the time complexity remains O(n) as these operations are sequential, not nested.

Space Complexity: O(n), A hash map is used to store the elements of the array along with their indices. The space required for the hash map grows linearly with the number of elements in the array, resulting in a space complexity of O(n).

Solution 3: One-Pass Hash Table

Explanation

This approach optimizes the Two-Pass Hash Table Approach by only making one iteration through the array.

Python Code:

class Solution(object):
    def twoSum(self, nums, target):
      numMap = {}
      for i, num in enumerate(nums):
          complement = target - num
          if complement in numMap:
            return [numMap[complement], i]
          numMap[num] = i
      return []

Time Complexity: O(n), This approach iterates over the array only once, and for each element, it checks whether its complement exists in the hash map. The insertion and lookup time for a hash map is O(1) on average, so the overall time complexity for traversing the array once is O(n).

Space Complexity: O(n), Similar to the Two-Pass Hash Table Approach, a hash map is used to store the elements and their indices. The space complexity is O(n) as the space required for the hash map grows with the number of elements in the array.

Conclusion and Comparison

In unraveling the Two Sum problem, three different strategies were extensively examined, each holding its unique advantages and limitations.

• Brute Force Approach: This method, although straightforward, tends to be inefficient for large datasets due to its O(n²) time complexity. The simplicity of this method might be attractive for smaller datasets, and when the execution time is not a critical factor.
• Two-Pass Hash Table Approach: This strategy significantly improves performance by utilizing a hash table, bringing the time complexity down to O(n). It stands as a more efficient alternative for larger datasets compared to the Brute Force Approach, albeit involving a bit more complexity in implementation.
• One-Pass Hash Table Approach: This is the most time-efficient option among the three, with O(n) time complexity but with a single pass over the dataset. It’s especially advantageous for vast datasets, ensuring both speed and efficiency in finding the two numbers that sum up to the target value.

Final Thoughts

The choice among these methods should be a careful consideration of both the size of the dataset and the permissible trade-offs between time and space complexity.

• For modest datasets where time complexity is not a pressing issue, the Brute Force Approach might suffice.
• The Two-Pass Hash Table Approach emerges as a balanced solution, providing enhanced time efficiency with a straightforward implementation.
• The One-Pass Hash Table Approach, however, is the ultimate choice for handling larger datasets, where execution time is crucial. It guarantees optimal performance and efficient resource utilization, ensuring the task is accomplished swiftly without unnecessary resource expenditure.

For a majority of real-world scenarios where datasets can be substantial and execution time paramount, the One-Pass Hash Table Approach often emerges as the most pragmatic and efficient solution, striking a harmonious balance between time complexity, space usage, and implementation complexity.

1. Official Python Documentation
2. Big O Cheat Sheet
3. Hash Table explanation

Thank you for reading! If you find this guide helpful, please consider highlighting, clapping, responding or connecting with me on Twitter/X as it’s very appreciated!

Also check out my other Leetcode Walkthrough Lists:

• Palindrome Number Problem

Step-by-Step Explanations with Code Comments

Solution 1: Brute Force Approach with Comments

class Solution(object):
  def twoSum(self, nums, target):
    # Step 1: Iterate over the numbers in the array.
    for i in range(len(nums)):
        # Step 2: For each number, iterate over the rest of the numbers in the array.
        for j in range(i+1, len(nums)):
            # Step 3: Check if the current two numbers add up to the target.
            if nums[i] + nums[j] == target:
                return [i, j]
    # Step 4: If no such pair is found, return an empty list.
    return []

• Step 1: The outer loop iterates over the numbers in the list.
• Step 2: The inner loop iterates over the rest of the numbers for each number from the outer loop.
• Step 3: If a pair sums up to the target, their indices are returned. Step 4: If no such pair is found, an empty list is returned.

Solution 2: Two-Pass Hash Table Approach with Comments

class Solution(object):
  def twoSum(self, nums, target):
    # Step 1: Create a dictionary to store numbers and their indices.
    numMap = {}
    # Step 2: Add each number and its index to the dictionary.
    for i, num in enumerate(nums):
        numMap[num] = i
    # Step 3: Check for each number, if its complement exists in the dictionary.
    for i, num in enumerate(nums):
        complement = target - num
        # Ensure the complement is not the number itself.
        if complement in numMap and numMap[complement] != i:
            # Step 4: If the complement exists, the indices are returned.
            return [i, numMap[complement]]
    # Step 5: If no two numbers sum up to the target, return an empty list.
    return []

• Step 1: A dictionary is created to store numbers and their indices.
• Step 2: Each number and its index are added to the dictionary.
• Step 3: For each number, it checks if its complement exists in the dictionary (ensuring it’s not the number itself).
• Step 4: If the complement exists, the indices are returned, otherwise, move to the next iteration.
• Step 5: If no pair sums up to the target, an empty list is returned.

Solution 3: One-Pass Hash Table Approach with Comments

class Solution(object):
  def twoSum(self, nums, target):
    # Step 1: Again, create a dictionary to store numbers and their indices.
    numMap = {}
    # Step 2: During iteration over the numbers, the complement is calculated for each number.
    for i, num in enumerate(nums):
        complement = target - num
        # Step 3: It checks if the complement exists in the dictionary. If so, the indices are returned.
        if complement in numMap:
            return [numMap[complement], i]
        # Step 4: Otherwise, the current number and its index are added to the dictionary.
        numMap[num] = i
    # Step 5: If no pair sums up to the target, return an empty list.
    return []

• Step 1: A dictionary is created to store numbers and their indices.
• Step 2: During iteration over the numbers, the complement is calculated for each number.
• Step 3: It checks if the complement exists in the dictionary. If so, the indices are returned.
• Step 4: Otherwise, the current number and its index are added to the dictionary.
• Step 5: If no pair sums up to the target, an empty list is returned.