Two Sum IV in O(n) Time Complexity using Python

Problem Definition

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) time and use O(n) space.

Understanding the Problem

The core challenge of this problem is to find two indices in an 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 value.

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

Approach

To solve this problem, we can start with a naive solution and then optimize it:

Naive Solution

The naive approach involves using two nested loops to check all possible pairs of indices. This solution has a time complexity of O(n^2), which is not optimal for large arrays.

Optimized Solution

To achieve an O(n) time complexity, we can use a hash map (dictionary in Python) to store the elements and their indices 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) exists in the hash map.

Algorithm

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

Code Implementation

def two_sum(nums, target):
    # Create a dictionary to store the value and its index
    index_map = {}
    
    # Iterate through the list
    for i, num in enumerate(nums):
        # Calculate the complement
        complement = target - num
        
        # Check if the complement exists in the dictionary
        if complement in index_map:
            # If found, return the indices
            return [index_map[complement], i]
        
        # Otherwise, add the current number and its index to the dictionary
        index_map[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 solution is O(n) because we iterate through the array once. The space complexity is also O(n) due to the hash map storing up to n elements.

Edge Cases

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, include a variety of test cases:

Simple cases with small arrays.
Edge cases with empty or single-element arrays.
Cases where no solution exists.
Cases with negative numbers and zero.

Example test cases:

def test_two_sum():
    assert two_sum([2, 7, 11, 15], 9) == [0, 1]
    assert two_sum([3, 2, 4], 6) == [1, 2]
    assert two_sum([3, 3], 6) == [0, 1]
    assert two_sum([], 9) == [-1, -1]
    assert two_sum([1], 9) == [-1, -1]
    assert two_sum([1, 2, 3], 7) == [-1, -1]
    assert two_sum([-1, -2, -3, -4, -5], -8) == [2, 4]
    print("All test cases pass")

test_two_sum()

Thinking and Problem-Solving Tips

When approaching such problems:

Understand the problem requirements and constraints.
Start with a brute force solution to understand the basic logic.
Look for ways to optimize the solution using data structures like hash maps.
Consider edge cases and test your solution thoroughly.

Conclusion

In this blog post, we discussed the Two Sum problem, explored a naive solution, and then optimized it using a hash map to achieve O(n) time complexity. Understanding and solving such problems is crucial for developing strong problem-solving skills in programming.

Practice is key to mastering these concepts, so keep solving similar problems and exploring different algorithms.