Basics
The idea behind the pattern, why it is correct, and the clues in a question that point to it.
1.1Core idea
What the pattern does, in plain words.
Put one pointer at each end. Compare, then move the pointer that can only improve the answer. Each step discards a whole row of possibilities, so you visit each element once.
In a sorted array, the pair at lo and hi bounds every pair still possible. If their sum is too small, no pair using nums[lo] with anything at or left of hi can reach the target, so lo can move right; if it is too large, hi moves left. Each step rules out a whole row of pairs, so one pass is enough.
Typical cost: O(n) time after sorting, O(1) extra space
1.2Recognition signals
If a question has one of these clues, try this pattern first.
Question
A classic interview problem from this family. Read it carefully and plan the approach before writing any code.
2.13Sum
The problem statement, then the plan you would say out loud.
Return all unique triplets in nums that sum to zero.
Plan before you code
- Sort the array.
- Fix one number, then run two pointers on the rest for the negated value.
- Skip duplicates at every level so triplets stay unique.
Detailed answer
First the reusable template, then the worked solution built from it and a walk through it one step at a time.
3.1Template
Memorise this shape. Most problems in this family are this code plus one twist.
Pair with target sum (sorted)
1function pairSum(nums: number[], target: number): [number, number] | null {2 let lo = 0, hi = nums.length - 1;3 while (lo < hi) {4 const s = nums[lo] + nums[hi];5 if (s === target) return [lo, hi];6 if (s < target) lo++; // need a bigger sum7 else hi--; // need a smaller sum8 }9 return null;10}1fun pairSum(nums: IntArray, target: Int): Pair<Int, Int>? {2 var lo = 03 var hi = nums.size - 14 while (lo < hi) {5 val s = nums[lo] + nums[hi]6 when {7 s == target -> return lo to hi8 s < target -> lo++ // need a bigger sum9 else -> hi-- // need a smaller sum10 }11 }12 return null13}1static int[] pairSum(int[] nums, int target) {2 int lo = 0, hi = nums.length - 1;3 while (lo < hi) {4 int s = nums[lo] + nums[hi];5 if (s == target) return new int[] {lo, hi};6 if (s < target) lo++; // need a bigger sum7 else hi--; // need a smaller sum8 }9 return null;10}- Start at both ends of the sorted array.
- Compare the current pair with the target.
- Move the pointer that can only improve the sum.
3.2Solution
Strict TypeScript, type-checked and tested.
3Sum
1function threeSum(nums: number[]): number[][] {2 nums.sort((a, b) => a - b);3 const out: number[][] = [];4 for (let i = 0; i < nums.length - 2; i++) {5 if (i > 0 && nums[i] === nums[i - 1]) continue; // skip duplicate anchors6 let lo = i + 1, hi = nums.length - 1;7 while (lo < hi) {8 const s = nums[i] + nums[lo] + nums[hi];9 if (s < 0) lo++;10 else if (s > 0) hi--;11 else {12 out.push([nums[i], nums[lo], nums[hi]]);13 lo++;14 while (lo < hi && nums[lo] === nums[lo - 1]) lo++; // skip duplicate seconds15 }16 }17 }18 return out;19}1fun threeSum(nums: IntArray): List<List<Int>> {2 nums.sort()3 val out = mutableListOf<List<Int>>()4 for (i in 0 until nums.size - 2) {5 if (i > 0 && nums[i] == nums[i - 1]) continue // skip duplicate anchors6 var lo = i + 17 var hi = nums.size - 18 while (lo < hi) {9 val s = nums[i] + nums[lo] + nums[hi]10 when {11 s < 0 -> lo++12 s > 0 -> hi--13 else -> {14 out.add(listOf(nums[i], nums[lo], nums[hi]))15 lo++16 while (lo < hi && nums[lo] == nums[lo - 1]) lo++ // skip duplicate seconds17 }18 }19 }20 }21 return out22}1static List<List<Integer>> threeSum(int[] nums) {2 Arrays.sort(nums);3 List<List<Integer>> out = new ArrayList<>();4 for (int i = 0; i < nums.length - 2; i++) {5 if (i > 0 && nums[i] == nums[i - 1]) continue; // skip duplicate anchors6 int lo = i + 1, hi = nums.length - 1;7 while (lo < hi) {8 int s = nums[i] + nums[lo] + nums[hi];9 if (s < 0) lo++;10 else if (s > 0) hi--;11 else {12 out.add(List.of(nums[i], nums[lo], nums[hi]));13 lo++;14 while (lo < hi && nums[lo] == nums[lo - 1]) lo++; // skip duplicate seconds15 }16 }17 }18 return out;19}Step by step
- Sort numerically first (the default sort compares strings), so two pointers can steer the sum.
- Fix each anchor once and skip duplicate anchors.
- Two pointers on the rest: move towards a zero sum.
- Record the triplet, then skip duplicate seconds.
Complexity: O(n²) time, O(1) extra space beyond the output
Q&A
What interviewers ask once your code works, and problems to try on your own.
4.1Interview questions
Answer out loud, then open.
Why must the array be sorted?
Two pointers or a hash map for Two Sum?
How do you avoid duplicate triplets in 3Sum?
4.2Solo practice
Try these without looking; open the hint only when stuck.
Hint
Skip non-alphanumerics from both ends.
Extra depth
More fully worked problems in the same family, and the mistakes that cost offers.
5.12 more worked problems
Each one: the problem, the plan, the code and its cost.
Show detailsHide details
Container With Most Water
Pick two lines that, with the x-axis, hold the most water.
- Start with the widest container.
- The shorter wall limits the area, so moving the taller wall can never help.
- Always move the shorter wall inwards.
1function maxArea(height: number[]): number {2 let lo = 0, hi = height.length - 1, best = 0;3 while (lo < hi) {4 const h = Math.min(height[lo], height[hi]);5 best = Math.max(best, h * (hi - lo));6 if (height[lo] < height[hi]) lo++;7 else hi--;8 }9 return best;10}Complexity: O(n) time, O(1) space
Trapping Rain Water
Given bar heights, how much rain water is trapped between them?
- Water above a bar = min(max left, max right) − height.
- Walk inwards from both ends.
- The side with the lower wall is already bounded, so settle it and move on.
1function trap(height: number[]): number {2 let lo = 0, hi = height.length - 1;3 let leftMax = 0, rightMax = 0, water = 0;4 while (lo < hi) {5 if (height[lo] < height[hi]) {6 leftMax = Math.max(leftMax, height[lo]);7 water += leftMax - height[lo];8 lo++;9 } else {10 rightMax = Math.max(rightMax, height[hi]);11 water += rightMax - height[hi];12 hi--;13 }14 }15 return water;16}Complexity: O(n) time, O(1) space
5.2Traps
Bugs and misreadings that come up again and again with this pattern.
Show detailsHide details
- Forgetting to sort first
- Infinite loop when neither pointer moves
- Duplicate answers without skip logic