Two Sum II LeetCode Problem 167 [Python Solution]

LeetCode Problem 167, Two Sum II asks to find two numbers that add up to a target when given a 1-indexed array of integers sorted in decreasing.

Question: Given a 1-indexed array of integers numbers that is already sorted in non-decreasing order, find two numbers such that they add up to a specific target number. Let these two numbers be numbers[index1] and numbers[index2] where 1 <= index1 < index2 < numbers.length.

Return the indices of the two numbers, index1 and index2, added by one as an integer array [index1, index2] of length 2.

The tests are generated such that there is exactly one solution. You may not use the same element twice.

Your solution must use only constant extra space.

Problem Overview

In this problem, we are given a 1-indexed array of integers that is already sorted in non-decreasing order. Our task is to find two numbers in the array that add up to a specific target number. We need to return the indices of these two numbers, where the indices are 1-based.

For example, if we have an array [2,7,11,15] and the target is 9, the two numbers that sum up to 9 are 2 and 7, and we should return the indices [1,2].

Example 1:

Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: The sum of 2 and 7 is 9. Therefore, index1 = 1, index2 = 2. We return [1, 2].

Example 2:

Input: numbers = [2,3,4], target = 6
Output: [1,3]
Explanation: The sum of 2 and 4 is 6. Therefore index1 = 1, index2 = 3. We return [1, 3].

Example 3:

Input: numbers = [-1,0], target = -1
Output: [1,2]
Explanation: The sum of -1 and 0 is -1. Therefore index1 = 1, index2 = 2. We return [1, 2].

Understanding the Constraints

Before diving into the solution, let’s understand the constraints of the problem:

The array length numbers.length is between 2 and 3 * 10^4.
Each element in the array numbers[i] is between -1000 and 1000.
The array is sorted in non-decreasing order.
The target target is between -1000 and 1000.
There is exactly one solution.

Bruteforce Approach

One straightforward approach to solving this problem is to consider every possible pair of numbers in the array and check if their sum equals the target.

However, this approach is not efficient as it would require nested loops and result in a time complexity of O(N^2), where N is the length of the array.

Here’s a Python code snippet for the brute force approach:

def twoSumBruteforce(numbers, target):
    n = len(numbers)
    for i in range(n):
        for j in range(i + 1, n):
            if numbers[i] + numbers[j] == target:
                return [i + 1, j + 1]  # Adjusting indices to be 1-based

Efficient Approach with Two Pointers

Fortunately, we can take advantage of the fact that the input array is sorted to devise a more efficient solution.

We’ll use the two-pointer technique to achieve a linear time complexity of O(N), where N is the length of the array.

Python Two Pointer Solution Implementation

Here’s the efficient Python code solution:

View on GitHub ➹

def twoSum(numbers, target):
    left, right = 0, len(numbers) - 1

    while left &lt; right:
        cur_sum = numbers[left] + numbers[right]

        if cur_sum > target:
            right -= 1
        elif cur_sum &lt; target:
            left += 1
        else:
            return [left + 1, right + 1]  # Adjusting indices to be 1-based

Time and Space Complexity

Time Complexity: O(N)
Space Complexity: O(1)

Reasoning Behind Our Efficient Approach

We use two pointers, left and right, initialized to the start and end of the array, respectively. This approach leverages the fact that the array is sorted.

We calculate the sum of the elements at the left and right pointers.
If the sum is greater than the target, we decrement right, effectively reducing the sum.
If the sum is less than the target, we increment left, increasing the sum.
If the sum equals the target, we have found our solution and return the indices. Since the indices are 0-based, we add 1 to each index to make them 1-based.

This algorithm works because as we adjust the pointers based on the comparison of the current sum with the target, we effectively explore all possible pairs of elements in a sorted order.

When we find the pair that sums to the target, we return their indices.

Conclusion

In this blog post, we discussed and solved the Two Sum II – Input Array is Sorted LeetCode problem 167.

We discussed the problem’s requirements, and constraints, and provided both a brute force and an efficient solution using the two-pointer technique.

The brute force approach involved considering all possible pairs of numbers in the array, resulting in a time complexity of O(N^2).

However, we then introduced an optimized solution that utilized the fact that the array was sorted.

By using two pointers, we achieved a linear time complexity of O(N), making the algorithm significantly more efficient.

We encourage you to practice and explore more coding challenges to enhance your problem-solving skills.

Solve on LeetCode now.

If you have any questions, or suggestions, or would like to share your thoughts, please feel free to comment below. Happy coding!