Input: nums = [-5, -2, 3, 4, 6], target = 7
Output: [2, 3]

Input: nums = [1, 1, 1], target = 2
Output: [0, 1]

In Plain English

New to this one? Start here. Below is the core idea in everyday language, plus a real-world analogy—then the sections that follow build on it with the formal reasoning, code, and step-by-step walkthroughs.

Intuition

The brute force solution to this problem involves checking all possible pairs. This is done using two nested loops: an outer loop that traverses the array for the first element of the pair, and an inner loop that traverses the rest of the array to find the second element. Below is the code snippet for this approach:

from typing import List

def pair_sum_sorted_brute_force(nums: List[int], target: int) -> List[int]:
    n = len(nums)
    for i in range(n):
        for j in range(i + 1, n):
            if nums[i] + nums[j] == target:
                return [i, j]
    return []

#include <vector>
using namespace std;

vector<int> pairSumSortedBruteForce(vector<int>& nums, int target) {
    int n = nums.size();
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {     // every pair with j right of i
            if (nums[i] + nums[j] == target) {
                return {i, j};                // first pair that works
            }
        }
    }
    return {};                                // no pair adds up to target
}

// This method lives inside a class, e.g. class Solution { ... }
public int[] pairSumSortedBruteForce(int[] nums, int target) {
    int n = nums.length;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {     // every pair with j right of i
            if (nums[i] + nums[j] == target) {
                return new int[]{i, j};       // first pair that works
            }
        }
    }
    return new int[]{};                       // no pair adds up to target
}

This approach has a time complexity of $O(n^2)$, where $n$ denotes the length of the array. This approach does not take into account that the input array is sorted. Could we use this fact to come up with a more efficient solution?

A two-pointer approach is worth considering here because a sorted array allows us to move the pointers in a logical way. Let's see how this works in the example below:

A good place to start is by looking at the smallest and largest values: the first and last elements, respectively. The sum of these two values is 1.

Since 1 is less than the target, we need to move one of our pointers to find a new pair with a larger sum.

• Left pointer: The left pointer will always point to a value less than or equal to the value at the right pointer because the array is sorted. Incrementing it would result in a sum greater than or equal to the current sum of 1.

• Right pointer: Decrementing the right pointer would result in a sum that’s less than or equal to 1.

Therefore, we should increment the left pointer to find a larger sum:

Again, the sum of the values at those two pointers (4) is too small. So, let's increment the left pointer:

Now, the sum (9) is too large. So, we should decrement the right pointer to find a pair of values with a smaller sum:

Finally, we found two numbers that yield a sum equal to the target. Let’s return their indexes:

Above, we’ve demonstrated a two-pointer algorithm using inward traversal. Let’s summarize this logic. For any pair of values at left and right:

• If their sum is less than the target, increment left, aiming to increase the sum towards the target value.

• If their sum is greater than the target, decrement right, aiming to decrease the sum towards the target value.

• If their sum is equal to the target value, return [left, right].

We can stop moving the left and right pointers when they meet, as this indicates no pair summing to the target was found.

Implementation

from typing import List

def pair_sum_sorted(nums: List[int], target: int) -> List[int]:
    left, right = 0, len(nums) - 1
    while left < right:
        sum = nums[left] + nums[right]
        # If the sum is smaller, increment the left pointer, aiming to increase the
        # sum towards the target value.
        if sum < target:
            left += 1
        # If the sum is larger, decrement the right pointer, aiming to decrease the
        # sum towards the target value.
        elif sum > target:
            right -= 1
        # If the target pair is found, return its indexes.
        else:
            return [left, right]
    return []

#include <vector>
using namespace std;

vector<int> pairSumSorted(vector<int>& nums, int target) {
    int left = 0;
    int right = (int)nums.size() - 1;
    while (left < right) {
        int sum = nums[left] + nums[right];
        // Sum too small: move left rightward to a bigger number.
        if (sum < target) {
            left++;
        // Sum too big: move right leftward to a smaller number.
        } else if (sum > target) {
            right--;
        // Found the target pair: return its indexes.
        } else {
            return {left, right};
        }
    }
    return {};
}

// This method lives inside a class, e.g. class Solution { ... }
public int[] pairSumSorted(int[] nums, int target) {
    int left = 0;
    int right = nums.length - 1;
    while (left < right) {
        int sum = nums[left] + nums[right];
        // Sum too small: move left rightward to a bigger number.
        if (sum < target) {
            left++;
        // Sum too big: move right leftward to a smaller number.
        } else if (sum > target) {
            right--;
        // Found the target pair: return its indexes.
        } else {
            return new int[]{left, right};
        }
    }
    return new int[]{};
}

Complexity Analysis

Time complexity: The time complexity of pair_sum_sorted is $O(n)$ because we perform approximately $n$ iterations using the two-pointer technique in the worst case.

Space complexity: We only allocated a constant number of variables, so the space complexity is $O(1)$.

Dry Runs

Two step-by-step walkthroughs of the algorithm below: a valid case (the expected happy path) and an invalid / edge case that exercises the tricky parts. Each step shows the program state as the code runs—the same steps apply to Python, C++ and Java.

The same steps in each language

Test Cases

In addition to the examples already discussed, here are some other test cases you can use. These extra test cases cover different contexts to ensure the code works well across a range of inputs. Testing is important because it helps identify mistakes in your code, ensures the solution works for uncommon inputs, and brings attention to cases you might have overlooked.

Interview Tip

Tip: Consider all information provided.
When interviewers pose a problem, they sometimes provide only the minimum amount of information required for you to start solving it. Consequently, it’s crucial to thoroughly evaluate all that information to determine which details are essential for solving the problem efficiently. In this problem, the key to arriving at the optimal solution is recognizing that the input is sorted.