Leetcode – Two Sum

The Two Sum problem is one of the most fundamental problems in computer science and serves as a great introduction to problem-solving techniques in data structures and algorithms. It is often used as an interview question for software engineering positions and is the first problem that you encounter on LeetCode. This article will provide an in-depth analysis of the problem, discuss different solution approaches, and illustrate how to implement them in Python.

Problem Statement

LeetCode Problem #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

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

The problem is straightforward: we need to find two indices i and j in the given array such that nums[i] + nums[j] == target.

Now let’s dive into different approaches for solving this problem.

Approach 1: Brute Force

The brute force approach involves two nested loops to check every possible pair of numbers in the array. We will use Python’s built-in range function to generate all possible pairs of indices.

def twoSum(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]

This solution works, but it is inefficient. It has a time complexity of O(n^2) because for each element in the array, we are checking its sum with every other element. This can be very slow for large arrays. Therefore, we need to consider a more efficient approach.

Approach 2: Two-pass Hash Table

The next approach is to use a hash table, also known as a dictionary in Python, to store the numbers in the array and their indices. The basic idea is to make a pass over the array to build the hash table and then make a second pass to find the target pair.

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

This approach has a time complexity of O(n), which is significantly faster than the brute force method. However, it requires two passes over the array, and it also uses O(n) additional space to store the hash table. Can we do better?

Approach 3: One-pass Hash Table

Yes, we can! By making some modifications to the previous approach, we can solve the problem in a single pass over the array. The idea is to check if each element’s complement already exists in the hash table while we are inserting elements into the hash table.

def twoSum(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

This approach also has a time complexity of O(n), but it only requires a single pass over the array, making it more efficient than the two-pass hash table approach. It still uses O(n) additional space for the hash table.

Conclusion

The Two Sum problem provides a great opportunity to learn and apply various problem-solving techniques. It shows how a brute force solution can be improved using data structures like hash tables. The Python solutions provided here demonstrate these techniques and provide a strong foundation for solving more complex problems on LeetCode.

Remember, when it comes to solving problems, understanding the problem statement is crucial. Once you fully understand the problem, start with a simple solution, even if it’s not the most efficient. After you have a working solution, think about how you can improve it. Can you use a different data structure? Can you reduce the number of passes over the data? Can you reduce the amount of additional space used? As you work through more problems, you’ll become more comfortable with these techniques and be able to apply them more effectively.