Find Pair Indices in Sorted Array

You're sitting in a Google phone screen when the interviewer says, "I'll give you a sorted array of numbers and a target. Find two numbers that add up to the target and give me their positions." You recognize it immediately. This is the sorted variant of Two Sum, and it's been asked at Adobe, Apple, Amazon, Microsoft, and pretty much every tech company with a whiteboard. On Firecode, we call it "Find Pair Indices in Sorted Array," but you'll find this problem across interview platforms under the name Two Sum II - Input Array Is Sorted. The sorted constraint is what makes this version interesting, because it unlocks an elegant O(1) space solution that the original unsorted Two Sum can't match.

TL;DR

Place two pointers at opposite ends of the sorted array. Compute the sum: if it matches the target, return those indices. If the sum is too small, advance the left pointer. If it's too large, retreat the right pointer. Since the array is sorted, this converges on the answer in O(n) time using O(1) space. Return 1-based indices.

Prefer a different language? Jump to solutions in other languages.

Why This Problem Matters

Two Sum is the gateway drug to the two-pointer technique. It shows up everywhere: 3Sum builds on it, Container With Most Water uses the same pattern, and interviewers love it because it has a clean progression from brute force to optimal. If you can only master one array problem before your interview, make it this one.

The Setup

Given a sorted array numbers (1-indexed) and an integer target, find two distinct indices where the values sum to target. Return the indices as a length-2 array, incremented by one.

For the array [2, 7, 11, 15] with target 9, the answer is [1, 2] because numbers[1] + numbers[2] = 2 + 7 = 9.

Constraints

• 2 <= numbers.length <= 3 * 10^4
• -1000 <= numbers[i] <= 1000
• The array is sorted in non-decreasing order
• Exactly one solution exists
• You cannot use the same element twice
• Only constant extra space allowed

Edge Cases

1. Minimum array (two elements): The pair is always indices 1 and 2
2. Negative numbers: [-1, 0] with target -1 returns [1, 2]
3. Duplicate values: [1, 1, 1, 2, 3] - the sorted property still guides the pointers correctly
4. Wide spread: [5, 25, 75] with target 100 - pointers start far apart and converge

Brute Force (and Why You Shouldn't Stop There)

The naive approach checks every pair:

// O(n^2) time, O(1) space - don't submit this in an interview
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};
    }
  }
}

This works but runs in O(n^2) time. For an array of 30,000 elements, that's 450 million comparisons. The interviewer is waiting for you to notice the array is sorted and leverage that.

The Two-Pointer Approach

Here's the key insight: in a sorted array, the smallest value is at the left and the largest is at the right. If you add these two extremes:

• Sum too large? The right value is too big. Move right left to try a smaller number.
• Sum too small? The left value is too small. Move left right to try a larger number.
• Sum matches? You found the pair.

Start: left=0 points to 2, right=3 points to 15. Sum = 17 > 9, so move right left.

Step 1: left=0, right=2. Sum = 2 + 11 = 13 > 9, so move right left again.

Step 2: left=0, right=1. Sum = 2 + 7 = 9 = target. Return [1, 2].

The pointers always converge because exactly one solution exists and each step eliminates at least one candidate from consideration.

Pointer Evolution

Here's the full trace as a state diagram:

Each step either moves left right (increasing the sum) or right left (decreasing the sum). The algorithm terminates the moment the sum hits the target.

Implementation

Java

public class Solution {
  public int[] twoSum(int[] numbers, int target) {
    int left = 0;
    int right = numbers.length - 1;

    while (left < right) {
      int sum = numbers[left] + numbers[right];

      if (sum == target) {
        return new int[]{left + 1, right + 1};
      } else if (sum < target) {
        left++;
      } else {
        right--;
      }
    }

    return new int[]{-1, -1}; // Unreachable given problem constraints
  }
}

Python

class Solution:
    def two_sum(self, numbers: list[int], target: int) -> list[int]:
        left, right = 0, len(numbers) - 1

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

            if current_sum == target:
                return [left + 1, right + 1]
            elif current_sum < target:
                left += 1
            else:
                right -= 1

        return []  # Unreachable given problem constraints

The logic is identical in both languages. Two variables, one loop, three branches. That's the entire algorithm.

