Difficulty: Medium · LeetCode 167

Problem

Given a 1-indexed sorted array of integers numbers, find two numbers that add up to target.

Understanding the problem

Array is already sorted in non-decreasing order.

Intuition

Leverage sorted property: two pointers at ends. If sum < target, increment left; if sum > target, decrement right.

Approach

Set left = 0, right = len(numbers) - 1.
Compute total = numbers[left] + numbers[right].
If total == target, return 1-based indices [left + 1, right + 1].
If total < target, move left += 1. Else move right -= 1.

Naive Solution — Brute Force

Try every pair with two nested loops.

Python

class Solution:
    def twoSum(self, numbers, target):
        for i in range(len(numbers)):
            for j in range(i + 1, len(numbers)):
                if numbers[i] + numbers[j] == target:
                    return [i + 1, j + 1]

        return []

C++

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        for (int i = 0; i < numbers.size(); i++)
            for (int j = i + 1; j < numbers.size(); j++)
                if (numbers[i] + numbers[j] == target)
                    return {i + 1, j + 1};
        return {};
    }
};

Java

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        for (int i = 0; i < numbers.length; i++)
            for (int j = i + 1; j < numbers.length; j++)
                if (numbers[i] + numbers[j] == target)
                    return new int[]{i + 1, j + 1};
        return new int[]{};
    }
}

JavaScript

var twoSum = function(numbers, target) {
    for (let i = 0; i < numbers.length; i++)
        for (let j = i + 1; j < numbers.length; j++)
            if (numbers[i] + numbers[j] === target)
                return [i + 1, j + 1];
    return [];
};

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

Optimized Code (Python 3)

Python

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

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

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

            if total < target:
                left += 1
            else:
                right -= 1

        return []

C++

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        int left = 0, right = numbers.size() - 1;
        while (left < right) {
            int total = numbers[left] + numbers[right];
            if (total == target) return {left + 1, right + 1};
            if (total < target) left++;
            else right--;
        }
        return {};
    }
};

Java

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int left = 0, right = numbers.length - 1;
        while (left < right) {
            int total = numbers[left] + numbers[right];
            if (total == target) return new int[]{left + 1, right + 1};
            if (total < target) left++;
            else right--;
        }
        return new int[]{};
    }
}

JavaScript

var twoSum = function(numbers, target) {
    let left = 0, right = numbers.length - 1;
    while (left < right) {
        const total = numbers[left] + numbers[right];
        if (total === target) return [left + 1, right + 1];
        if (total < target) left++;
        else right--;
    }
    return [];
};

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

Takeaway

Pattern — Sorted array + Target Sum → Two Pointers