Every question from the "Two pointers" block of your DSA Pattern Sheet (#34 to #44). Each one goes brute force → better → best, with the code, time and space, the Java you pick up along the way, and the cost of every collection or API call used. After the main approaches, an Other approaches block adds techniques from other topics, because those questions won't come back. Where only two real approaches exist, the note says so.
int left = 0, right = n - 1;
while (left < right) {
int sum = a[left] + a[right];
if (sum == target) return ...;
if (sum < target) left++; // need bigger
else right--; // need smaller
}Used by: Valid Palindrome, Two Sum II, Container With Most Water, Trapping Rain Water, Squares of a Sorted Array. Works when moving one pointer rules out a value for good (usually because the data is sorted, or one side decides the limit).
int write = 0;
for (int read = 0; read < n; read++) {
if (keep(a[read])) {
a[write] = a[read];
write++;
}
}
return write; // new lengthUsed by: Move Zeroes, Remove Duplicates, Remove Element. read looks at everything, write marks the end of the kept part. For "at most k copies" compare with a[write - k].
Arrays.sort(a);
for (int i = 0; i < n - 2; i++) {
if (i > 0 && a[i] == a[i - 1]) continue; // skip duplicate anchor
int left = i + 1, right = n - 1;
while (left < right) {
int sum = a[i] + a[left] + a[right];
if (sum < target) left++;
else if (sum > target) right--;
else {
// record the triplet
left++; right--;
while (left < right && a[left] == a[left - 1]) left++;
while (left < right && a[right] == a[right + 1]) right--;
}
}
}Used by: 3Sum, 3Sum Closest, 4Sum (one more outer loop). Each extra number adds one nested loop. Use long for the sum when values are large.
| Sorted + pair or triple with a target | Template 1 or 3 |
| Edit the array in place, keep some elements | Template 2 |
| Palindrome or symmetric check | Template 1 |
| Answer depends on the smaller of two sides | Template 1, move the smaller side |
| Unsorted, only need a pair | HashMap instead (O(n) space) |
| Each pointer moves one way only | O(n) total |
| Sort first (then two pointers) | O(n log n) |
| 3Sum / 3Sum Closest | O(n²) |
| 4Sum | O(n³) |
| k-Sum | O(n^(k-1)) |
a[i], s.charAt(i), s.length() | O(1) |
Arrays.sort(int[]) | O(n log n) |
clone(), new int[n] | O(n) |
HashSet / HashMap add, get, contains | O(1) avg |
StringBuilder.append, deleteCharAt(last) | O(1) |
StringBuilder.reverse(), substring | O(n) |
ArrayDeque push, pop, peek | O(1) |
Character.isLetterOrDigit, toLowerCase | O(1) |
| Duplicates: skip duplicate anchors BEFORE using them, skip duplicate pointer values AFTER a match. | |
Overflow: (long) a + b + c + d for 4Sum. Cast the first operand. | |
Crossing pointers: repeat left < right inside inner skip loops. | |
Lists as keys: List<Integer> works in a HashSet; int[] does not. |
All snippets assume import java.util.*; and are static methods, so you can paste them into a class and call them from main.
Spot it: 'Reads the same forwards and backwards', ignoring punctuation and case. One pointer at each end, compare, move inwards.
Build a new string with only letters and digits, all lowercase. Reverse a copy and check the two are equal.
static boolean isPalindromeBrute(String s) {
StringBuilder cleaned = new StringBuilder();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (Character.isLetterOrDigit(c)) {
cleaned.append(Character.toLowerCase(c));
}
}
String forward = cleaned.toString();
String backward = cleaned.reverse().toString(); // reverse() changes the builder itself
return forward.equals(backward);
}Still builds the cleaned string, but compares with two pointers instead of reversing a whole copy. It stops at the first mismatch and only needs the one cleaned string.
static boolean isPalindromeBetter(String s) {
StringBuilder cleaned = new StringBuilder();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (Character.isLetterOrDigit(c)) {
cleaned.append(Character.toLowerCase(c));
}
}
int left = 0, right = cleaned.length() - 1;
while (left < right) {
if (cleaned.charAt(left) != cleaned.charAt(right)) return false;
left++;
right--;
}
return true;
}Don't build anything. Left pointer from the start, right pointer from the end. Skip anything that isn't a letter or digit on each side, then compare the two characters in lowercase. Mismatch: not a palindrome. Otherwise move both inwards.
static boolean isPalindromeBest(String s) {
int left = 0, right = s.length() - 1;
while (left < right) {
while (left < right && !Character.isLetterOrDigit(s.charAt(left))) left++;
while (left < right && !Character.isLetterOrDigit(s.charAt(right))) right--;
if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) {
return false;
}
left++;
right--;
}
return true;
}replaceAll("[^A-Za-z0-9]", "") deletes every character that is NOT a letter or digit, toLowerCase() handles case, and a reversed copy gives the comparison. Short, but it creates several temporary strings.
When it fits: Fine for quick code. Interviewers usually want the O(1) two-pointer version.
static boolean isPalindromeRegex(String s) {
String cleaned = s.replaceAll("[^A-Za-z0-9]", "").toLowerCase();
String reversed = new StringBuilder(cleaned).reverse().toString();
return cleaned.equals(reversed);
}Same logic with the loop replaced by a method calling itself on a smaller range: skip a junk character on either side, compare the two ends, then recurse on (left + 1, right - 1).
When it fits: Shows how a two-pointer loop maps to recursion. Costs O(n) stack space, so the loop is better.
static boolean isPalindromeRecursive(String s) {
return checkPal(s, 0, s.length() - 1);
}
private static boolean checkPal(String s, int left, int right) {
if (left >= right) return true;
if (!Character.isLetterOrDigit(s.charAt(left))) return checkPal(s, left + 1, right);
if (!Character.isLetterOrDigit(s.charAt(right))) return checkPal(s, left, right - 1);
if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) return false;
return checkPal(s, left + 1, right - 1);
}Character.isLetterOrDigit(c)isLetter, isDigit, isUpperCase, isWhitespace. All O(1).Character.toLowerCase(c)char. Use it before comparing so A and a match. String.toLowerCase() is the version for whole strings.StringBuilder.reverse() changes the buildertoString() before it (as above) you keep the original; after it, the original is gone.left < right inside the inner loops tooleft past right, and charAt would throw..equals() for strings==: it compares references, not contents.| String.charAt(i) / length() | O(1) |
| StringBuilder.append | O(1) amortised |
| StringBuilder.reverse / toString | O(n) |
| Character.isLetterOrDigit / toLowerCase | O(1) |
| String.equals | O(n) |
Remember: Two pointers from the ends: skip the junk, compare the rest, move inwards. The loop condition left < right is what makes it stop in the middle.
Spot it: 'Do it in place' and 'keep the order of the other elements'. One pointer READS every element. A second pointer, write, marks where the next non-zero belongs.
This is the read/write (slow and fast) pointer pattern. Zeroes naturally end up at the back.
Copy the non-zero numbers in order into a fresh array (which starts full of zeros), then copy that array back.
static void moveZeroesBrute(int[] nums) {
int[] result = new int[nums.length]; // starts filled with 0
int idx = 0;
for (int x : nums) {
if (x != 0) {
result[idx] = x;
idx++;
}
}
for (int i = 0; i < nums.length; i++) {
nums[i] = result[i];
}
}read walks the whole array. Each non-zero is copied to nums[write] and write moves on. When the walk ends, every slot from write to the end must be a zero, so fill them. In place, but two passes.
static void moveZeroesBetter(int[] nums) {
int write = 0;
for (int read = 0; read < nums.length; read++) {
if (nums[read] != 0) {
nums[write] = nums[read];
write++;
}
}
while (write < nums.length) {
nums[write] = 0;
write++;
}
}Same two pointers, but instead of copying and then filling, swap nums[read] with nums[write] whenever nums[read] is non-zero. The zero that was at write goes to read, so the zeroes get pushed back as you go. Everything done in one loop. The read != write check just skips pointless self-swaps.
static void moveZeroesBest(int[] nums) {
int write = 0; // where the next non-zero goes
for (int read = 0; read < nums.length; read++) {
if (nums[read] != 0) {
if (read != write) {
int temp = nums[write];
nums[write] = nums[read];
nums[read] = temp;
}
write++;
}
}
}Nothing else to add. The write-pointer idea is the whole question. (Sorting with a custom comparator would also work but costs O(n log n) and breaks the 'keep the order' rule.)
int temp = a; a = b; b = temp;. Java has no tuple swap. If you copy first without saving, you lose a value.for (int x : nums) is read-onlyx inside the loop doesn't change the array. When you need to write back, use the index loop.int[n] starts with zerosvoid method that changes nums[i] changes the caller's array. No need to return anything.| Array read / write | O(1) |
| new int[n] | O(n) |
Remember: The read/write pointer pair is the in-place filter. Remove Duplicates, Remove Element and Sort Colors are all the same idea.
Spot it: Sorted, so duplicates are neighbours. Modify in place and return how many unique values there are. Read/write pointers again: read scans, write marks the end of the unique part.
Walk the array. Whenever nums[i] equals the previous one, delete it by shifting every later element one step left and shrinking the logical length. Every duplicate costs a full shift.
static int removeDuplicatesBrute(int[] nums) {
int n = nums.length;
int i = 1;
while (i < n) {
if (nums[i] == nums[i - 1]) {
for (int j = i; j < n - 1; j++) {
nums[j] = nums[j + 1]; // shift left over the duplicate
}
n--; // one fewer element
} else {
i++;
}
}
return n;
}Copy each value into a second array only if it differs from the previous value. Then copy the uniques back to the front. Linear time, but uses O(n) extra memory.
static int removeDuplicatesBetter(int[] nums) {
if (nums.length == 0) return 0;
int[] temp = new int[nums.length];
int k = 0;
for (int i = 0; i < nums.length; i++) {
if (i == 0 || nums[i] != nums[i - 1]) {
temp[k] = nums[i];
k++;
}
}
for (int i = 0; i < k; i++) {
nums[i] = temp[i];
}
return k;
}write is the next free slot in the unique part; the last unique value sits at write - 1. read scans forward. When nums[read] differs from nums[write - 1], it is a new value: copy it to nums[write] and advance write. When it's the same, skip it. Return write.
static int removeDuplicatesBest(int[] nums) {
if (nums.length == 0) return 0;
int write = 1; // nums[0] is always unique
for (int read = 1; read < nums.length; read++) {
if (nums[read] != nums[write - 1]) {
nums[write] = nums[read];
write++;
}
}
return write;
}The follow-up (Remove Duplicates II keeps at most 2). Compare nums[read] with nums[write - k] instead of nums[write - 1]: if they're equal, there are already k copies kept. The first k elements are always kept.
When it fits: With k = 1 it's exactly the best solution. Learn it as one template.
static int removeDuplicatesAtMostK(int[] nums, int k) {
if (nums.length <= k) return nums.length;
int write = k; // the first k elements are always kept
for (int read = k; read < nums.length; read++) {
if (nums[read] != nums[write - k]) {
nums[write] = nums[read];
write++;
}
}
return write;
}nums[0..k-1] matters. What's after index k is ignored by the judge, so don't bother clearing it.nums[write - 1], not nums[read - 1]write - 1 is the pattern that generalises to the 'keep at most k copies' version below.nums[0] throws on new int[0]. Constraints often say at least 1 element, but check.i don't increase i: the element that just moved into position i still needs to be compared.| Array read / write | O(1) |
| new int[n] | O(n) |
Remember: write - 1 is 'the last thing I kept'. Compare against it and you can keep any rule (unique, at most k copies, non-zero) in the same loop.
Spot it: The input is sorted but includes negatives, so squaring breaks the order: the biggest squares are at BOTH ends. Compare the two ends, and put the larger square at the back of the result.
Square everything and sort. Correct, but throws away the fact that the input was already sorted.
static int[] sortedSquaresBrute(int[] nums) {
int[] result = new int[nums.length];
for (int i = 0; i < nums.length; i++) {
result[i] = nums[i] * nums[i];
}
Arrays.sort(result);
return result;
}Find where the numbers become non-negative. Going right from there the squares increase; going left from there the squares also increase (the negatives, mirrored). That's two sorted lists of squares, so merge them with two pointers moving outwards from the split.
static int[] sortedSquaresBetter(int[] nums) {
int n = nums.length;
int right = 0;
while (right < n && nums[right] < 0) right++; // first non-negative index
int left = right - 1; // last negative index
int[] result = new int[n];
int idx = 0;
while (left >= 0 && right < n) {
int leftSquare = nums[left] * nums[left];
int rightSquare = nums[right] * nums[right];
if (leftSquare < rightSquare) {
result[idx] = leftSquare;
left--;
} else {
result[idx] = rightSquare;
right++;
}
idx++;
}
while (left >= 0) {
result[idx] = nums[left] * nums[left];
left--;
idx++;
}
while (right < n) {
result[idx] = nums[right] * nums[right];
right++;
idx++;
}
return result;
}The biggest square is always at the left end or the right end. Compare the two, put the larger one at the LAST free spot of the result, and move that pointer inwards. Repeat while filling the result from the back to the front. No split point, no leftover loops.
static int[] sortedSquaresBest(int[] nums) {
int n = nums.length;
int[] result = new int[n];
int left = 0, right = n - 1;
for (int pos = n - 1; pos >= 0; pos--) {
int leftSquare = nums[left] * nums[left];
int rightSquare = nums[right] * nums[right];
if (leftSquare > rightSquare) {
result[pos] = leftSquare;
left++;
} else {
result[pos] = rightSquare;
right--;
}
}
return result;
}Nothing else to add. The ends-inwards version is the intended answer. (A heap or counting sort would be slower or only work for bounded values.)
for with a decreasing counterfor (int pos = n - 1; pos >= 0; pos--) fills from the back. Same loop shape for any 'process in reverse'.nums[i] * nums[i] is an int. With values up to 10^4 that's 10^8, fine. For values near 10^5 or more, use long.Arrays.sort(int[]) on the result| Arrays.sort(int[]) | O(n log n) |
| new int[n] | O(n) |
| Array read / write | O(1) |
Remember: Two pointers from both ends + fill from the back: whenever the extreme values are at the ends (squares, absolute values, 'largest first').
Spot it: '#' means backspace, and you compare the two final strings. Going from the END helps: a # tells you how many characters to skip before you reach the real ones, so you can compare without building anything.
x# until none is leftTime O(n²)Space O(n)Find the first #. If it has a character before it, remove both. If it's at the start, just remove the # (backspace on empty does nothing). Repeat until there are no # left. Each removal copies the whole string.
private static String applyBackspacesSlow(String s) {
String cur = s;
while (cur.contains("#")) {
int idx = cur.indexOf('#');
if (idx == 0) {
cur = cur.substring(1); // nothing to delete
} else {
cur = cur.substring(0, idx - 1) + cur.substring(idx + 1); // drop the char and the '#'
}
}
return cur;
}
static boolean backspaceCompareBrute(String s, String t) {
return applyBackspacesSlow(s).equals(applyBackspacesSlow(t));
}Walk the string. A normal character is appended to a StringBuilder. A # removes the last appended character (if there is one). At the end the builder holds the final text. Do it for both strings and compare.
private static String buildFinal(String s) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c == '#') {
if (sb.length() > 0) sb.deleteCharAt(sb.length() - 1); // backspace
} else {
sb.append(c);
}
}
return sb.toString();
}
static boolean backspaceCompareBetter(String s, String t) {
return buildFinal(s).equals(buildFinal(t));
}Start one pointer at the end of each string. For each pointer, move back to the next character that SURVIVES: count # as skips, and each skip cancels the next normal character. Then compare the two surviving characters. Both pointers run out together means equal. No new strings, O(1) space.
private static int nextValidIndex(String str, int index) {
int skip = 0;
while (index >= 0) {
if (str.charAt(index) == '#') {
skip++; // a backspace: it will cancel one character
index--;
} else if (skip > 0) {
skip--; // this character was erased
index--;
} else {
break; // a real surviving character
}
}
return index; // -1 if nothing is left
}
static boolean backspaceCompareBest(String s, String t) {
int i = s.length() - 1, j = t.length() - 1;
while (i >= 0 || j >= 0) {
i = nextValidIndex(s, i);
j = nextValidIndex(t, j);
if (i < 0 && j < 0) return true; // both finished together
if (i < 0 || j < 0) return false; // one has characters left
if (s.charAt(i) != t.charAt(j)) return false;
i--;
j--;
}
return true;
}Push each normal character onto a stack. On #, pop one if the stack isn't empty. At the end the stack holds the final text. Same complexity as the StringBuilder version, and it is the answer people expect for 'undo' style problems (it's the pattern behind valid parentheses, remove adjacent duplicates and decode string).
When it fits: Use when the question says 'undo' or 'cancel the previous'. ArrayDeque is the right stack in Java (not Stack).
private static String buildWithStack(String s) {
ArrayDeque<Character> stack = new ArrayDeque<>();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c == '#') {
if (!stack.isEmpty()) stack.pop(); // backspace
} else {
stack.push(c);
}
}
StringBuilder sb = new StringBuilder();
for (char c : stack) sb.append(c); // top first; both strings use the same order
return sb.toString();
}
static boolean backspaceCompareStack(String s, String t) {
return buildWithStack(s).equals(buildWithStack(t));
}sb.deleteCharAt(sb.length() - 1)deleteCharAt(i) anywhere else shifts everything after it, so O(n).String.substring(a, b)a up to but NOT including b. O(length). That copying is why the brute force is O(n²).str.contains("#") and indexOf('#')indexOf with a char and with a String both exist.# you've already seen tells you the future for free.i < 0 && j < 0 before i < 0 || j < 0| StringBuilder.append / deleteCharAt(last) | O(1) |
| String.substring / concat | O(n) |
| String.indexOf / contains | O(n) |
| String.charAt | O(1) |
| String.equals | O(n) |
Remember: Scanning from the back turns 'what survives?' into a local decision. The same trick solves 'remove adjacent duplicates' style problems without a stack.
Spot it: Sorted array, find a pair adding to the target, in O(1) extra space. Left pointer at the smallest, right at the largest. Sum too small: move left up. Sum too big: move right down.
Indices in the answer are 1-based, so return i + 1 and j + 1.
Check every pair.
static int[] twoSumSortedBrute(int[] numbers, int target) {
for (int i = 0; i < numbers.length; i++) {
for (int j = i + 1; j < numbers.length; j++) {
if (numbers[i] + numbers[j] == target) return new int[]{i + 1, j + 1};
}
}
return new int[]{};
}For each number, the partner must be target - numbers[i]. Because the array is sorted, binary search for it in the part to the right. Uses the sorted order but still does n separate searches.
static int[] twoSumSortedBetter(int[] numbers, int target) {
for (int i = 0; i < numbers.length; i++) {
int need = target - numbers[i];
int low = i + 1, high = numbers.length - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (numbers[mid] == need) return new int[]{i + 1, mid + 1};
if (numbers[mid] < need) low = mid + 1;
else high = mid - 1;
}
}
return new int[]{};
}Look at numbers[left] + numbers[right]. Too small? The only way to make it bigger is to move left up. Too big? The only way to shrink it is to move right down. Each step permanently rules out one number, so you never need to go back.
static int[] twoSumSortedBest(int[] numbers, int target) {
int left = 0, right = numbers.length - 1;
while (left < right) {
int sum = numbers[left] + numbers[right];
if (sum == target) return new int[]{left + 1, right + 1};
if (sum < target) left++;
else right--;
}
return new int[]{};
}The same one-pass 'have I seen the partner?' map as Two Sum. It works on any array, sorted or not, but it uses O(n) extra memory, which is exactly what the question asks you to avoid.
When it fits: Worth knowing as the fallback if the array weren't sorted.
static int[] twoSumSortedMap(int[] numbers, int target) {
Map<Integer, Integer> seen = new HashMap<>(); // value -> index
for (int i = 0; i < numbers.length; i++) {
int need = target - numbers[i];
if (seen.containsKey(need)) {
return new int[]{seen.get(need) + 1, i + 1};
}
seen.put(numbers[i], i);
}
return new int[]{};
}numbers[left] + numbers[right] is too small, then numbers[left] can't pair with anything at or before right (those are all smaller or equal to numbers[right]). So left can be safely discarded. Same argument for right when the sum is too big.new int[]{}| Array read | O(1) |
| HashMap.get / put (extra version) | O(1) avg |
Remember: Sorted input + a target sum = two pointers. This is the base case for 3Sum, 3Sum Closest and 4Sum.
Spot it: 'All unique triplets that add up to a target', and the order doesn't matter. Sort first, fix one number, then run the Two Sum II two-pointer on the rest. Skipping duplicates is what makes the answer unique.
This is THE template: 3Sum Closest, 4Sum and k-Sum are the same code with one more loop or a different condition.
Sort the array so each triplet is in a fixed order (smallest first). Try every i < j < k. When the sum is 0, put the triplet in a HashSet so duplicates are dropped automatically.
static List<List<Integer>> threeSumBrute(int[] nums) {
int[] a = nums.clone();
Arrays.sort(a);
Set<List<Integer>> found = new HashSet<>();
int n = a.length;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
for (int k = j + 1; k < n; k++) {
if (a[i] + a[j] + a[k] == 0) {
found.add(Arrays.asList(a[i], a[j], a[k]));
}
}
}
}
return new ArrayList<>(found);
}Fix i. Now it's Two Sum for -a[i] on the numbers to the right: walk j, check whether the needed third value was already seen in this round. Skip repeated values of i so you don't produce the same triplet twice. After a match, skip repeated j values too.
static List<List<Integer>> threeSumBetter(int[] nums) {
int[] a = nums.clone();
Arrays.sort(a);
List<List<Integer>> res = new ArrayList<>();
int n = a.length;
for (int i = 0; i < n; i++) {
if (i > 0 && a[i] == a[i - 1]) continue; // same anchor as last time
Set<Integer> seen = new HashSet<>();
int j = i + 1;
while (j < n) {
int need = -a[i] - a[j];
if (seen.contains(need)) {
res.add(Arrays.asList(a[i], need, a[j]));
while (j + 1 < n && a[j] == a[j + 1]) j++; // skip duplicate j values
}
seen.add(a[j]);
j++;
}
}
return res;
}Sort. For each anchor i, put left = i + 1 and right = n - 1 and run the Two Sum II loop for the target -a[i]. Sum too small: left++. Too big: right--. Match: record it, move both pointers, then skip over equal values on each side so the same triplet isn't added twice. Also skip equal anchors. No extra set needed.
static List<List<Integer>> threeSumBest(int[] nums) {
int[] a = nums.clone();
Arrays.sort(a);
List<List<Integer>> res = new ArrayList<>();
int n = a.length;
for (int i = 0; i < n - 2; i++) {
if (a[i] > 0) break; // smallest is positive: no sum of 0 possible
if (i > 0 && a[i] == a[i - 1]) continue; // skip duplicate anchors
int left = i + 1, right = n - 1;
while (left < right) {
int sum = a[i] + a[left] + a[right];
if (sum < 0) {
left++;
} else if (sum > 0) {
right--;
} else {
res.add(Arrays.asList(a[i], a[left], a[right]));
left++;
right--;
while (left < right && a[left] == a[left - 1]) left++; // skip duplicates
while (left < right && a[right] == a[right + 1]) right--;
}
}
}
return res;
}Sort once. kSum(k, start, target) fixes one number and recurses with k - 1. When k == 2 it runs the two-pointer walk. This one function solves 2Sum II, 3Sum, 4Sum, 5Sum... with the same duplicate-skipping rules.
When it fits: Worth it if an interviewer says 'now do k numbers'. Time is O(n^(k-1)).
static List<List<Integer>> threeSumKSum(int[] nums) {
int[] a = nums.clone();
Arrays.sort(a);
return kSumHelper(a, 3, 0, 0L);
}
private static List<List<Integer>> kSumHelper(int[] a, int k, int start, long target) {
List<List<Integer>> res = new ArrayList<>();
int n = a.length;
if (k == 2) {
int left = start, right = n - 1;
while (left < right) {
long sum = (long) a[left] + a[right];
if (sum < target) {
left++;
} else if (sum > target) {
right--;
} else {
res.add(new ArrayList<>(Arrays.asList(a[left], a[right])));
left++;
right--;
while (left < right && a[left] == a[left - 1]) left++;
while (left < right && a[right] == a[right + 1]) right--;
}
}
return res;
}
for (int i = start; i < n - k + 1; i++) {
if (i > start && a[i] == a[i - 1]) continue;
List<List<Integer>> rest = kSumHelper(a, k - 1, i + 1, target - a[i]);
for (List<Integer> tail : rest) {
tail.add(0, a[i]);
res.add(tail);
}
}
return res;
}Arrays.asList(x, y, z)List<Integer> from values. Good for answers. Don't try to add to it afterwards.HashSet / HashMap keysList.equals and hashCode compare the contents, so [−1,0,1] equals another [−1,0,1]. That's how the brute force dedups. (Arrays do NOT work: they compare by reference.)nums.clone()int[].a[i] == a[i-1]). Skip duplicate left/right values AFTER a match. Skipping before checking would lose valid triplets like [-1,-1,2].while (left < right && ...) inside skips| Arrays.sort(int[]) | O(n log n) |
| HashSet.add / contains | O(1) avg |
| ArrayList.add | O(1) amortised |
| Arrays.asList | O(k) for k values |
| List.hashCode / equals | O(length) |
Remember: Sort, fix one, two pointers for the rest, skip duplicates. Learn it once: 3Sum Closest, 4Sum and k-Sum are the same thing.
Spot it: Same as 3Sum, but nothing has to match exactly: keep the sum with the smallest distance to the target. One answer, so no duplicate handling.
Try all i < j < k. Track the sum whose distance |sum - target| is smallest.
static int threeSumClosestBrute(int[] nums, int target) {
int n = nums.length;
int best = nums[0] + nums[1] + nums[2];
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
for (int k = j + 1; k < n; k++) {
int sum = nums[i] + nums[j] + nums[k];
if (Math.abs(sum - target) < Math.abs(best - target)) {
best = sum;
}
}
}
}
return best;
}Sort. For each pair (i, j), the ideal third number is target - a[i] - a[j]. Binary search (lower bound) for the first value >= that in the part after j; the closest is either that value or the one right before it. Check both.
static int threeSumClosestBetter(int[] nums, int target) {
int[] a = nums.clone();
Arrays.sort(a);
int n = a.length;
int best = a[0] + a[1] + a[2];
for (int i = 0; i < n - 2; i++) {
for (int j = i + 1; j < n - 1; j++) {
int want = target - a[i] - a[j];
int low = j + 1, high = n - 1;
while (low <= high) { // first index in [j+1, n-1] with a[idx] >= want
int mid = low + (high - low) / 2;
if (a[mid] >= want) high = mid - 1;
else low = mid + 1;
}
if (low < n) {
int sum = a[i] + a[j] + a[low];
if (Math.abs(sum - target) < Math.abs(best - target)) best = sum;
}
if (low - 1 > j) {
int sum = a[i] + a[j] + a[low - 1];
if (Math.abs(sum - target) < Math.abs(best - target)) best = sum;
}
}
}
return best;
}Sort. For each anchor i, run the two-pointer walk. After computing sum, update best if it's closer. Then, as usual, sum < target moves left up and sum > target moves right down. An exact hit can't be beaten, so return the target immediately.
static int threeSumClosestBest(int[] nums, int target) {
int[] a = nums.clone();
Arrays.sort(a);
int n = a.length;
int best = a[0] + a[1] + a[2];
for (int i = 0; i < n - 2; i++) {
int left = i + 1, right = n - 1;
while (left < right) {
int sum = a[i] + a[left] + a[right];
if (Math.abs(sum - target) < Math.abs(best - target)) {
best = sum;
}
if (sum == target) return sum; // can't get closer than exact
if (sum < target) left++;
else right--;
}
}
return best;
}Nothing else to add. Hashing doesn't help with 'closest', and sorting + two pointers already reaches the O(n²) floor for 3Sum-type problems.
Math.abs(x)Math.abs(Integer.MIN_VALUE) is still negative, so don't start best as MAX_VALUE and subtract. Starting from a real sum (the first three numbers) avoids this.best with a real tripleta[0] + a[1] + a[2] is a valid answer candidate. A sentinel like MAX_VALUE makes abs(best - target) overflow.low - 1 > j guardj; otherwise you'd reuse j or i as the third element.| Arrays.sort(int[]) | O(n log n) |
| Math.abs | O(1) |
| Array read | O(1) |
Remember: Same loop as 3Sum, but compare distances instead of testing for zero. Early exit on an exact match.
Spot it: Unique quadruplets that sum to a target. Same as 3Sum with one more fixed number. Use long for sums because four values near 10^9 overflow int.
Sort, try every i < j < k < l, store matching quadruplets in a HashSet<List<Integer>> to dedupe.
static List<List<Integer>> fourSumBrute(int[] nums, int target) {
int[] a = nums.clone();
Arrays.sort(a);
Set<List<Integer>> found = new HashSet<>();
int n = a.length;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
for (int k = j + 1; k < n; k++) {
for (int l = k + 1; l < n; l++) {
long sum = (long) a[i] + a[j] + a[k] + a[l];
if (sum == target) {
found.add(Arrays.asList(a[i], a[j], a[k], a[l]));
}
}
}
}
}
return new ArrayList<>(found);
}Sort. Fix i, j, k (skipping repeated values at each level), and binary search for target - a[i] - a[j] - a[k] in the part after k. The sorted order makes the duplicates easy to skip, so no set is needed.
static List<List<Integer>> fourSumBetter(int[] nums, int target) {
int[] a = nums.clone();
Arrays.sort(a);
List<List<Integer>> res = new ArrayList<>();
int n = a.length;
for (int i = 0; i < n; i++) {
if (i > 0 && a[i] == a[i - 1]) continue;
for (int j = i + 1; j < n; j++) {
if (j > i + 1 && a[j] == a[j - 1]) continue;
for (int k = j + 1; k < n; k++) {
if (k > j + 1 && a[k] == a[k - 1]) continue;
long need = (long) target - a[i] - a[j] - a[k];
int low = k + 1, high = n - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (a[mid] == need) {
res.add(Arrays.asList(a[i], a[j], a[k], a[mid]));
break;
}
if (a[mid] < need) low = mid + 1;
else high = mid - 1;
}
}
}
}
return res;
}Two outer loops fix i and j. The inner part is the Two Sum II loop on left = j + 1, right = n - 1 with the remaining target. Same duplicate-skipping rules as 3Sum, applied at four places: both anchors and both pointers. The long sum avoids overflow.
static List<List<Integer>> fourSumBest(int[] nums, int target) {
int[] a = nums.clone();
Arrays.sort(a);
List<List<Integer>> res = new ArrayList<>();
int n = a.length;
for (int i = 0; i < n - 3; i++) {
if (i > 0 && a[i] == a[i - 1]) continue;
for (int j = i + 1; j < n - 2; j++) {
if (j > i + 1 && a[j] == a[j - 1]) continue;
int left = j + 1, right = n - 1;
while (left < right) {
long sum = (long) a[i] + a[j] + a[left] + a[right];
if (sum < target) {
left++;
} else if (sum > target) {
right--;
} else {
res.add(Arrays.asList(a[i], a[j], a[left], a[right]));
left++;
right--;
while (left < right && a[left] == a[left - 1]) left++;
while (left < right && a[right] == a[right + 1]) right--;
}
}
}
}
return res;
}Store the sum of every pair (k, l) in a map from sum to list of index pairs. For each pair (i, j) with i < j, look up target - a[i] - a[j] and use only entries whose indices are after j. About O(n²) pairs, but with duplicates/overflow handling it gets messy and the worst case degrades.
When it fits: Good for the 'count of quadruplets across 4 arrays' version (4Sum II). Awkward for the unique-quadruplets version, so sorting + two pointers is preferred here.
static List<List<Integer>> fourSumMap(int[] nums, int target) {
int[] a = nums.clone();
Arrays.sort(a);
int n = a.length;
Map<Long, List<int[]>> pairs = new HashMap<>();
for (int k = 0; k < n; k++) {
for (int l = k + 1; l < n; l++) {
long s = (long) a[k] + a[l];
if (!pairs.containsKey(s)) {
pairs.put(s, new ArrayList<>());
}
pairs.get(s).add(new int[]{k, l});
}
}
Set<List<Integer>> found = new HashSet<>();
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
long need = (long) target - a[i] - a[j];
if (!pairs.containsKey(need)) continue;
for (int[] p : pairs.get(need)) {
if (p[0] > j) { // indices must be after j
found.add(Arrays.asList(a[i], a[j], a[p[0]], a[p[1]]));
}
}
}
}
return new ArrayList<>(found);
}int overflow in sums(long) a[i] + a[j] + ...: cast the FIRST operand, then the rest are promoted.long sum == targetlong with int is fine: the int is widened.long need vs the arraya[mid] == need compares an int to a long, which is also OK. It can't match when need is out of int range, which is correct.j > i + 1, not j > 0: you only skip a repeated value if it's the same as the one you already tried FOR THIS i.n - 3, n - 2| Arrays.sort(int[]) | O(n log n) |
| HashSet.add (list keys) | O(length) to hash |
| ArrayList.add | O(1) amortised |
| Arrays.asList | O(k) |
Remember: Each extra number in k-Sum adds one nested loop in front of the Two Sum II walk. Cast to long before adding.
Spot it: Maximise width * min(height) between two lines. Start with the widest container and move the SHORTER side inwards, since that's the only move that can ever improve the area.
The area is limited by the shorter wall. Moving the taller wall can only shrink the width and keep the same limit, so it can never help.
For every pair i < j, area is (j - i) * min(height[i], height[j]). Keep the largest.
static int maxAreaBrute(int[] height) {
int best = 0;
for (int i = 0; i < height.length; i++) {
for (int j = i + 1; j < height.length; j++) {
int area = (j - i) * Math.min(height[i], height[j]);
best = Math.max(best, area);
}
}
return best;
}Begin with left = 0 and right = n - 1 (maximum width). Compute the area. Then move whichever wall is shorter: with the shorter wall kept, any narrower container is still capped by that same height, so it can't be better. With the shorter wall replaced, there's at least a chance. Repeat until the pointers meet.
static int maxAreaBest(int[] height) {
int left = 0, right = height.length - 1;
int best = 0;
while (left < right) {
int area = (right - left) * Math.min(height[left], height[right]);
best = Math.max(best, area);
if (height[left] < height[right]) {
left++;
} else {
right--;
}
}
return best;
}Nothing else to add. There is no meaningful alternative: the two-pointer argument is the solution.
height[left] * (smaller width), which is less than what we just measured. So left can be discarded for good.Math.min / Math.maxmin of heights, the answer tracker uses max.else) is fine.| Math.min / max | O(1) |
| Array read | O(1) |
Remember: If one side decides the limit, only moving THAT side can help. Same reasoning as Two Sum II, but with area instead of sum.
Spot it: Water above bar i = min(tallest bar to its left, tallest bar to its right) - height[i]. The two-pointer version works because you only need the SMALLER of the two maxes, and you always know which side is smaller.
For each index, find the highest bar on its left and the highest on its right (including itself). Water on that bar is min(leftMax, rightMax) - height[i]. Sum over all bars.
static int trapBrute(int[] height) {
int n = height.length;
int total = 0;
for (int i = 0; i < n; i++) {
int leftMax = 0;
for (int j = 0; j <= i; j++) {
leftMax = Math.max(leftMax, height[j]);
}
int rightMax = 0;
for (int j = i; j < n; j++) {
rightMax = Math.max(rightMax, height[j]);
}
total += Math.min(leftMax, rightMax) - height[i];
}
return total;
}The inner scans keep recomputing the same maxima. Fill leftMax[i] going left to right and rightMax[i] going right to left, each in one pass using the previous entry. Then each bar is O(1).
static int trapBetter(int[] height) {
int n = height.length;
if (n == 0) return 0;
int[] leftMax = new int[n];
int[] rightMax = new int[n];
leftMax[0] = height[0];
for (int i = 1; i < n; i++) {
leftMax[i] = Math.max(leftMax[i - 1], height[i]);
}
rightMax[n - 1] = height[n - 1];
for (int i = n - 2; i >= 0; i--) {
rightMax[i] = Math.max(rightMax[i + 1], height[i]);
}
int total = 0;
for (int i = 0; i < n; i++) {
total += Math.min(leftMax[i], rightMax[i]) - height[i];
}
return total;
}Keep leftMax and rightMax as single numbers. Whichever side currently has the smaller bar is the side we can finish: if height[left] <= height[right], then whatever the true right max is, it is at least height[right], which is at least height[left], so the limit on the left is leftMax alone. Add leftMax - height[left] and move left. Otherwise do the mirror on the right.
static int trapBest(int[] height) {
int left = 0, right = height.length - 1;
int leftMax = 0, rightMax = 0;
int total = 0;
while (left < right) {
if (height[left] <= height[right]) {
leftMax = Math.max(leftMax, height[left]);
total += leftMax - height[left];
left++;
} else {
rightMax = Math.max(rightMax, height[right]);
total += rightMax - height[right];
right--;
}
}
return total;
}Keep a stack of indices whose bar heights are decreasing. When a taller bar arrives, it closes a 'pool': pop the bottom, the new top of the stack is the left wall and the current bar is the right wall. Water in that layer is (min(wallHeights) - bottom) * width.
When it fits: Counts water row by row instead of column by column. Same O(n), and the pattern also solves Largest Rectangle in Histogram and Next Greater Element.
static int trapStack(int[] height) {
ArrayDeque<Integer> stack = new ArrayDeque<>(); // indices, heights decreasing
int total = 0;
for (int i = 0; i < height.length; i++) {
while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
int bottom = stack.pop();
if (stack.isEmpty()) break; // no left wall
int leftWall = stack.peek();
int width = i - leftWall - 1;
int boundedHeight = Math.min(height[i], height[leftWall]) - height[bottom];
total += width * boundedHeight;
}
stack.push(i);
}
return total;
}That is exactly the Better tier: leftMax[i] and rightMax[i] are two tiny DP tables. Mentioned here because it shows up under the DP label in some lists.
When it fits: Use it to explain how the O(1)-space version was derived.
static int trapDP(int[] height) {
int n = height.length;
if (n == 0) return 0;
int[] prefix = new int[n];
int[] suffix = new int[n];
prefix[0] = height[0];
for (int i = 1; i < n; i++) prefix[i] = Math.max(prefix[i - 1], height[i]);
suffix[n - 1] = height[n - 1];
for (int i = n - 2; i >= 0; i--) suffix[i] = Math.max(suffix[i + 1], height[i]);
int total = 0;
for (int i = 0; i < n; i++) total += Math.min(prefix[i], suffix[i]) - height[i];
return total;
}max - height is never negative.int limit. Use long if the constraints are bigger.height[0] throws on new int[0]. The two-pointer version doesn't touch it, because the loop doesn't run.| Array read / write | O(1) |
| new int[n] | O(n) |
| ArrayDeque push / pop / peek | O(1) (monotonic stack extra) |
Remember: Water at a bar = min(left wall, right wall) - bar. Two pointers because the smaller side's wall is already known to be the limiting one.
| Opposite ends, compare and move inwards | Valid Palindrome, Two Sum II, Container With Most Water, Trapping Rain Water |
| Read / write pointers (in-place filter) | Move Zeroes, Remove Duplicates (and the at-most-k version) |
| Fill the answer from the back | Squares of a Sorted Array |
| Scan from the end so the future is known | Backspace String Compare |
| Sort, fix one number, two pointers for the rest | 3Sum, 3Sum Closest, 4Sum (kSum) |
| Skip duplicates to keep results unique | 3Sum, 4Sum, Remove Duplicates |
| Move the side that limits the answer | Container With Most Water, Trapping Rain Water |
| Extra techniques that came up | Stack (Backspace, Trapping Rain Water), HashMap (Two Sum II), binary search (Two Sum II, 3Sum Closest, 4Sum) |