Solving LeetCode's 167. Two Sum II: A Step-by-Step Guide
Introduction
Welcome to our LeetCode substack! In this post, we'll be walking through the process of solving the Two Sum II problem using Python. This is a variation of the popular Two Sum problem, but with the added constraint that the input array is already sorted. This presents some interesting challenges and opportunities for optimization that we'll explore in this post.
Problem Statement
The Two Sum II problem asks us to find two numbers in a sorted array that add up to a given target. For example, given the array [2, 7, 11, 15] and target 9, we should return [1, 2], because 2 + 7 = 9.
Solution
To solve this problem, we can use a two-pointer approach. We start by initializing two pointers, one at the beginning of the array and one at the end. We then compare the sum of the numbers pointed to by the two pointers with the target. If the sum is equal to the target, we return the indices of the two numbers as a list. If the sum is less than the target, we move the left pointer to the right to increase the sum. If the sum is greater than the target, we move the right pointer to the left to decrease the sum.
Here's the Python code to implement this solution:
class Solution:
def twoSum(self, numbers: List[int], target: int) -> List[int]:
left, right = 0, len(numbers)-1
while left <= right:
if numbers[left] + numbers[right] == target:
return [left + 1, right + 1]
elif numbers[left] + numbers[right] < target:
# move left pointer rightward to increase the sum
left += 1
else:
# move right pointers leftward to reduce the sum
right -= 1
Let's walk through how this code works. We start by initializing two pointers, left
and right
, to the beginning and end of the array, respectively. We then enter a loop that continues as long as left
is less than right
.
At each iteration of the loop, we calculate the sum of the numbers pointed to by the two pointers, numbers[left]
and numbers[right]
. If the sum is equal to the target, we have found our two numbers and can return their indices as a list.
If the sum is less than the target, we increment left
to move the pointer to the right and increase the sum. If the sum is greater than the target, we decrement right
to move the pointer to the left and decrease the sum. We continue this process until we find the two numbers that add up to the target or exhaust all possible pairs of numbers.
One important thing to note is that the problem statement asks for the indices of the numbers as a 1-based array, rather than a 0-based array. That's why we add 1 to each index before returning the list.
Difference between Two Sum II and Two Sum
The Two Sum II problem is a variation of the original Two Sum problem that adds the constraint that the input array is already sorted. This presents some interesting challenges and opportunities for optimization that are not present in the original problem.
In the original Two Sum problem, we can use a hash table to store the indices of each number in the array and check if the complement of the current number is already in the hash table. This gives us a time complexity of O(n) since we only need to iterate through the array once to find the solution.
In contrast, the Two Sum II problem requires us to take advantage of the fact that the input array is sorted to achieve a better time complexity. We can use a two-pointer approach to iterate through the array and find the two numbers that add up to the target. This approach has a time complexity of O(n), which is the same as the original problem, but requires less space since we don't need to use a hash table.
Another difference between the two problems is the format of the output. The original Two Sum problem asks us to return the indices of the two numbers as a 0-based array. In contrast, the Two Sum II problem asks us to return the indices as a 1-based array. This means we need to add 1 to each index before returning the solution in the Two Sum II problem.
Overall, while the Two Sum II problem is a variation of the original Two Sum problem, it requires a different approach due to the added constraint of a sorted input array. By taking advantage of this constraint, we can achieve better time complexity and optimize our solution.
Interview Pitch
To solve this problem, we start by initializing two pointers, one at the beginning of the array and one at the end. We then compare the sum of the numbers pointed to by the two pointers with the target. If the sum is equal to the target, we return the indices of the two numbers as a list. If the sum is less than the target, we move the left pointer to the right to increase the sum. If the sum is greater than the target, we move the right pointer to the left to decrease the sum.
This approach takes advantage of the fact that the input array is sorted by allowing us to discard certain pairs of numbers that we know won't sum up to the target. This leads to a more efficient algorithm and highlights the importance of understanding the properties of the input data when solving algorithmic problems.
In conclusion, the Two Sum II problem is a great example of how optimizing a solution based on the input data can lead to significant performance gains. By taking advantage of the sorted nature of the input array, we can use a two-pointer approach to achieve a time complexity of O(n) and optimize our solution.
Conclusion
In this post, we've walked through the process of solving the Two Sum II problem using a two-pointer approach in Python. We've shown how this approach can take advantage of the fact that the input array is already sorted to achieve better time complexity than the original Two Sum problem. We hope this post has been helpful in improving your algorithmic problem-solving skills. Stay tuned for more LeetCode solutions and strategies in our substack!