LeetCode Array Problem: Solving the Two Sum Challenge

The Two Sum problem is a classic problem frequently encountered in coding interviews and algorithm challenges. It tests your ability to efficiently find two numbers in an array that sum up to a given target. In this blog post, we’ll explore different approaches to solving this problem, highlighting their time and space complexities.

Problem Statement

Given an array of integers nums and an integer, return the indices of the two numbers such that they add up to target. Each input is guaranteed to have exactly one solution, and you may not use the same element twice.

Example:

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

Solution 1: Brute Force Approach

Description

The brute force approach involves checking every possible pair of numbers to see if they add up to the target. This method is straightforward but not the most efficient.

Algorithm

1. Iterate through each element in the array.
2. For each element, iterate through the remaining elements to check if the sum of the current element and another element equals the target.
3. If such a pair is found, return their indices.

Code

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]

Time Complexity

The time complexity of this approach is O(n^2) due to the two nested loops iterating through the array.

Space Complexity

The space complexity is O(1) since no additional space is used apart from a few variables.

Pros and Cons

• Pros: Simple to understand and implement.
• Cons: Inefficient for large arrays due to its quadratic time complexity.

Solution 2: Hash Map Approach

Description

The hash map approach utilizes a dictionary (hash map) to store indices of elements as we iterate through the array. This allows us to check if the complement of the current component (i.e., target - current_element) is already present in the hash map.

Algorithm

1. Create an empty dictionary to store elements and their indices.
2. Iterate through the array, and for each element, calculate its complement by subtracting the element from the target.
3. Check if the complement is already in the dictionary:
   • If it is, return the indices of the complement and the current element.
   • If it is not, store the current element and its index in the dictionary.

Code

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

Time Complexity

The time complexity of this approach is O(n) as each lookup and insertion in the hash map takes constant time, and we only traverse the array once.

Space Complexity

The space complexity is O(n) due to the hash map that stores elements and their indices.

Pros and Cons

• Pros: Efficient with linear time complexity and suitable for large arrays.
• Cons: Requires additional space for the hash map.

Comparison

Approach	Time Complexity	Space Complexity	Pros	Cons
Brute Force	O(n^2)	O(1)	Simple to implement	Inefficient for large arrays
Hash Map	O(n)	O(n)	Efficient and suitable for large arrays	Requires extra space

Conclusion

The Two Sum problem can be tackled using various methods, each with its own advantages and trade-offs. The brute force approach, while simple, is not ideal for large datasets due to its quadratic time complexity. The hash map approach, although requiring extra space, provides a more efficient solution with linear time complexity.