Lesson 6.3 · Two Pointers

Sort First, and Skip Duplicates

When order doesn't matter, sorting (O(n log n)) unlocks two pointers; skipping equal neighbours avoids duplicate answers.

12 min

Think of it like this

Lining a class up by height before picking dance partners: once sorted, finding pairs with a target total height is quick, and two students of identical height are easy to spot standing next to each other.

1.When sorting is allowed

If the problem wants values (not original indexes), sort first. The O(n log n) sort is usually cheaper than the O(n²) search it replaces.

For triples (3Sum), fix the first element with a loop and run two pointers on the rest: O(n²) instead of O(n³).

2.Skipping duplicates

Sorted arrays put equal values together. To avoid reporting the same triple twice, skip a fixed element equal to the previous one, and after finding a match, move each pointer past all copies of its value.

SkipDuplicates.java

import java.util.*;

public class Main {
    // all unique pairs that sum to target
    static List<int[]> pairs(int[] a, int target) {
        Arrays.sort(a);
        List<int[]> out = new ArrayList<>();
        int L = 0, R = a.length - 1;
        while (L < R) {
            int s = a[L] + a[R];
            if (s < target) L++;
            else if (s > target) R--;
            else {
                out.add(new int[]{a[L], a[R]});
                while (L < R && a[L] == a[L + 1]) L++;   // skip copies of a[L]
                while (L < R && a[R] == a[R - 1]) R--;   // skip copies of a[R]
                L++;
                R--;
            }
        }
        return out;
    }
    public static void main(String[] args) {
        for (int[] p : pairs(new int[]{2, 2, 3, 3, 4, 4, 1, 5}, 6)) System.out.println(Arrays.toString(p));
    }
}

Output

[1, 5]
[2, 4]
[3, 3]

Remember

Sort when the answer is values, not indexes.
Fix one element and two-pointer the rest for triples.
Skip equal neighbours to avoid duplicate answers.

Common mistakes

Sorting when the problem needs original indexes.
Skipping duplicates before recording the first match.

Command Palette

Sort First, and Skip Duplicates

1.When sorting is allowed

2.Skipping duplicates