30% off Lifetime Premium Access expires December 2nd!

30% off Lifetime Premium Access expires Dec 2nd!

Your Dashboard

Interview Coaching

Mock Interviews

1:1 Mentorship

Salary Negotiation

Practice

Learn

System Design

ML System Design

Code

Behavioral

Salary Negotiation

Interview Guides

Blog

Community

Interview Questions

Interview Experiences

Peer System Design Library

Ask The Community

Discord

Refer a Friend

Pricing

Become a Coach

⌘K

Pricing Become a Coach

⌘K

Get Premium

Leetcode 167. Two Sum II - Input Array Is Sorted

Given a sorted (non-decreasing) 1-indexed array, find two distinct elements whose sum equals a target and return their 1-based indices. Because the array is sorted and there is exactly one solution, this is typically solved in constant extra space using a two-pointer scan from both ends.

Asked at:

Google

DESCRIPTION

Given a sorted (non-decreasing) 1-indexed array, find two distinct elements whose sum equals a target and return their 1-based indices.

Input:


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

Output:


[1, 2]

Explanation: The elements at 1-based indices 1 and 2 are 2 and 7, which sum to 9

Constraints:

2 <= nums.length <= 3 * 10^4
-1000 <= nums[i] <= 1000
-1000 <= target <= 1000
nums is sorted in non-decreasing order
There is exactly one valid solution
The two elements must be at distinct indices

Understanding the Problem

Let's understand what we're being asked to do. We have a sorted array like [2, 7, 11, 15] and a target sum like target=9. We need to find two distinct elements that add up to the target and return their 1-based indices.

Tracing through: index 1 has value 2, index 2 has value 7. Check: 2+7=9 (matches target!). Return [1, 2] (1-based indices).

Important constraint: The array is already sorted in non-decreasing order, and there is exactly one solution. This means we don't need to handle cases where no solution exists or multiple solutions exist.

Edge cases to consider: What if the array has only two elements? What if the two elements are at opposite ends of the array? Remember that indices are 1-based, not 0-based!

Brute Force Approach

The brute force approach checks all possible pairs of elements using nested loops. For each element at index i, check every element at index j (where j > i) to see if their sum equals the target. When a matching pair is found, return their 1-based indices. This approach is straightforward but inefficient because it doesn't leverage the sorted property of the array.

def two_sum_brute_force(nums, target):
    """
    Find two distinct elements in sorted array that sum to target.
    Returns their 1-based indices using brute force approach.
    """
    n = len(nums)
    
    # Check all possible pairs
    for i in range(n):
        for j in range(i + 1, n):
            # Calculate sum of current pair
            current_sum = nums[i] + nums[j]
            
            # Check if sum equals target
            if current_sum == target:
                # Return 1-based indices
                return [i + 1, j + 1]
    
    # No solution found (should not happen per problem statement)
    return []

Start two sum brute force algorithm

0 / 23

Test Your Knowledge

Complexity Analysis

Time Complexity: O(n²) We use nested loops to check all possible pairs, resulting in approximately n*(n-1)/2 comparisons

Space Complexity: O(1) We only use a constant amount of extra space for loop counters and comparison variables

Building Intuition

Since the array is sorted, if we pick two elements and their sum is too large, we need to try a smaller element. If their sum is too small, we need to try a larger element.

By starting with pointers at both ends of the array, we can make smart decisions about which direction to move based on whether the current sum is too large or too small.

This observation means we can find the solution in a single pass through the array without checking all possible pairs.

Instead of checking n*(n-1)/2 pairs (which would be O(n²)), we only need to check at most n pairs by intelligently moving our pointers inward. The sorted property is what makes this optimization possible!

Imagine you're standing at opposite ends of a number line. If you're too far apart (sum too large), the person on the right steps left. If you're too close (sum too small), the person on the left steps right.

You keep adjusting until you meet at exactly the right distance. The sorted property guarantees that moving left always decreases the sum and moving right always increases it, so you'll never miss the solution.

Common Mistakes

