Pattern: Two Pointers — Problem Statement & Solution Guide

Two PointersMediumMixed

TimeO(n)

SpaceO(1)

Problem Description

Given a strictly increasing sequence of integers and a specific target value, determine the positions of two distinct elements that sum to the target. The array is guaranteed to be sorted in ascending order, which allows for an efficient linear-time solution using the two-pointer technique. Initialize one pointer at the beginning of the array and another at the end. Calculate the sum of the elements at these two positions. If the sum equals the target, return the indices. If the sum is less than the target, increment the left pointer to increase the sum. If the sum is greater than the target, decrement the right pointer to decrease the sum. Continue this process until the pointers meet or the target is found.

The input consists of a single array of integers and an integer target. The output should be the zero-based indices of the two elements that sum to the target. If no such pair exists, return an empty array or a specific sentinel value as defined by the implementation context, though for this problem, a valid pair is guaranteed to exist in the test cases provided.

This problem requires leveraging the sorted property of the array to avoid the O(n^2) complexity of brute-force checking. By moving pointers inward based on the comparison of the current sum with the target, you can find the solution in O(n) time and O(1) space.

DSA Pattern Breakdown

"Pattern: Two Pointers"

medium

WHY DOES IT MATTER?

Two‑pointer patterns turn problems that appear quadratic into linear ones by exploiting order. They are a cornerstone for interviewers to assess a candidate's ability to recognize problem constraints and apply space‑optimal strategies.

OPTIMIZATION CHALLENGE

The key insight is that the sorted order creates a monotonic relationship between pointer movement and sum magnitude, allowing us to discard large swaths of the search space with a single comparison.

REAL-WORLD CONNECTION

Think of a warehouse aisle where items are sorted by weight; a picker starts at both ends and moves inward to find two items that together meet a shipping weight limit, minimizing the number of moves and avoiding a full inventory scan.

During an interview, write the loop invariant explicitly: "All pairs left of the left pointer and right of the right pointer have been ruled out as impossible"—this demonstrates rigorous reasoning and helps avoid off‑by‑one errors.

COMPLEXITY AT A GLANCE

⏱ Time:O(n)

💾 Space:O(1)

Core Theory — Why This Approach?

The two‑pointer technique leverages the monotonic property of a sorted array to locate a pair whose sum equals a target in linear time. By placing one pointer at the smallest element and another at the largest, we can evaluate the current sum and deterministically move the pointer that brings the sum closer to the target: if the sum is too small, increment the left pointer; if it is too large, decrement the right pointer. This deterministic movement guarantees that every element is examined at most once, yielding O(n) time.

A naive solution would examine every possible pair using two nested loops, resulting in O(n²) time, which quickly becomes infeasible for large inputs (e.g., n > 10⁵). The extra space required for hash‑based complements is O(n), but it discards the ordering information that can be exploited for a more elegant solution. The two‑pointer paradigm is optimal for this class of problems because it simultaneously achieves the best possible time complexity while using only O(1) auxiliary space.

The underlying theory is rooted in the concept of a sliding window on a sorted domain. Because the array is strictly increasing, moving the left pointer forward strictly increases the sum, and moving the right pointer backward strictly decreases it. This monotonic behavior eliminates the need for backtracking or revisiting indices, which is why the algorithm is both simple and provably optimal.

Interview Questions on This Problem

Q1How would you modify the two‑pointer solution if the array could contain duplicate values and you needed to return all unique pairs that sum to the target?

After finding a valid pair, advance the left pointer past any duplicates of its current value and similarly retreat the right pointer past duplicates of its current value. Continue the process until the pointers cross, collecting each distinct pair.

Q2Explain why a hash‑map based complement search is less optimal than the two‑pointer approach for a sorted array, even though both achieve O(n) time.

