LeetCode 167 - Two Sum II - Input Array Is Sorted

LeetCode Problem 167

Difficulty: 🟡 Medium
Topics: Array, Two Pointers, Binary Search

Solution

Problem Understanding

This problem gives us a sorted, 1-indexed array of integers called numbers and a target integer target. Our task is to find exactly two numbers in the array whose sum equals target, then return their 1-based indices.

The key detail is that the array is already sorted in non-decreasing order, meaning values are arranged from smallest to largest, with duplicates allowed. Unlike the classic Two Sum problem, where the array is unsorted and a hash map is commonly used, this sorted property changes the strategy significantly.

The input consists of:

• numbers, a sorted integer array
• target, the sum we want to achieve

The expected output is an array of length 2, containing the 1-based positions of the two numbers that add up to the target.

For example:

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

The pair 2 + 7 = 9, and their indices are 1 and 2, so the answer is:

[1,2]

The problem guarantees several important constraints:

• The array length can be up to 3 * 10^4, meaning inefficient quadratic solutions may become slow.
• The array is already sorted.
• There is exactly one valid solution.
• We may not reuse the same element twice.
• The solution must use constant extra space.

These guarantees strongly influence the optimal approach. Since there is exactly one answer, we do not need to handle ambiguity or multiple valid pairs. Since the array is sorted, we can exploit ordering relationships to avoid checking every pair. Since constant extra space is required, a hash map approach, while efficient in time, violates the problem constraint.

Several edge cases are worth considering upfront. The solution may involve negative numbers, such as [-1, 0]. The valid pair might appear at the beginning or end of the array. Duplicate values may exist, for example [3,3], where the same numeric value appears twice but different indices must be used. A naive implementation may accidentally reuse the same index or miss valid pairs when duplicates exist.

Approaches

Brute Force Approach

The most straightforward solution is to try every possible pair of numbers.

We can use two nested loops. For every index i, we check every later index j and compute:

numbers[i] + numbers[j]

If the sum equals target, we return the indices.

This works because eventually we examine every possible pair, guaranteeing that we find the correct one. Since the problem guarantees exactly one solution, we can stop immediately when the pair is found.

However, this approach is inefficient. If the array contains n elements, the nested loops examine approximately:

n * (n - 1) / 2

pairs in the worst case.

For an input size of 30,000, quadratic behavior becomes unnecessarily expensive.

Optimal Approach, Two Pointers

The crucial observation is that the array is already sorted.

Because the numbers are ordered, we can make intelligent decisions about how to move through the array instead of checking every pair.

We place:

• One pointer at the leftmost element
• One pointer at the rightmost element

At each step:

• Compute the current sum
• If the sum is too small, move the left pointer rightward
• If the sum is too large, move the right pointer leftward
• If the sum matches the target, return the indices

This works because of the sorted order.

Suppose the sum is too small. Since the left value is among the smallest remaining numbers, decreasing the right pointer would only make the sum smaller. Therefore, the only meaningful move is increasing the left pointer.

Similarly, if the sum is too large, increasing the left pointer would make the sum even larger. The only sensible move is decreasing the right pointer.

This allows us to eliminate impossible candidates efficiently and scan the array in linear time while using constant extra space.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	Checks every pair of numbers
Optimal	O(n)	O(1)	Uses sorted property with two pointers

Algorithm Walkthrough

Optimal Algorithm, Two Pointers

1. Initialize two pointers.

Set left = 0 and right = len(numbers) - 1.

The left pointer starts at the smallest number, while the right pointer starts at the largest number. 2. Compute the current sum.

At each iteration, calculate:

current_sum = numbers[left] + numbers[right]

This tells us whether we are below, above, or exactly at the target. 3. Compare the sum with the target.

If current_sum == target, we have found the answer.

Since the problem uses 1-indexed positions, return:

[left + 1, right + 1]

4. Move the left pointer if the sum is too small.

If:

current_sum < target

then the sum must increase.

Because the array is sorted, moving left rightward gives us a larger number. 5. Move the right pointer if the sum is too large.

If:

current_sum > target

then the sum must decrease.

Because the array is sorted, moving right leftward gives us a smaller number. 6. Repeat until the solution is found.

Since exactly one valid solution exists, the pointers will eventually locate it.

Why it works

The algorithm maintains an important invariant: every pair outside the current pointer range has already been ruled out.

If the sum is too small, any pair using the current left element with a smaller right element would also be too small, so we safely discard the current left position.

If the sum is too large, any pair using the current right element with a larger left element would also remain too large, so we safely discard the current right position.

Because we eliminate impossible candidates without missing the valid solution, and because exactly one solution exists, the algorithm is guaranteed to find the correct pair.

Python Solution

from typing import List

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

        while left < right:
            current_sum = numbers[left] + numbers[right]

            if current_sum == target:
                return [left + 1, right + 1]

            if current_sum < target:
                left += 1
            else:
                right -= 1

        return []

The implementation begins by creating two pointers, left and right, positioned at opposite ends of the array.