Forgetting to convert from 0-based to 1-based indices when returning the result

Moving both pointers simultaneously instead of moving only one based on the comparison result

Not handling the case where pointers cross without finding a solution (though this problem guarantees a solution exists)

Using the same index twice - the problem requires two distinct elements at different positions

Incorrect pointer movement logic: moving left pointer when sum is too large, or right pointer when sum is too small

Optimal Solution

The optimal approach uses two pointers starting at opposite ends of the sorted array. Calculate the sum of elements at both pointers. If the sum equals the target, return the 1-based indices. If the sum is less than the target, move the left pointer right to increase the sum. If the sum is greater than the target, move the right pointer left to decrease the sum. This converges to the solution in a single pass by exploiting the sorted property.

def two_sum_sorted(nums, target):
    """
    Find two distinct elements in sorted array that sum to target.
    Returns their 1-based indices.
    """
    # Initialize two pointers at opposite ends
    left = 0
    right = len(nums) - 1
    
    # Scan from both ends toward center
    while left < right:
        current_sum = nums[left] + nums[right]
        
        # Check if we found the target sum
        if current_sum == target:
            # Return 1-based indices
            return [left + 1, right + 1]
        elif current_sum < target:
            # Sum too small, move left pointer right to increase sum
            left += 1
        else:
            # Sum too large, move right pointer left to decrease sum
            right -= 1
    
    # Should never reach here if exactly one solution exists
    return []

Start two-pointer search on sorted array

0 / 12

Test Your Knowledge

Complexity Analysis

Time Complexity: O(n) We traverse the array at most once with two pointers moving toward each other, checking at most n elements total

Space Complexity: O(1) We only need two pointer variables regardless of array size, using constant extra space

What We've Learned

Two-pointer convergence on sorted arrays: When you have a sorted array and need to find pairs meeting a condition, use opposing pointers (left at start, right at end) - the sorted property lets you intelligently move pointers based on whether the current sum is too high (move right pointer left) or too low (move left pointer right), guaranteeing O(n) time.
Space-time tradeoff awareness: While a hash map would solve this in one pass, the sorted array property enables an O(1) space solution with two pointers - recognize when problem constraints (like sorted input) allow you to avoid extra space by leveraging inherent structure.
Index adjustment for 1-based arrays: When problems specify 1-indexed returns, add 1 to your 0-based loop indices at the return statement only - keep all internal logic 0-indexed to avoid off-by-one errors, then convert at the boundary.
Pointer movement logic: The critical insight is monotonic adjustment - if `arr[left] + arr[right] < target`, left must move right (no point checking smaller right values), and vice versa - this eliminates the need to check all O(n²) pairs by pruning impossible combinations.
Sorted array pattern recognition: Whenever you see sorted input combined with pair/triplet sum problems, immediately consider two-pointer techniques - this pattern extends to 3Sum, 4Sum, and container problems where sorted order enables intelligent search space reduction.
Guaranteed solution handling: When the problem states exactly one solution exists, you can safely return immediately upon finding a match without defensive null checks - but in real-world scenarios, always add validation to handle the no-solution case by returning after the loop completes.

Test Your Understanding

Why is array the right data structure for this problem?

array provides the optimal access pattern

It's the only data structure that works

It's the easiest to implement

It uses the least memory

Select an answer to see the explanation

Question Timeline

See when this question was last asked and where, including any notes left by other candidates.

Company

Level

Region

Early November, 2025

Google

Mid-level

Comments

Your account is free and you can post anonymously if you choose.

Hello Interview Premium

Recent interview questions

System Design Guided Practice

Exclusive content

Learn More

Leetcode 167. Two Sum II - Input Array Is Sorted

DESCRIPTION

Understanding the Problem

Brute Force Approach

Test Your Knowledge

Complexity Analysis

Building Intuition

Common Mistakes

Optimal Solution

Test Your Knowledge

Complexity Analysis

What We've Learned

Related Concepts and Problems to Practice

Test Your Understanding

Question Timeline

Comments

Questions

Learn

Links

Legal

Contact