Two Sum in O(n^2) Time Complexity Using Python
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
Problem Definition
The problem requires us to find two distinct indices in an array such that the numbers at those indices add up to a given target. If no such indices exist, we should return [-1, -1].
Input:
- An array of integers,
nums. - An integer,
target.
Output:
- A list of two integers representing the indices of the two numbers that add up to the target.
- If no such indices exist, return
[-1, -1].
Constraints:
- Each input will have at most one solution.
- You may not use the same index twice.
Example:
Input: nums = [2, 7, 11, 15], target = 9 Output: [0, 1] Explanation: nums[0] + nums[1] = 2 + 7 = 9
Understanding the Problem
The core challenge is to identify two distinct indices in the array whose corresponding values sum up to the target. This problem is significant in various applications such as financial transactions, inventory management, and more.
Potential pitfalls include assuming multiple solutions or using the same index twice, which the problem explicitly disallows.
Approach
To solve this problem, we can start with a naive approach and then discuss optimized solutions.
Naive Solution
The naive solution involves checking all possible pairs of indices to see if their corresponding values sum up to the target. This can be achieved using two nested loops.
Optimized Solution
While the naive solution works, it is not optimal. We can use a hash map to store the difference between the target and each element as we iterate through the array. This allows us to check in constant time if the complement of the current element exists in the hash map.
Algorithm
Naive Approach
def two_sum(nums, target):
# Iterate through each pair of indices
for i in range(len(nums) - 1):
for j in range(i + 1, len(nums)):
# Check if the sum of the pair equals the target
if nums[i] + nums[j] == target:
return [i, j]
# Return [-1, -1] if no solution is found
return [-1, -1]
Optimized Approach
def two_sum(nums, target):
# Create a hash map to store the difference and index
num_map = {}
for i, num in enumerate(nums):
# Calculate the complement
complement = target - num
# Check if the complement exists in the hash map
if complement in num_map:
return [num_map[complement], i]
# Store the index of the current number
num_map[num] = i
# Return [-1, -1] if no solution is found
return [-1, -1]
Code Implementation
Naive Solution
def two_sum(nums, target):
# Iterate through each pair of indices
for i in range(len(nums) - 1):
for j in range(i + 1, len(nums)):
# Check if the sum of the pair equals the target
if nums[i] + nums[j] == target:
return [i, j]
# Return [-1, -1] if no solution is found
return [-1, -1]
Optimized Solution
def two_sum(nums, target):
# Create a hash map to store the difference and index
num_map = {}
for i, num in enumerate(nums):
# Calculate the complement
complement = target - num
# Check if the complement exists in the hash map
if complement in num_map:
return [num_map[complement], i]
# Store the index of the current number
num_map[num] = i
# Return [-1, -1] if no solution is found
return [-1, -1]
Complexity Analysis
Naive Solution
- Time Complexity: O(n^2) - We have two nested loops.
- Space Complexity: O(1) - No extra space is used.
Optimized Solution
- Time Complexity: O(n) - We traverse the list once.
- Space Complexity: O(n) - We use a hash map to store the indices.
Edge Cases
- Empty array: Should return [-1, -1].
- Array with one element: Should return [-1, -1].
- No valid pairs: Should return [-1, -1].
Testing
To test the solution comprehensively, we should include a variety of 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([], 1) == [-1, -1]
assert two_sum([1], 1) == [-1, -1]
assert two_sum([1, 2, 3], 7) == [-1, -1]
print("All test cases pass")
test_two_sum()
Thinking and Problem-Solving Tips
- Break down the problem into smaller parts.
- Consider edge cases and constraints.
- Think about different approaches and their trade-offs.
- Practice similar problems to improve problem-solving skills.
Conclusion
Understanding and solving the Two Sum problem is crucial for developing problem-solving skills. It helps in understanding the importance of different approaches and their trade-offs. Practice and exploration of similar problems can further enhance these skills.