Solving Sorted-Array Problems with Two Pointers

Welcome back. In the previous lesson, you used sliding windows to maintain state for a contiguous range. Two pointers are related, but their purpose is broader: two indices move according to a rule that lets you discard impossible work.

Here, the critical extra property is that the input is sorted. Sorted order gives pointer movements meaning: moving left forward selects an equal-or-larger value; moving right backward selects an equal-or-smaller value. You will use that monotonic structure in two interview staples:

1. Opposing pointers for finding a pair with a target sum.
2. Same-direction pointers for compacting a sorted array in place.

The goal is not to memorize left++ and right--. It is to be able to state which candidates are eliminated, why that elimination is safe, and what invariant makes your Java implementation correct.

---

Two-pointer families: direction follows the problem

Two pointers are simply two independently moving indices. The direction and meaning of the pointers depend on the problem:

Pattern	Pointer movement	Typical purpose
Opposing pointers	One begins at each end and they converge	Pair sums, palindromes, maximizing an objective between endpoints
Same-direction read/write pointers	Both move from left to right, often at different rates	In-place filtering, deduplication, merging
Sliding window	Both generally move forward and delimit a contiguous range	Subarrays and substrings satisfying a condition

The previous lesson’s sliding windows are therefore a specialized form of same-direction pointer movement. But do not label every two-pointer problem a sliding window: a deduplication problem has no active contiguous “window”; instead, it has a processed output prefix.

The following opposing-pointer diagram captures the initial geometry: the left pointer starts at the smallest candidate and the right pointer starts at the largest.

---

Opposing pointers: Two Sum in a sorted array

Consider the prompt:

Given a nondecreasing integer array nums and an integer target, return the indices of two distinct elements whose sum equals target, or report that no such pair exists.

For example:

nums   = [-4, -1, 0, 3, 5, 9]
target = 4

A brute-force approach tests every pair. That takes:

$$O(n^2)$$

Because the array is sorted, we can start with the widest and most extreme candidate pair:

left  = 0, value -4
right = 5, value  9
sum   = 5

The sum is too large. Which pointer should move?

Move right leftward. Since nums[right] is currently the largest available value, replacing it with a value to its left can only decrease or preserve the sum. Moving left would increase or preserve the sum, which cannot help.

The trace is:

left value	right value	Sum	Decision
-4	9	5	Too large, decrement right
-4	5	1	Too small, increment left
-1	5	4	Found the pair

The elimination argument

This is the part interviewers care about. It turns the technique from a pattern into a justified algorithm.

Suppose the current pair is nums[left] and nums[right].

When the sum is too small

If:

$$nums[left]+nums[right]<target$$

then left cannot be part of any valid pair in the remaining search range.

Why? Every element between left and right is no larger than nums[right]. Therefore, for every valid candidate index $k\le right$:

$$nums[left]+nums[k]\le nums[left]+nums[right]<target$$

No pair containing the current left value can reach the target. Incrementing left safely discards it.

When the sum is too large

If:

$$nums[left]+nums[right]>target$$

then right cannot be part of any valid pair in the remaining search range.

Every element between left and right is at least nums[left]. Thus, for every candidate index $k\ge left$:

$$nums[k]+nums[right]\ge nums[left]+nums[right]>target$$

No pair containing the current right value can work. Decrementing right safely discards it.

That safe elimination is why sortedness matters. Without sortedness, pointer movement gives you no reliable information about whether discarded pairs might work.

Java implementation

This version returns zero-based indices. It uses long for the addition so that two large int values cannot overflow before comparison.

import java.util.Objects;

public static int[] twoSumSorted(int[] nums, int target) {
    Objects.requireNonNull(nums, "nums must not be null");

    int left = 0;
    int right = nums.length - 1;

    while (left < right) {
        long sum = (long) nums[left] + nums[right];

        if (sum == target) {
            return new int[] {left, right};
        }

        if (sum < target) {
            left++;
        } else {
            right--;
        }
    }

    // Explicit contract: no matching pair exists.
    return new int[0];
}

The loop condition must be:

left < right

This prevents using the same element twice. For instance, with nums = [4] and target = 8, returning index 0 twice would violate the “two distinct elements” requirement.

Correctness invariant

A concise invariant is:

At the start of each iteration, if a valid pair exists, at least one valid pair remains within the inclusive index range [left, right].

Each pointer move removes only values proven incapable of participating in a valid pair. When left >= right, there are fewer than two candidate positions left, so no valid distinct-index pair remains.

Complexity

Each iteration moves exactly one pointer inward. Neither pointer ever reverses direction.

• Time: $O(n)$
• Auxiliary space: $O(1)$

The difference from a hash-based Two Sum solution is worth stating explicitly in interviews:

• If the input is already sorted and you only need a pair, opposing pointers are usually the best fit.
• If the input is unsorted and you must preserve original indices, the hash-map strategy from the earlier lesson is usually preferable.
• Sorting an unsorted array costs $O(n\log n)$, and you must retain original-index information if the prompt asks for it.

---

Same-direction pointers: remove duplicates in place

Now consider a different sorted-array contract:

Given a sorted array, remove duplicates in place so that each distinct value appears once in the prefix of the original array. Return the number of distinct values.

For:

nums = [2, 3, 3, 3, 6, 9, 9]

the desired result is:

return value: 4
meaningful prefix: [2, 3, 6, 9]

