{ }DevToolsDaily
ToolsInterview Prep
New
CheatsheetsDirectoryMy spaceBlog
Ctrl + K
Ask AI

Two Sum II - Input Array Is Sorted – Solution & Complexity

Interview solutions
/
Two Sum II - Input Array Is Sorted

Solution Walkthrough

  1. Step 1: Use the sorted order

    • The unsorted Two Sum needs a hash map, but here the array is already sorted.
    • A sorted array lets two converging pointers decide, in one comparison, whether the current pair is too small or too large.
    • Remember the required output is 1-based, so add one to each final index.

  2. Step 2: Converge two pointers

    • Start lo at the first element and hi at the last.
    • If numbers[lo] + numbers[hi] equals the target, you found the unique answer.
    • If the sum is too small, the only way to grow it is to move lo right; if it is too large, move hi left.

  3. Step 3: Why moving a pointer never skips the answer

    • If the sum is too small, every pair using the current lo with a smaller hi is even smaller, so lo can never pair with anything left of hi — safe to advance lo.
    • The symmetric argument justifies decrementing hi.
    • Because exactly one answer exists, the pointers are guaranteed to meet it before crossing.

  4. Step 4: Brute-force baseline

    • Checking every pair also works and needs no extra space, but costs O(n^2) time.
    • It is a useful correctness reference for the two-pointer version.
    def two_sum(numbers: list[int], target: int) -> list[int]:
    n = len(numbers)
    for i in range(n):
        for j in range(i + 1, n):
            if numbers[i] + numbers[j] == target:
                return [i + 1, j + 1]
    return []

  5. Step 5: Optimal two-pointer solution

    • Walk the two pointers toward each other, returning the 1-based indices on a match.
    • Time is O(n) and extra space is O(1).
    def two_sum(numbers: list[int], target: int) -> list[int]:
    lo, hi = 0, len(numbers) - 1
    while lo < hi:
        total = numbers[lo] + numbers[hi]
        if total == target:
            return [lo + 1, hi + 1]
        if total < target:
            lo += 1
        else:
            hi -= 1
    return []

  6. Step 6: Common mistakes

    • Returning 0-based indices instead of adding one for the 1-based contract.
    • Returning [hi + 1, lo + 1] — the smaller index must come first.
    • Using a nested loop when the sorted input makes the linear scan available.

FAQ

See also

Practice Two Sum II - Input Array Is Sorted online (run code in the browser)3Sum solution (medium)3Sum Closest solution (medium)Binary Search solution (easy)Container With Most Water solution (medium)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsPricingContact Us © Monkey SkatesHave kids?