A hash‑map requires O(n) extra space and incurs constant‑time overhead for hashing and collision handling, whereas the two‑pointer method uses O(1) space and benefits from cache‑friendly sequential access, leading to lower actual runtime and memory footprint.

Q3In a distributed system where the sorted list is sharded across multiple nodes, how could you apply the two‑pointer technique to find a target sum without gathering the entire list centrally?

Each node can expose its local minimum and maximum values. A coordinator can perform a distributed two‑pointer walk by requesting elements from the leftmost and rightmost shards, moving inward based on the sum, and only pulling additional elements from a shard when its pointer advances, thus preserving linear work across the combined dataset.

Examples

Example 1

Input

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

Output

[0, 1]

Explanation: Initialize left=0, right=3. Sum = nums[0] + nums[3] = 2 + 15 = 17. Since 17 > 9, decrement right to 2. Sum = nums[0] + nums[2] = 2 + 11 = 13. Since 13 > 9, decrement right to 1. Sum = nums[0] + nums[1] = 2 + 7 = 9. Since 9 == 9, return [0, 1].

Example 2

Input

nums = [1, 3, 5, 8, 10], target = 13

Output

[1, 3]

Explanation: Initialize left=0, right=4. Sum = 1 + 10 = 11. Since 11 < 13, increment left to 1. Sum = 3 + 10 = 13. Since 13 == 13, return [1, 3].

Example 3

Input

nums = [4, 6, 9, 12, 15], target = 21

Output

[1, 3]

Explanation: Initialize left=0, right=4. Sum = 4 + 15 = 19. Since 19 < 21, increment left to 1. Sum = 6 + 15 = 21. Since 21 == 21, return [1, 3].

Example 4

Input

nums = [1, 2, 3, 4, 5], target = 7

Output

[1, 4]

Explanation: Initialize left=0, right=4. Sum = 1 + 5 = 6. Since 6 < 7, increment left to 1. Sum = 2 + 5 = 7. Since 7 == 7, return [1, 4].

Constraints

2 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9
nums is strictly increasing
There is exactly one valid pair of indices that satisfies the condition
The same element cannot be used twice

Optimal Approach & Strategy

Initialize pointers at the two ends of the sorted array and move them inward based on the current sum relative to the target, achieving linear time with constant extra space.

Brute Force Approach

Check every possible pair with two nested loops, comparing each sum to the target. This runs in quadratic time and quickly becomes too slow for large arrays.

Verified Code Solutions

Language:

JavaScript Solution

Time: O(n)

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    let left = 0;
    let right = nums.length - 1;
    while (left < right) {
        let sum = nums[left] + nums[right];
        if (sum === target) {
            return [left, right];
        } else if (sum < target) {
            left++;
        } else {
            right--;
        }
    }
    return [];
};

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

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

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        left, right = 0, len(nums) - 1
        while left < right:
            current_sum = nums[left] + nums[right]
            if current_sum == target:
                return [left, right]
            elif current_sum < target:
                left += 1
            else:
                right -= 1
        return []

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    let left = 0;
    let right = nums.length - 1;
    while (left < right) {
        let sum = nums[left] + nums[right];
        if (sum === target) {
            return [left, right];
        } else if (sum < target) {
            left++;
        } else {
            right--;
        }
    }
    return [];
};

Asked in Top Tech Interviews

uncategorizedmediumgeneric

Solve in Interative Editor

Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.

Pattern: Two Pointers Solution

Problem Statement

Input

Output

Input

Output

Input

Output

Input

Output

Constraints

More Two Pointers

Optimized Approach

Brute Force Approach

Step-by-Step Dry Run

Tested Solutions

Pattern: Two Pointers — Problem Statement & Solution Guide

Problem Description

DSA Pattern Breakdown

Core Theory — Why This Approach?

Interview Questions on This Problem

Examples

Constraints

Optimal Approach & Strategy

Brute Force Approach

Verified Code Solutions

Asked in Top Tech Interviews

Solve in Interative Editor