Problems/Two Pointers/Pair Sum - Sorted
Two Pointers
easy

Pair Sum - Sorted

The problem asks to find two numbers in a sorted array that add up to a specific target value. It's a classic interview question testing your ability to leverage data ordering for efficient searching.

arraytwo-pointerssorted arraysearchingalgorithm

Problem Statement

Given a sorted array of integers in ascending order and a target integer, find the indices of any two distinct numbers in the array that sum exactly to the target. If no such pair exists, return an empty list. The order of the indices in the returned list does not matter.

Example 1
Input: numbers = [2, 7, 11, 15], target = 9
Output: [0, 1]
numbers[0] + numbers[1] = 2 + 7 = 9, so the indices 0 and 1 are returned.
Example 2
Input: numbers = [-3, 0, 1, 5, 9], target = 6
Output: [1, 4]
numbers[1] + numbers[4] = 0 + 6 = 6, so the indices 1 and 4 are returned.
Constraints
  • -The input array will be sorted in ascending order.
  • -The array will contain at least two elements.
  • -The numbers in the array may be positive, negative, or zero.
  • -The target value may be positive, negative, or zero.
  • -You need to return the indices of the two numbers, not the numbers themselves.

Brute Force Approach

The most straightforward way to solve this is to check every possible pair of numbers in the array. Imagine you're at a potluck and need to find two dishes that, when combined, have exactly 1000 calories. You'd pick up each dish one by one and try it with every other dish until you find a pair that fits. This involves nested loops, leading to a higher time complexity.

TimeO(n^2)
SpaceO(1)

Ready to practice?

Work through this problem with AI coaching and get real-time feedback

Practice This Problem