Walkthrough with a Larger Example

Let's trace through [1, 3, 4, 5, 7, 10, 11] with target 9:

The pointers took 5 steps to converge on indices 2 and 3 (0-based), returning [3, 4] (1-based). Even with 7 elements, the algorithm never backtracks. Each step permanently narrows the search window.

Complexity Analysis

Time: O(n)

Each iteration advances at least one pointer inward. The left pointer only moves right. The right pointer only moves left. Together they start n-1 positions apart and close by at least 1 per step, so the loop runs at most n-1 times. Every operation inside the loop (one addition, two comparisons, one pointer move) is O(1).

Space: O(1)

Three variables: left, right, sum. No hash maps, no auxiliary arrays, no recursion stack. This is the main advantage over the unsorted Two Sum, which needs an O(n) hash map.

Why Not Binary Search?

You could fix one pointer and binary search for the complement, giving O(n log n) time. It works, but it's slower than two pointers and harder to code correctly. Mention it as an alternative approach if the interviewer asks, but lead with two pointers.

Common Pitfalls

1. 1-based vs 0-based indexing: The problem says the array is 1-indexed. Forgetting + 1 when returning indices is the most common bug.

2. Moving the wrong pointer: If the sum is too large, move right left (not left right). I've seen candidates mix this up under pressure - trace through one example before coding.

3. Using a hash map: It works, but it uses O(n) space. The interviewer gave you a sorted array for a reason. Reaching for a hash map here is like using a sledgehammer to hang a picture frame.

4. Off-by-one on the while condition: Use left < right, not left <= right. When they're equal, you'd be using the same element twice.

Interview Tips

When you get this problem in an interview:

1. Clarify constraints first: "Is the array sorted? Is there exactly one solution? Are the indices 1-based?" These questions show you read carefully.

2. Start with the brute force: Briefly mention the O(n^2) approach to establish a baseline, then explain why sorting enables something better.

3. Draw the array: Sketch the example on the whiteboard with arrows for left and right. Walk through 2-3 iterations showing how the pointers move.

4. State the complexity upfront: "This runs in O(n) time and O(1) space" before you start coding. It shows you know where you're headed.

5. Handle the follow-up: The interviewer might ask "What if the array isn't sorted?" That's the classic Two Sum - use a hash map for O(n) time, O(n) space. Showing you know both variants is a strong signal.

Key Takeaways

• Two pointers on a sorted array gives O(n) time and O(1) space, beating both brute force O(n^2) and hash map O(n) space approaches.
• The invariant is simple: if the sum is too small, the left value needs to grow; if it's too large, the right value needs to shrink. Sorted order guarantees this works.
• Always return 1-based indices when the problem specifies 1-indexed input. This is the number one source of wrong answers on this problem.
• The two-pointer pattern transfers directly to 3Sum, Container With Most Water, and dozens of other sorted-array problems. Master it here, and the pattern will feel natural everywhere else.
• When the interviewer gives you a sorted array, that's a hint. Don't ignore it by reaching for a hash map.

Related Problems

Once you're comfortable with this two-pointer pattern, try these:

• Zero-Sum Triplet Finder (3Sum) - extend the technique to three numbers
• Maximize Water Storage Between Lines (Container With Most Water) - two pointers on heights
• Eliminate Node from Tail of Linked List - two pointers at different speeds
• Pivoted Array Target Search - binary search on a rotated sorted array

These are all available on Firecode, where over 50,000 engineers have prepared for technical interviews and landed roles at top tech companies. The two-pointer technique you just learned will come up again and again. Build the muscle memory now.

Solutions in Other Languages

JavaScript

class Solution {
  twoSum(numbers, target) {
    let left = 0;
    let right = numbers.length - 1;

    while (left < right) {
      const sum = numbers[left] + numbers[right];
      if (sum === target) {
        return [left + 1, right + 1];
      } else if (sum < target) {
        left++;
      } else {
        right--;
      }
    }
  }
}

TypeScript

class Solution {
  twoSum(numbers: number[], target: number): number[] {
    let left = 0;
    let right = numbers.length - 1;

    while (left < right) {
      const sum = numbers[left] + numbers[right];
      if (sum === target) {
        return [left + 1, right + 1];
      } else if (sum < target) {
        left++;
      } else {
        right--;
      }
    }

    return [-1, -1];
  }
}

