Two Pointers

Opening scenario

Problem references use LC for LeetCode.

Two Sum on a sorted array (a sorted-input variation of LC 1, using the idea from LC 167). You are given an array of integers nums sorted in non-decreasing order and a target. Return zero-based indices of two distinct elements whose values add up to target, or [] if no pair exists. Any matching pair is acceptable; LC 167 itself uses one-based indices. Then a follow-up you should expect: 3Sum (LC 15) — given an unsorted array nums, return all unique triplets a + b + c == 0.

For 3Sum, each triplet uses three distinct indices, and duplicate value triplets should appear only once. Start by asking what sorted order lets you rule out after comparing a pair’s sum with the target.

Question progression

Q1 — What does the brute force look like, and what is it costing you?

Question: Without any cleverness, how do you find the pair summing to target, and what is that complexity?