Two Sum II - Input Array Is Sorted

Medium · two-pointer two-sum (1-indexed). Real solution for this problem — same player as the hand-authored deep-dives.

Problem

Read the prompt, flip through the examples, then steal the idea.

LeetCode 167. Two Sum II - Input Array Is Sorted. The copyrighted prompt is on LeetCode. This page is a working two-pointer two-sum (1-indexed) for this problem: editable input, Python, Go, and a step-by-step animation.

Constraints

—Player inputs are capped so the animation stays readable.
—Match LeetCode's own constraints when you submit there.

Examples

Input

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

Output

[1, 2]

Solution

Python and Go. The walkthrough below runs this same code.

Approach 1Optimal▶ Animated

Inward walk on a sorted array

The array is sorted. A too-small sum means advance lo; a too-big sum means retreat hi. Return 1-based indices.

Each comparison throws away an index forever, so the walk is linear. The problem asks for 1-based indices — add one at the end.

Algorithm

lo = 0, hi = n−1.
Equal → return [lo+1, hi+1]. Too small → lo++. Too big → hi--.

Time: O(n)
Space: O(1)

Solution.py

1class Solution:2    def twoSum(self, numbers: list[int], target: int) -> list[int]:3        lo, hi = 0, len(numbers) - 14        while lo < hi:5            s = numbers[lo] + numbers[hi]6            if s == target:7                return [lo + 1, hi + 1]8            if s < target:9                lo += 110            else:11                hi -= 112        return []

Watch this run

Interactive walkthrough

Playing “Inward walk on a sorted array”. Edit the input, hit Run, then scrub.

Approach: Inward walk on a sorted array

Loading animation…