C++

#include <vector>

class Solution {
public:
  std::vector<int> twoSum(std::vector<int> &numbers, int target) {
    int left = 0;
    int right = numbers.size() - 1;

    while (left < right) {
      int sum = numbers[left] + numbers[right];
      if (sum == target) {
        return {left + 1, right + 1};
      } else if (sum < target) {
        ++left;
      } else {
        --right;
      }
    }

    return {};
  }
};

Go

func TwoSum(numbers []int, target int) []int {
    left, right := 0, len(numbers)-1

    for left < right {
        sum := numbers[left] + numbers[right]
        if sum == target {
            return []int{left + 1, right + 1}
        } else if sum < target {
            left++
        } else {
            right--
        }
    }

    return nil
}

Kotlin

class Solution {
  fun twoSum(numbers: IntArray, target: Int): IntArray {
    var left = 0
    var right = numbers.size - 1

    while (left < right) {
      val sum = numbers[left] + numbers[right]
      when {
        sum == target -> return intArrayOf(left + 1, right + 1)
        sum < target -> left++
        else -> right--
      }
    }

    return intArrayOf(-1, -1)
  }
}

Scala

class Solution {
  def twoSum(numbers: Array[Int], target: Int): Array[Int] = {
    var left = 0
    var right = numbers.length - 1

    while (left < right) {
      val sum = numbers(left) + numbers(right)
      if (sum == target) {
        return Array(left + 1, right + 1)
      } else if (sum < target) {
        left += 1
      } else {
        right -= 1
      }
    }

    Array()
  }
}

Ruby

class Solution
  def two_sum(numbers, target)
    left = 0
    right = numbers.length - 1

    while left < right
      sum = numbers[left] + numbers[right]
      if sum == target
        return [left + 1, right + 1]
      elsif sum < target
        left += 1
      else
        right -= 1
      end
    end

    [-1, -1]
  end
end

Rust

impl Solution {
    pub fn two_sum(&self, numbers: Vec<i32>, target: i32) -> Vec<i32> {
        let (mut left, mut right) = (0usize, numbers.len() - 1);

        while left < right {
            let sum = numbers[left] + numbers[right];
            if sum == target {
                return vec![(left + 1) as i32, (right + 1) as i32];
            } else if sum < target {
                left += 1;
            } else {
                right -= 1;
            }
        }

        vec![-1, -1]
    }
}

Swift

class Solution {
    func twoSum(_ numbers: [Int], _ target: Int) -> [Int] {
        var left = 0
        var right = numbers.count - 1

        while left < right {
            let sum = numbers[left] + numbers[right]
            if sum == target {
                return [left + 1, right + 1]
            } else if sum < target {
                left += 1
            } else {
                right -= 1
            }
        }

        return [-1, -1]
    }
}

C#

public class Solution {
    public int[] TwoSum(int[] numbers, int target) {
        int left = 0;
        int right = numbers.Length - 1;

        while (left < right) {
            int sum = numbers[left] + numbers[right];
            if (sum == target) {
                return new int[]{ left + 1, right + 1 };
            } else if (sum < target) {
                left++;
            } else {
                right--;
            }
        }

        return new int[]{ -1, -1 };
    }
}

Dart

class Solution {
  List<int> twoSum(List<int> numbers, int target) {
    int left = 0;
    int right = numbers.length - 1;

    while (left < right) {
      int sum = numbers[left] + numbers[right];
      if (sum == target) {
        return [left + 1, right + 1];
      } else if (sum < target) {
        left++;
      } else {
        right--;
      }
    }

    return [-1, -1];
  }
}

PHP

class Solution {
    public function twoSum(array $numbers, int $target): array {
        $left = 0;
        $right = count($numbers) - 1;

        while ($left < $right) {
            $sum = $numbers[$left] + $numbers[$right];
            if ($sum == $target) {
                return [$left + 1, $right + 1];
            } elseif ($sum < $target) {
                $left++;
            } else {
                $right--;
            }
        }

        return [-1, -1];
    }
}