Inside the loop, we compute the sum of the values at the current pointers. If this sum equals the target, we immediately return the indices adjusted to 1-based indexing, which the problem requires.

If the sum is too small, we increment left because larger values lie to the right in a sorted array. If the sum is too large, we decrement right because smaller values lie to the left.

The loop continues until the correct pair is found. Although the problem guarantees a valid solution, returning an empty list at the end makes the function syntactically complete and safe.

Go Solution

func twoSum(numbers []int, target int) []int {
	left := 0
	right := len(numbers) - 1

	for left < right {
		currentSum := numbers[left] + numbers[right]

		if currentSum == target {
			return []int{left + 1, right + 1}
		}

		if currentSum < target {
			left++
		} else {
			right--
		}
	}

	return []int{}
}

The Go implementation follows the exact same algorithmic structure as the Python version.

Instead of Python lists, Go uses slices. The returned result is created using:

[]int{left + 1, right + 1}

Go integers are sufficiently large for this problem's constraints, so integer overflow is not a concern. Since the problem guarantees one valid solution, the fallback empty slice is effectively unreachable, but it keeps the function complete.

Worked Examples

Example 1

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

Step	Left Index	Right Index	Left Value	Right Value	Sum	Action
1	0	3	2	15	17	Too large, move right
2	0	2	2	11	13	Too large, move right
3	0	1	2	7	9	Found answer

Return:

[left + 1, right + 1] = [1, 2]

Example 2

numbers = [2,3,4]
target = 6

Step	Left Index	Right Index	Left Value	Right Value	Sum	Action
1	0	2	2	4	6	Found answer

Return:

[1,3]

Example 3

numbers = [-1,0]
target = -1

Step	Left Index	Right Index	Left Value	Right Value	Sum	Action
1	0	1	-1	0	-1	Found answer

Return:

[1,2]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each pointer moves at most n times
Space	O(1)	Only a few variables are used

The time complexity is O(n) because each pointer moves in only one direction and never revisits positions. Even though there is a loop, each element is processed at most once by either pointer.

The space complexity is O(1) because the algorithm only stores a few integer variables regardless of input size. No auxiliary data structures are used, satisfying the constant space requirement.

Test Cases

solution = Solution()

# Provided examples
assert solution.twoSum([2, 7, 11, 15], 9) == [1, 2]  # Basic example
assert solution.twoSum([2, 3, 4], 6) == [1, 3]  # Pair spans array
assert solution.twoSum([-1, 0], -1) == [1, 2]  # Negative number case

# Minimum array length
assert solution.twoSum([1, 2], 3) == [1, 2]  # Smallest valid input

# Duplicate values
assert solution.twoSum([3, 3], 6) == [1, 2]  # Same value, different indices
assert solution.twoSum([1, 2, 2, 3], 4) == [1, 4]  # Duplicates present

# Negative and positive mix
assert solution.twoSum([-10, -3, 0, 5, 9], -13) == [1, 2]  # Two negatives
assert solution.twoSum([-5, -2, 0, 3, 8], 1) == [2, 4]  # Mixed values

# Solution at boundaries
assert solution.twoSum([1, 2, 3, 4, 10], 11) == [1, 5]  # First and last element

# Large values within constraints
assert solution.twoSum([-1000, 0, 1000], 0) == [1, 3]  # Constraint boundaries

# Middle elements
assert solution.twoSum([1, 3, 5, 7, 9], 12) == [2, 5]  # Pair in middle/end

Test	Why
[2,7,11,15], 9	Verifies standard example
[2,3,4], 6	Validates immediate match
[-1,0], -1	Ensures negatives work
[1,2], 3	Smallest valid input size
[3,3], 6	Confirms duplicate handling
[1,2,2,3], 4	Ensures duplicates do not break logic
[-10,-3,0,5,9], -13	Tests two negative numbers
[-5,-2,0,3,8], 1	Verifies mixed positive and negative values
[1,2,3,4,10], 11	Checks boundary elements
[-1000,0,1000], 0	Tests extreme constraint values
[1,3,5,7,9], 12	Validates non-adjacent match

Edge Cases

Arrays with duplicate values

A common source of bugs occurs when duplicate numbers exist. For example:

[3,3], target = 6

A careless implementation might accidentally reuse the same index twice. The two-pointer solution avoids this because left and right are always distinct positions. Even if the values are identical, the indices remain different.

Negative numbers

Some implementations implicitly assume all numbers are positive, which breaks when negatives appear.

For example:

[-1,0], target = -1

The two-pointer method still works because it relies only on the sorted ordering, not on positivity. Pointer movement decisions remain valid regardless of sign.

Solution at the boundaries

The valid pair may involve the first and last elements.

Example:

[1,2,3,4,10], target = 11

The optimal algorithm naturally handles this case because it begins with pointers at both ends. If the outermost elements form the answer, it returns immediately without unnecessary work.

Large input sizes

With arrays approaching 30,000 elements, brute-force solutions become inefficient due to quadratic growth.

The two-pointer solution scales efficiently because each pointer only moves inward once, ensuring linear time performance even for the largest valid inputs.