Skip to content

Leetcode 167 - Two Sum II

Difficulty: medium

Table of contents

Open Table of contents


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



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:

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
            right -= 1


Time and Memory Complexity

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


  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