Two Sum III in Python (O(n log n) Time Complexity)

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input will have at most one solution, and you may not use the same index twice.

In case no solution exists, return [-1, -1]

Example:

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

Note:

Your algorithm should run in O(n log n) time and use O(n) extra space.

Understanding the Problem

The core challenge of this problem is to find two distinct indices in the array such that the sum of the elements at these indices equals the target value. This problem is significant in various applications, such as financial transactions, where you need to find pairs of transactions that sum up to a specific amount.

Potential pitfalls include assuming that there are multiple solutions or using the same index twice, which the problem explicitly forbids.

Approach

To solve this problem, we can use a hash map (dictionary in Python) to store the indices of the elements as we iterate through the array. This allows us to check in constant time whether the complement of the current element (i.e., target - current element) has already been seen.

Here is a step-by-step breakdown of the approach:

Initialize an empty dictionary to store the indices of the elements.
Iterate through the array using a for loop.
For each element, calculate its complement (i.e., target - current element).
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, add the current element and its index to the dictionary.
If no solution is found by the end of the loop, return [-1, -1].

Algorithm

Let's break down the algorithm step-by-step:

Create an empty dictionary called num_to_index.
Loop through the array nums using a for loop with index i and value num.
Calculate the complement as target - num.
Check if the complement is in num_to_index.
If it is, return the list of indices [num_to_index[complement], i].
If it is not, add num and its index i to num_to_index.
If the loop completes without finding a solution, return [-1, -1].

Code Implementation

def two_sum(nums, target):
    # Dictionary to store the index of each number
    num_to_index = {}
    
    # Iterate through the list of numbers
    for i, num in enumerate(nums):
        # Calculate the complement
        complement = target - num
        
        # Check if the complement is already in the dictionary
        if complement in num_to_index:
            # If found, return the indices of the complement and the current number
            return [num_to_index[complement], i]
        
        # Otherwise, add the current number and its index to the dictionary
        num_to_index[num] = i
    
    # If no solution is found, return [-1, -1]
    return [-1, -1]

# Example usage
nums = [2, 7, 11, 15]
target = 9
print(two_sum(nums, target))  # Output: [0, 1]

Complexity Analysis

The time complexity of this approach is O(n) because we are iterating through the array once. The space complexity is also O(n) because we are storing each element in the dictionary.

Edge Cases

Some potential edge cases include:

An empty array: The function should return [-1, -1].
An array with one element: The function should return [-1, -1].
No two elements sum up to the target: The function should return [-1, -1].

Examples:

print(two_sum([], 9))  # Output: [-1, -1]
print(two_sum([1], 9))  # Output: [-1, -1]
print(two_sum([1, 2, 3], 7))  # Output: [-1, -1]

Testing

To test the solution comprehensively, we should include a variety of test cases:

Simple cases with a known solution.
Edge cases with no solution.
Cases with negative numbers and zero.

Example test cases:

print(two_sum([2, 7, 11, 15], 9))  # Output: [0, 1]
print(two_sum([3, 2, 4], 6))  # Output: [1, 2]
print(two_sum([3, 3], 6))  # Output: [0, 1]
print(two_sum([1, 2, 3], 7))  # Output: [-1, -1]
print(two_sum([], 9))  # Output: [-1, -1]
print(two_sum([1], 9))  # Output: [-1, -1]

Thinking and Problem-Solving Tips

When approaching such problems, consider the following tips:

Understand the problem requirements and constraints thoroughly.
Think about different data structures that can help optimize the solution.
Break down the problem into smaller steps and solve each step incrementally.
Practice similar problems to improve problem-solving skills and familiarity with common patterns.

Conclusion

In this blog post, we discussed the Two Sum III problem, explored different approaches to solve it, and provided a detailed explanation of the optimized solution using a hash map. We also covered edge cases, testing, and tips for problem-solving. Understanding and solving such problems is crucial for developing strong algorithmic thinking and coding skills.

Additional Resources

For further reading and practice, consider the following resources: