What is the brute force approach and complexity for Two Sum II – Input Array Is Sorted?

Check every pair (i, j) with i < j with time complexity O(N²) and space complexity O(1).

What is the optimal approach and complexity for Two Sum II – Input Array Is Sorted?

Too small → move left right; too big → move right left with optimal time complexity O(N) and space complexity O(1).

How do you identify the pattern for Two Sum II – Input Array Is Sorted?

Look for key signals in the prompt: "already sorted" indicates The smallest and largest are at the ends, so one sum tells you which side is useless → opposite ends.; "two numbers that add up to target" indicates A pair, not a range. The two positions can be far apart.; "constant extra space" indicates Rules out the hash map. Two indexes is all we're allowed..

Two Sum II – Input Array Is Sorted

Q: What is the optimal approach and complexity for Two Sum II – Input Array Is Sorted?

Too small → move left right; too big → move right left with optimal time complexity O(N) and space complexity O(1).

Q: How do you identify the pattern for Two Sum II – Input Array Is Sorted?

Look for key signals in the prompt: "already sorted" indicates The smallest and largest are at the ends, so one sum tells you which side is useless → opposite ends.; "two numbers that add up to target" indicates A pair, not a range. The two positions can be far apart.; "constant extra space" indicates Rules out the hash map. Two indexes is all we're allowed..

Medium·LeetCode #167 Pro OnlyBasic Reinforcement

LeetCode

Problem Statement

You are given an array numbers that is already sorted from smallest to largest, and a number target.

Find two different positions whose values add up to exactly target. Return those two positions as [index1, index2], where positions are counted from 1 (not 0) and index1 < index2.

There is always exactly one such pair. You may not use the same position twice, and your solution should use only constant extra space.

Input

A sorted integer array numbers and an integer target.

Output

An array of two 1-based positions [index1, index2] with numbers[index1] + numbers[index2] == target.

Example 1

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

Output: [1, 2]

2 + 7 = 9. They are at positions 1 and 2 (counting from 1).

Example 2

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

Output: [1, 3]

2 + 4 = 6. Note that 3 + 3 is not allowed — that would use position 2 twice.

Example 3

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

Output: [1, 2]

−1 + 0 = −1.

Constraints

• 2 ≤ numbers.length ≤ 3 · 10^4
• −1000 ≤ numbers[i] ≤ 1000
• numbers is sorted in non-decreasing order
• −1000 ≤ target ≤ 1000
• Exactly one valid pair exists.

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“already sorted”

→ The smallest and largest are at the ends, so one sum tells you which side is useless → opposite ends.

“two numbers that add up to target”

→ A pair, not a range. The two positions can be far apart.

“constant extra space”

→ Rules out the hash map. Two indexes is all we're allowed.

Approach Complexity Ladder

Brute Force — try every pairO(N²)O(1)

Check every pair (i, j) with i < j

Better — binary search for the partnerO(N log N)O(1)

For each number, binary search the rest for target − number

Optimal — two pointers from both endsO(N)O(1)

Too small → move left right; too big → move right left

Brute Force Intuition

Try every pair of positions i < j. The first pair whose sum equals target is the answer.

Recognition rule for this sub-pattern:

Start at both ends of a sorted (or symmetric) structure. Each step, move the side that cannot do better.

Remember this · Two Pointers

Trigger

Sorted array, pairs/triplets with a target, comparing from both ends, compacting an array in place.

Think

If I compare the elements at two positions, can I safely discard one side?

Key question

Which pointer moves, and why can the skipped elements never be the answer?

Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms

Interactive step-by-step playback with pointer & array state transitions

52 comprehensive LLD chapters

Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions

40 C++ basics labs & hardware memory models

Vtables, byte layouts, assembly insights, and multi-threading race conditions

Production-ready C++23 source code

Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways

Create Free Account Log in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Two Pointers translate into production architectures and low-level memory mechanics.

LLD Architecture

Circular Buffer & Ring Queue

Two pointer read/write head synchronization in production memory pools.

Explore Track

C++ Internals

Pointers vs References Deep Dive

Pointer arithmetic, dereferencing semantics, and memory layout behind in-place array passes.

Explore Track

C++ Internals

const Correctness & East-Const

Passing read-only spans with const int* without copying buffers.

Explore Track

Valid Palindrome Reverse Vowels of a String