LeetCode #167: Two Sum II — Input Array Is Sorted

LeetCode Problem: Two Sum II — Input Array Is Sorted
Difficulty: Medium
Topics: Array, Two Pointers, Binary Search
Series: LeetCode Interview Preparation — From Beginner to Expert

In our first LeetCode article, we solved Two Sum using a Hash Map.

Now we're going to revisit the same fundamental problem—but with one important change:

The array is already sorted.

That single constraint completely changes our strategy.

Instead of using extra memory with a Hash Map, we can use one of the most important interview patterns in DSA:

Two Pointers

This pattern appears everywhere in technical interviews, especially in problems involving:

• Sorted arrays
• Pairs
• Searching from both ends
• Removing duplicates
• Partitioning
• Palindromes
• Sliding-window-style reasoning

If you're preparing for coding interviews, Two Pointers is a pattern you absolutely need to master.

The Problem

You are given a 1-indexed array of integers:

numbers

that is already sorted in non-decreasing order.

You are also given:

target

Find two numbers such that:

numbers[i] + numbers[j] = target

where:

1 <= i < j <= numbers.length

Return their indices.

You may assume that exactly one solution exists.

Example

Consider:

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

We need:

2 + 7 = 9

Therefore:

Output:
[1, 2]

Remember that LeetCode's problem uses 1-based indexing here.

So:

2 → index 1
7 → index 2

Why Is the Sorted Array Important?

In the original Two Sum problem, the array wasn't necessarily sorted.

We used a Hash Map:

number → index

But now the input is sorted:

[2, 7, 11, 15]

That gives us valuable information.

If our current sum is:

2 + 15 = 17

and the target is:

9

our sum is too large.

Because the array is sorted, we know that moving the right pointer to the left will make the number smaller.

Therefore:

Move right pointer left.

Similarly, if:

2 + 7 = 9

we're done.

And if:

2 + 7 = 9

were too small, we'd move the left pointer right to increase the sum.

This is the magic of sorted data.

The Two-Pointer Idea

Place two pointers:

left
right

at opposite ends.

For:

[2, 7, 11, 15]

we start:

 L              R
 ↓              ↓
[2, 7, 11, 15]

Calculate:

2 + 15 = 17

Target:

9

Since:

17 > 9

we need a smaller sum.

Move:

right--

Now:

 L          R
 ↓          ↓
[2, 7, 11, 15]

Calculate:

2 + 11 = 13

Still too large.

Move right again:

 L   R
 ↓   ↓
[2, 7, 11, 15]

Now:

2 + 7 = 9

Found it.

The Algorithm

The algorithm is extremely simple.

Step 1

Set:

left = 0
right = len(numbers) - 1

Step 2

Calculate:

current_sum = numbers[left] + numbers[right]

Step 3

Compare the sum with the target.

If:

current_sum == target

return the indices.

If:

current_sum < target

move:

left += 1

If:

current_sum > target

move:

right -= 1

Step 4

Continue until the pointers meet.

Python Solution

def twoSum(numbers, target):
    left = 0
    right = len(numbers) - 1

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

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

        elif current_sum < target:
            left += 1

        else:
            right -= 1

    return []

Notice:

left + 1
right + 1

because the problem uses 1-based indexing.

Let's Understand Why Moving the Pointers Works

This is the most important part of the problem.

Suppose:

numbers = [1, 3, 5, 7, 9]
target = 10

Initially:

1 + 9 = 10

Done.

But suppose target were:

12

We start with:

1 + 9 = 10

The sum is too small.

Could moving right help?

No.

Moving right left would make the right value smaller:

1 + 7 = 8

That's even worse.

So the only useful move is:

left++

Now:

3 + 9 = 12

Found.

The Three Rules

Memorize these rules—not the code.

If:

current_sum < target

We need a larger sum.

Therefore:

left++

If:

current_sum > target

We need a smaller sum.

Therefore:

right--

If:

current_sum == target

We've found the answer.

Dry Run

Let's use a slightly larger example:

numbers = [2, 3, 4, 8, 11, 15]
target = 12

Initially:

left = 0
right = 5

Values:

2 + 15 = 17

Too large.

Move right:

right = 4

Now:

2 + 11 = 13

Still too large.

Move right:

right = 3

Now:

2 + 8 = 10

Too small.

Move left:

left = 1

Now:

3 + 8 = 11

Still too small.

Move left:

left = 2

Now:

4 + 8 = 12

Found.

Answer:

[3, 4]

because the problem uses 1-based indexing.

Dry Run Table

Final answer:

[3, 4]

Why Is This O(n)?

At first glance, you might think we're repeatedly searching the array.

We're not.

Each pointer only moves in one direction.

The left pointer starts at:

0

and can move at most:

n - 1

steps.

The right pointer also moves at most:

n - 1

steps.

Together, they perform at most roughly n useful pointer movements.

Therefore:

Time Complexity = O(n)

Space Complexity

We only use:

left
right
current_sum

No additional array or hash map is required.

Therefore:

Space Complexity = O(1)

This is one of the biggest advantages over the Hash Map solution.

Hash Map vs Two Pointers

Now we can compare our first Two Sum problem with this one.

This teaches an extremely important interview lesson:

Input constraints are often clues to the intended algorithm.

If the interviewer tells you:

"The array is sorted."

Don't ignore that information.

Ask:

"Can I exploit the sorted order?"

Very often, the answer is yes.

Why Not Use a Hash Map Again?

We could.

For example:

def twoSum(numbers, target):
    seen = {}

    for i, num in enumerate(numbers):
        complement = target - num

        if complement in seen:
            return [seen[complement] + 1, i + 1]

        seen[num] = i

    return []

This would work.

But we're using:

O(n)

extra memory even though the sorted property allows us to solve the problem using:

O(1)

space.

A strong interview candidate doesn't just find a solution.

They look for the best solution under the given constraints.

Common Mistake #1: Moving the Wrong Pointer

Suppose:

current_sum < target

You need a bigger sum.

Moving:

right--

would make the right value smaller.

That's the wrong direction.

Correct:

left++

Common Mistake #2: Forgetting 1-Based Indexing

This problem is slightly different from normal Python indexing.

Python uses:

0, 1, 2, 3...

But the problem expects:

1, 2, 3, 4...

Therefore:

return [left + 1, right + 1]

is necessary.

Common Mistake #3: Using Two Pointers on an Unsorted Array

This technique depends on the array being sorted.

Consider:

[8, 1, 7, 3, 5]

You cannot blindly use the same pointer logic.

Why?

Because moving a pointer no longer guarantees that the sum will increase or decrease predictably.

The sorted property is what makes the algorithm work.

Common Mistake #4: Sorting the Input Yourself

You might think:

numbers.sort()

and then use two pointers.

But if the problem asks for original indices, sorting destroys the relationship between values and their original positions.

If sorting is allowed, you'd need to preserve the original indices.

But for Two Sum II, the array is already sorted, so we don't have this problem.

The General Two-Pointer Pattern

Two Sum II gives us a reusable pattern:

        Sorted Array
             ↓
      L             R
      ↓             ↓
   [ ... ... ... ... ]
             ↓
       Calculate Sum
             ↓
     ┌───────┼───────┐
     ↓       ↓       ↓
   Too Low  Equal  Too High
     ↓       ↓       ↓
    L++    Found    R--

This pattern is incredibly powerful.

Where Else Do Two Pointers Appear?

Once you understand this problem, you'll start seeing two pointers everywhere.

Palindrome

Check characters from both ends:

L →       ← R

Move inward.

Remove Duplicates

Use one pointer to read and another to write.

Container With Most Water

Use two pointers at the ends and move the limiting side.

3Sum

Sort the array and combine:

one fixed pointer
+
two-pointer search

Merge Sorted Arrays

Use separate pointers to traverse both arrays.

Linked Lists

Use:

slow
fast

pointers.

This becomes the famous Fast & Slow Pointer pattern.

How to Recognize Two Pointers

During an interview, look for these signals:

• Array is sorted
• Find a pair
• Find two values satisfying a condition
• Search from both ends
• Compare values from opposite sides
• Remove duplicates
• Find a palindrome
• Merge sorted sequences
• Need O(1) extra space

