Leetcode 167 - Two Sum II - Input Array Is Sorted

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, as an integer array [index1, index2] of length 2. The 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].

Constraints:

• 2 <= numbers.length <= 3 * 10^4
• -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

Two Pointer Approach:

• Two Pointers: Start with two pointers, one at the beginning (left) and one at the end (right) of the array.
• Moving the Pointers: If the sum of numbers[left] and numbers[right] is less than the target, move the left pointer to the right. If the sum is greater, move the right pointer to the left.
• Finding the Solution: When the sum equals the target, return the indices of these two numbers.

Solution: Two Pointers

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        left, right = 0, len(numbers) - 1

        while left < right:
            current_sum = numbers[left] + numbers[right]
            if current_sum == target:
                # Add 1 to each index because the array is 1-indexed
                return [left + 1, right + 1]
            elif current_sum < target:
                left += 1
            else:
                right -= 1

        # Since there is exactly one solution, this return is theoretically unreachable
        return [-1, -1]

Time and Memory Complexity

The time complexity is O(n), where n is the number of elements in numbers, as each element is visited at most once. The space complexity is O(1), as only two pointers are used.

Explanation

The two-pointer approach efficiently finds the two numbers that sum up to the target. We move the left pointer to the right to increase the sum and the right pointer to the left to decrease the sum. This method leverages the sorted nature of the array to find the solution in a linear scan.

Visual Representation

Consider the input numbers = [2,7,11,15] and target = 9.

1. Initial Pointers:

   • left = 0 (pointing to 2) and right = 3 (pointing to 15).

2. Iteration Steps:

   • First iteration: Sum of 2 + 15 = 17 (greater than 9), move right to the left.
   • Second iteration: left = 0 (2) and right = 2 (11). Sum = 2 + 11 = 13 (greater than 9), move right to the left.
   • Third iteration: left = 0 (2) and right = 1 (7). Sum = 2 + 7 = 9 (equals target), return [1, 2].

Iteration 1: [2, 7, 11, 15]
              ^          ^
            left       right

Iteration 2: [2, 7, 11, 15]
              ^      ^
            left     right

Iteration 3: [2, 7, 11, 15]
              ^  ^
            left  right

In each iteration, we adjust the pointers based on the sum compared to the target, leading us to the solution.

Solution: Hashmap

• Hashmap for Complement: Use a hashmap to store the complement of each number with respect to the target, along with its index.
• Iterating Through the Array: For each number, check if it’s already in the hashmap. If it is, it means we have found the pair that adds up to the target.
• Returning Indices: Once a pair is found, return the indices of these two numbers.

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        hashmap = {}

        for i, num in enumerate(numbers):
            if num in hashmap:
                # The array is 1-indexed, so add 1 to the indices
                return [hashmap[num] + 1, i + 1]
            # Store the complement and its index
            hashmap[target - num] = i

        # Since there is exactly one solution, this return is theoretically unreachable
        return [-1, -1]

Time and Memory Complexity

The time complexity is O(n), where n is the number of elements in numbers, as we iterate through the array once. The space complexity is O(n), due to the additional hashmap storing up to n elements.

Explanation

In this approach, we use a hashmap to store the complement of each number with respect to the target. As we iterate through the array, we check if the current number exists in the hashmap. If it does, it means we have found the two numbers that sum up to the target. The indices of these two numbers are then returned.

Visual Representation

Consider the input numbers = [2,7,11,15] and target = 9.

1. Building the Hashmap:

   • Start iterating through numbers.
   • For 2, store 7 (complement of 9 - 2) with index 0.
   • For 7, find it already exists in the hashmap.

2. Finding the Pair:

   • Upon finding 7 in the hashmap, we know that 2 (at index 0) and 7 (current index) are the required pair.

numbers = [2, 7, 11, 15], target = 9

Hashmap Status:
{2: 0}  # Complement of 2 stored with its index

Finding 2 in the hashmap indicates the pair (2, 7) that sums up to 9. Indices: [1, 2].

In this way, the hashmap approach efficiently finds the two numbers that sum up to the target in a single pass through the array.