Leetcode 167 - Two Sum II

Table of contents

Problem

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.

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].

Constraints:

• 2 <= numbers.length <= 3 * 104
• -1000 <= numbers[i] <= 1000
• numbers is sorted in non-decreasing order. -1000 <= target <= 1000
• The tests are generated such that there is exactly one solution.

Explanation/Approach

Given a sorted array of integers, the task is to find two numbers that add up to a specific target number. The sorted nature of the array can be exploited to optimize the search for the two numbers, which is a crucial hint for efficiently solving this problem.

A possible approach is using the Two-Pointer technique. Since the array is sorted in non-decreasing order, you can start with two pointers, one at the beginning (left) and one at the end (right) of the array. At each step, calculate the sum of the elements pointed to by the two pointers. Depending on the comparison between the sum and the target:

• If the sum is equal to the target, you’ve found the two numbers.
• If the sum is less than the target, move the left pointer to the right (increment it).
• If the sum is more than the target, move the right pointer to the left (decrement it).

Repeat these steps until the left pointer is less than the right pointer.

Solution 1: (Two Pointers)

def two_sum(numbers: List[int], target: int) -> List[int]:
    # Initialize two pointers at both ends of the list
    left, right = 0, len(numbers) - 1

    # Loop until the two pointers meet
    while left < right:
        # Calculate the sum of elements at both pointers
        current_sum = numbers[left] + numbers[right]
        # If the sum is equal to target, return the indices (1-indexed)
        if current_sum == target:
            return [left + 1, right + 1]
        # If sum is less than target, move left pointer to the right
        elif current_sum < target:
            left += 1
        # If sum is more than target, move right pointer to the left
        else:
            right -= 1

Explanation

• Start with two pointers at both ends of the array. Initialize left at 0 and right at len(numbers) - 1.
• While left pointer is less than right pointer:
  • Calculate current_sum as the sum of numbers[left] and numbers[right].
  • If current_sum is equal to target, return the indices left + 1 and right + 1 (since the problem requires 1-indexed array).
  • If current_sum is less than target, increment left to move towards a larger value (since the array is sorted).
  • If current_sum is more than target, decrement right to move towards a smaller value.
• Continue this process until the left pointer is no longer less than the right pointer.

Time and Memory Complexity

• Time Complexity: O(N). Each element is visited at most once, leading to linear time complexity.
• Space Complexity: O(1). Only a constant amount of extra space is used, satisfying the problem constraint of using only constant extra space.

Solution 2: (Hash Map)

Although the two-pointer approach is more optimal for this specific problem due to the sorted nature of the array, you can also solve it using a Hash Map for general understanding. Below is the Hash Map approach explained:

def two_sum(numbers: List[int], target: int) -> List[int]:
    # Create a hash map to store indices of numbers
    index_map = {}

    # Iterate through the list of numbers with index
    for index, num in enumerate(numbers, start=1):  # Using 1-based indexing
        complement = target - num  # Calculate the complement of current number

        # If complement is found in hash map, return the indices
        if complement in index_map:
            return [index_map[complement], index]

        # Otherwise, add the number and its index to the hash map
        index_map[num] = index

Explanation

1. Create a Hash Map (index_map) to store indices of numbers as you iterate through the array.
2. Iterate through the list of numbers with their index. Using enumerate(numbers, start=1) to have 1-based indexing as required by the problem statement.
3. For each number, calculate its complement with respect to the target (i.e., complement = target - num).
4. Check if this complement is already available in the index_map. If it is, that means you have found two numbers whose sum is equal to the target. Return their indices.
5. If the complement is not in the index_map, add the current number and its index to the index_map.
6. Continue this process for all numbers in the array.

Time and Memory Complexity

• Time Complexity: O(N). You need to iterate through all elements in the array once, performing O(1) work for each due to the hash map.
• Space Complexity: O(N). You need to store all N elements in the hash map in the worst case. This solution does not satisfy the constant extra space requirement posed by the problem, but it’s provided here for educational purposes and for problems where space complexity is not a constraint.