The array after index 3 is irrelevant. Do not spend time shifting or deleting those trailing values; Java arrays have fixed length, and the interview contract only guarantees the returned prefix.

The pointers have different roles:

• read examines every input value.
• write marks the next free position in the compacted result prefix.

The key sorted-array observation is simple: all duplicates occur consecutively. Once you have kept a value, every equal value immediately following it can be skipped.

A robust Java implementation

import java.util.Objects;

public static int removeDuplicatesSorted(int[] nums) {
    Objects.requireNonNull(nums, "nums must not be null");

    int write = 0;

    for (int read = 0; read < nums.length; read++) {
        boolean firstValue = write == 0;
        boolean newDistinctValue = !firstValue && nums[read] != nums[write - 1];

        if (firstValue || newDistinctValue) {
            nums[write] = nums[read];
            write++;
        }
    }

    return write;
}

The method works for an empty array without a special branch:

int[] nums = {};
int distinctCount = removeDuplicatesSorted(nums); // 0

For a non-empty array such as:

[0, 0, 1, 1, 1, 2, 2, 3, 3, 4]

the final state is conceptually:

[0, 1, 2, 3, 4, _, _, _, _, _]

Only the returned prefix length, 5, defines the result. The underscores represent values that the caller must ignore.

Why compare with nums[write - 1]?

Before each read iteration, maintain this invariant:

nums[0..write - 1] contains exactly the distinct values found among the elements examined so far, in sorted order.

So nums[write - 1] is the last distinct value retained.

When nums[read] differs from it, the current value is the first instance of a new value. It belongs in the next result position, nums[write].

When the values are equal, the current element is a duplicate and read advances without moving write.

Because write never exceeds read, writing to nums[write] cannot overwrite an unexamined future element. At worst, it overwrites the current position with its own value.

Trace a representative case

Use:

nums = [1, 1, 2, 2, 3]

read	Current value	Unique prefix before decision	Action	write after action
0	1	empty	Keep first value	1
1	1	[1]	Skip duplicate	1
2	2	[1]	Write 2 at index 1	2
3	2	[1, 2]	Skip duplicate	2
4	3	[1, 2]	Write 3 at index 2	3

The meaningful final prefix is [1, 2, 3].

Complexity

The read pointer visits each array position once. write moves at most once for each distinct element.

• Time: $O(n)$
• Auxiliary space: $O(1)$

The in-place constraint is important. Building a HashSet would detect uniqueness but would use additional space and, unless handled carefully, would not preserve the sorted order or satisfy the required output contract.

---

Choosing the correct two-pointer pattern

Before coding, classify the prompt by asking what each pointer represents.

Prompt clue	Likely pattern	Pointer meaning
“Sorted array,” “find two values,” “target sum”	Opposing pointers	Two candidate values whose combined property is evaluated
“Palindrome,” “compare beginning and end”	Opposing pointers	Symmetric positions moving toward the center
“Remove duplicates in place”	Same-direction read/write	Scanner plus boundary of retained output
“Filter values in place”	Same-direction read/write	Scanner plus next output position
“Longest/shortest contiguous subarray”	Sliding window	Boundaries of an active contiguous range

A useful interview habit is to state the property that justifies movement:

• Target sum in sorted array: ordering allows you to eliminate an endpoint after comparing the sum to the target.
• In-place deduplication in sorted array: ordering places duplicates next to each other, so comparison with the last kept value is sufficient.

If you cannot state a safe-elimination argument or a maintained invariant, pause before applying two pointers. That pause prevents many incorrect “pattern-matching” solutions.

Edge cases to mention aloud

For opposing-pointer target sum:

• Empty or single-element array.
• No valid pair.
• Duplicate values, including a valid pair such as [2, 2] with target 4.
• Integer overflow during addition.
• The distinct-indices constraint.

For in-place deduplication:

• Empty array.
• One element.
• All values identical.
• No duplicates.
• Negative values, which require no special handling because the comparison is equality-based.
• Only the prefix of returned length is part of the result.

---

Interview-ready explanation

For sorted Two Sum, a concise explanation is:

“I will use opposing pointers because the array is sorted. I start with the smallest and largest values. If their sum is too small, the left value cannot form the target with any remaining value, so I move left forward. If the sum is too large, the right value cannot form the target with any remaining value, so I move right backward. Each pointer moves at most n times, giving $O(n)$ time and $O(1)$ extra space.”

For sorted-array deduplication, say:

“I use a read pointer to scan every value and a write pointer to maintain a compacted prefix of unique values. Because duplicates are adjacent in sorted input, a value is new exactly when it differs from the last value retained. The prefix through write - 1 is always the ordered set of unique values seen so far. This is one pass, $O(n)$ time, with $O(1)$ auxiliary space.”

---

Key takeaways

• Sorted order provides the monotonic structure that makes two-pointer decisions safe.
• With opposing pointers, a sum that is too small eliminates the current left value; a sum that is too large eliminates the current right value.
• With same-direction read/write pointers, one pointer scans input while the other maintains a valid output prefix.
• For in-place array problems, the returned length often defines the meaningful prefix; trailing array values need not be modified.
• Both patterns run in $O(n)$ time and $O(1)$ auxiliary space when each pointer moves only forward through its allowed range.
• In an interview, explain the elimination argument or invariant before discussing complexity.

Next, you will use prefix sums to answer repeated range queries and count subarrays meeting a target condition, including cases where a simple variable-size sum window is not valid.