We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Two Sum II - Input Array Is Sorted

Number: 167

Difficulty: Medium

Paid? No

Companies: Meta, Google, Amazon, Microsoft, Apple, Bloomberg, Yandex, Adobe, Oracle

Problem Description

Given a 1-indexed array of integers that is sorted in non-decreasing order, find and return the two indices such that their corresponding numbers add up to a given target. It is guaranteed that exactly one solution exists, and you cannot use the same element twice. Note that the returned indices must be adjusted by one (since the array is 1-indexed).

Key Insights

  • The array is sorted in non-decreasing order, which makes the two pointers technique very effective.
  • Using two pointers (one at the start and one at the end) allows checking pairs and adjusting the pointers based on the sum.
  • Since the problem guarantees exactly one solution and requires constant space, using two pointers satisfies both constraints.

Space and Time Complexity

Time Complexity: O(n), where n is the number of elements in the array, because in the worst-case scenario each element is visited at most once. Space Complexity: O(1), as no additional data structure is used that scales with the input size.

Solution

We use the two pointers approach:

  1. Initialize two pointers, left at the beginning (index 0) and right at the end (last index) of the array.
  2. While left is less than right, compute the sum of the elements at the two pointers.
  3. If the sum equals the target, return the indices as [left+1, right+1] (to adjust for the 1-indexed array).
  4. If the sum is less than the target, move the left pointer to the right to increase the sum.
  5. If the sum is greater than the target, move the right pointer to the left to decrease the sum. This approach leverages the sorted property and uses constant extra space.

Code Solutions

# Python solution for Two Sum II - Input Array Is Sorted
def twoSum(numbers, target):
    # Initialize two pointers at the beginning and end of the array
    left = 0
    right = len(numbers) - 1
    
    # Continue until the two pointers meet
    while left < right:
        # Calculate the sum of the two pointed values
        current_sum = numbers[left] + numbers[right]
        # If the sum matches the target, return the 1-indexed results
        if current_sum == target:
            return [left + 1, right + 1]
        # If the current sum is less than the target, move the left pointer to the right
        elif current_sum < target:
            left += 1
        # Otherwise, move the right pointer to the left since the current sum is too high
        else:
            right -= 1

# Example call
print(twoSum([2, 7, 11, 15], 9))  # Output: [1, 2]
← Back to All Questions