Two Sum Ii - Input Array Is Sorted

Two Sum II – Input Array Is Sorted: A Complete Guide for Developers

Two Sum II – Input Array Is Sorted is a classic algorithmic problem that appears frequently in coding interviews and competitive programming platforms. The task is simple in concept but offers multiple solution strategies, each with distinct trade‑offs in time and space complexity. In this article we’ll explore the problem statement, walk through the most efficient approaches, analyze their performance, and provide practical code examples. Whether you’re preparing for technical interviews or just love solving puzzles, mastering this problem will sharpen your algorithmic thinking and deepen your understanding of how sorted data can be leveraged for faster solutions.

Problem Statement

Given an array of integers numbers that is already sorted in non‑decreasing order, find two distinct indices i and j (with i < j) such that

numbers[i] + numbers[j] == target

The problem guarantees that exactly one valid solution exists, and you must return the indices as a 1‑based array (i.e., the first element of the array is at position 1). Because the input is sorted, you can exploit this property to avoid the naïve O(n²) brute‑force search Less friction, more output..

Why Sorted Input Matters

When an array is sorted, any two elements that sum to a target will have a predictable relationship: moving forward in the array increases the value of numbers[j]. This monotonic behavior is the key that unlocks the two‑pointer technique, an O(n) solution that is both intuitive and highly efficient. Understanding this relationship will help you recognize when similar optimizations can be applied to other problems.

You'll probably want to bookmark this section.

Brute‑Force Approach

The most straightforward method is to pick each element numbers[i], then scan the rest of the array for a complementary value target - numbers[i] Easy to understand, harder to ignore..

Iterate i from 0 to n‑2.
For each i, iterate j from i + 1 to n‑1.
If numbers[i] + numbers[j] == target, return [i+1, j+1].

While this approach is easy to implement, its time complexity is O(n²) and it completely ignores the sorted nature of the array. It’s useful only for tiny inputs or as a baseline for comparison Most people skip this — try not to..

Two‑Pointer Technique (Optimal Solution)

The two‑pointer method leverages the sorted order to eliminate unnecessary checks.

Initialize left = 0 (first element) and right = n‑1 (last element).
Compute currentSum = numbers[left] + numbers[right].
If currentSum == target, return [left+1, right+1].
If currentSum < target, increment left (move to a larger number).
If currentSum > target, decrement right (move to a smaller number).
Repeat until the pointers meet – the problem guarantees a solution, so the loop will always terminate with a result.

The intuition is simple: because the array is sorted, increasing left raises the sum, while decreasing right lowers it. By adjusting the pointers based on how the current sum compares to the target, we converge on the correct pair in a single pass That's the part that actually makes a difference..

Pseudocode

function twoSumII(numbers, target):
    left = 0
    right = length(numbers) - 1
    while left < right:
        s = numbers[left] + numbers[right]
        if s == target:
            return [left + 1, right + 1]
        else if s < target:
            left = left + 1
        else:
            right = right - 1

Complexity Analysis

Approach	Time Complexity	Space Complexity
Brute‑Force	O(n²)	O(1)
Two‑Pointer	O(n)	O(1)

The two‑pointer technique dominates in terms of speed while using constant extra memory, making it the preferred solution for production code and interview settings.

Code Implementation

Below are ready‑to‑run implementations in Python and Java. Both follow the two‑pointer pattern and return the required 1‑based indices.

Python

def two_sum_ii(numbers, target):
    left, right = 0, len(numbers) - 1
    while left < right:
        current_sum = numbers[left] + numbers[right]
        if current_sum == target:
            return [left + 1, right + 1]   # 1‑based indices
        elif current_sum < target:
            left += 1
        else:
            right -= 1
    # According to the problem statement a solution always exists,
    # so this line is never reached.
    return []

Java

public class TwoSumII {
    public int[] twoSum(int[] numbers, int target) {
        int left = 0;
        int right = numbers.length - 1;
        while (left < right) {
            int sum = numbers[left] + numbers[right];
            if (sum == target) {
                return new int[]{left + 1, right + 1}; // 1‑based
            } else if (sum < target) {
                left++;
            } else {
                right--;
            }
        }
        throw new IllegalArgumentException("No solution found");
    }
}

Both snippets are concise, readable, and directly reflect the algorithm’s logic.

Edge Cases and Pitfalls

Duplicate values: Because the array is sorted, duplicates appear consecutively. The two‑pointer method still works; it will simply skip over them when adjusting pointers.
Negative numbers: The algorithm does not assume positivity; it works for any integer range as long as the array remains sorted.
Large target values: If target exceeds the sum of the two largest elements, the loop will eventually move left past right before finding a match – but the problem guarantees a solution, so this scenario never occurs.
Single‑element array: Not possible per problem constraints (you need at least two numbers).

A common mistake is forgetting to return 1‑based indices. Always remember to add +1 when constructing the result array Less friction, more output..

Frequently Asked Questions

Q: Can I solve this problem using binary search?
A: Yes. For each element numbers[i], you can binary‑search for target - numbers[i] in the subarray i+1 … n‑1. This yields O(n log n) time and O(1) space, which is slower than the two‑pointer O(n) solution but still acceptable for moderate input sizes.

Q: What if the array is not sorted?
A: The two‑pointer technique cannot be applied directly. In that case you would typically use a hash map (dictionary) to store seen values, achieving O(n) time with O(n) space – this is the classic Two Sum problem Small thing, real impact..

**Q: Are there any variations that ask for the values instead of

Frequently Asked Questions

Q: Are there any variations that ask for the values instead of indices?
A: Absolutely. Many interview problems tweak the output requirement, and the two‑pointer technique can often be adapted with minimal changes:

Returning the actual numbers – Some formulations ask you to output the two elements that sum to the target rather than their positions. Since the array is sorted, you can simply return numbers[left] and numbers[right] after the pointers meet. This is useful when the caller only needs the pair’s values (e.g., for reporting or further arithmetic).
Finding all unique pairs – When the input may contain duplicates, you might be required to list every distinct combination that satisfies the condition. The two‑pointer method shines here: after a successful match, advance left past all identical values and retreat right past its duplicates before continuing, ensuring each pair is reported exactly once.
Closest‑to‑target pair – Instead of an exact match, you may need the pair whose sum is nearest to a given target (e.g., “Two Sum Less Than K”). By keeping track of the best difference seen so far while moving the pointers, you can solve this in a single pass with O(1) extra space Easy to understand, harder to ignore. Simple as that..
Minimum absolute difference – A related twist asks for the pair with the smallest absolute difference among all possible sums. The sorted nature again allows a linear scan: maintain the current minimum difference and update it whenever a new sum is examined And it works..
Two Sum III – Data structure design – Here you must support add(val) and find(target) operations on a dynamic collection. The static two‑pointer approach isn’t directly applicable, but you can store numbers in a sorted list (e.g., using TreeSet in Java or bisect.insort in Python) and reuse the same logic inside find.
Two Sum IV – Input is a BST – The problem flips the container: a binary search tree replaces the sorted array. You can perform an in‑order traversal to obtain a sorted stream and then apply the two‑pointer logic on the fly, or use a hash set during a standard tree traversal for a simpler O(n) solution.

Each of these variations preserves the core idea of leveraging sorted order (or its equivalent) to avoid the O(n²) brute‑force search, while the implementation details shift slightly to meet the new output constraints.

Practical Tips

Always verify the index‑base requirement early in your implementation. Adding +1 for 1‑based indexing is a frequent source of off‑

Two Sum Ii - Input Array Is Sorted