Whenever you see a sorted array + pair relationship, immediately consider:

Two Pointers.

Interview Thought Process

Don't start by saying:

"I remember Two Sum II uses two pointers."

Instead, reason your way to it.

You can tell the interviewer:

"Because the array is sorted, I can place one pointer at the beginning and one at the end. If their sum is smaller than the target, I need a larger value, so I move the left pointer forward. If their sum is larger, I move the right pointer backward. Each pointer moves at most n times, giving O(n) time and O(1) extra space."

That's a much stronger answer.

You're demonstrating understanding rather than memorization.

A Deeper Insight: Monotonic Movement

Why are two pointers so efficient?

Because the pointers never move backward.

For example:

left:
0 → 1 → 2 → 3 → ...

right:
n-1 → n-2 → n-3 → ...

Every movement eliminates a set of impossible pairs.

That's the deeper reason the algorithm is linear.

We're not checking:

every pair

We're systematically eliminating possibilities.

Can We Use Binary Search?

Yes.

For each number:

complement = target - number

we could binary-search for the complement.

That would produce approximately:

O(n log n)

time.

But Two Pointers is better here:

O(n)

and uses:

O(1)

extra space.

This is another useful interview lesson:

Knowing multiple approaches helps you choose the best one.

Interview Follow-Up Questions

Once you solve Two Sum II, the interviewer may increase the difficulty.

Follow-Up 1

What if there are multiple valid pairs?

Now you might need to find all valid pairs.

Follow-Up 2

What if the array is not sorted?

You can discuss:

• Hash Map
• Sorting + two pointers

and explain the trade-offs.

Follow-Up 3

What if we need three numbers?

This leads directly toward:

3Sum — LeetCode #15

The standard solution uses:

Sorting
+
Two Pointers

Follow-Up 4

What if we need four numbers?

This leads toward:

4Sum — LeetCode #18

and more advanced variations.

Follow-Up 5

What if we need the pair whose sum is closest to the target?

Now you modify the pointer logic to track:

minimum absolute difference

Connection to the Previous Problems

Our series is now developing recognizable patterns.

Two Sum

Pattern:
Hash Map

Best Time to Buy and Sell Stock

Pattern:
Running Minimum

Contains Duplicate

Pattern:
Hash Set

Maximum Subarray

Pattern:
Kadane's Algorithm

Two Sum II

Pattern:
Two Pointers

This is how you should study LeetCode.

Don't think:

"I need to solve 500 random problems."

Think:

"I need to master the major problem-solving patterns."

Once you understand a pattern, many problems become variations of the same idea.

Interview Cheat Sheet

Problem:
Find two numbers in a sorted array
whose sum equals target.

Input:
Sorted array.

Technique:
Two Pointers.

Initialize:

left = 0
right = n - 1

While left < right:

    current_sum =
        numbers[left] + numbers[right]

    If current_sum == target:
        return indices

    If current_sum < target:
        left += 1

    Else:
        right -= 1

Complexity:

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

Practice Challenges

Before moving to the next article, try these:

Challenge 1

Find whether a sorted array contains a pair with a given sum.

Challenge 2

Find all unique pairs with a target sum.

Challenge 3

Find the pair whose sum is closest to the target.

Challenge 4

Solve 3Sum using sorting and two pointers.

Challenge 5

Solve 4Sum.

Challenge 6

Determine whether a string is a palindrome using two pointers.

These problems will turn the Two Pointer technique into a natural instinct.

Final Takeaway

The biggest lesson from LeetCode #167 isn't the code.

It's this:

Sorted data contains information. Use it.

In the original Two Sum problem, we needed a Hash Map because the array gave us no ordering information.

In Two Sum II, the array is sorted.

That allows us to replace:

Hash Map
O(n) space

with:

Two Pointers
O(1) space

The algorithm is simple:

Sum too small → move left
Sum too large → move right
Sum equal → answer

But the deeper interview skill is recognizing why those pointer movements are valid.

That's the difference between memorizing a LeetCode solution and actually understanding algorithms.

As this Kairos Coders series progresses, we'll keep building these patterns one by one—until problems that initially look completely unfamiliar start looking like combinations of techniques you've already mastered.