Every question from the "Arrays and hashing" block of your DSA Pattern Sheet. 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 call used. Where only two real approaches exist, the note says so. After the main three, an Other approaches block adds techniques from other topics (Kadane, sliding window, two pointers, union-find, quickselect, sweep line and so on), with a note on when each one does and doesn't fit, because those topics won't bring these questions back.
Read / write a[i], a.length | O(1) |
| Search unsorted (loop) | O(n) |
| Insert / delete in the middle (shift) | O(n) |
new int[n] (zero-filled) | O(n) |
clone(), Arrays.copyOf, copy with a loop | O(n) |
Arrays.sort(int[]) dual-pivot quicksort, in place | O(n log n) |
Arrays.sort(T[]), list.sort TimSort, stable | O(n log n) |
Arrays.binarySearch (sorted only) | O(log n) |
Arrays.fill, equals, toString | O(n) |
Arrays.asList(arr) fixed-size view | O(1) |
get(i), set(i,x), size() | O(1) |
add(x) at the end | O(1) amortised |
add(i,x), remove(i) | O(n) |
contains, indexOf, remove(Object) | O(n) |
new ArrayList<>(collection), toArray | O(n) |
get, put, containsKey, remove | O(1) avg |
getOrDefault | O(1) avg |
Set: add, contains, remove | O(1) avg |
| Worst case (heavy collisions) | O(log n) |
| Iterate all entries | O(capacity + n) |
keySet(), values(), entrySet() (views) | O(1) |
One null key allowed. Order not guaranteed. LinkedHashMap is the same cost but remembers insertion order. | |
get, put, remove, containsKey | O(log n) |
first, last, floor, ceiling, higher, lower | O(log n) |
| Iterate in sorted order | O(n) |
| Red-black tree. Use it when you need "nearest bigger / smaller" or sorted iteration, otherwise HashMap. | |
offer / add | O(log n) |
poll / remove() | O(log n) |
peek | O(1) |
remove(Object), contains | O(n) |
new PriorityQueue<>(collection) (heapify) | O(n) |
Max-heap: new PriorityQueue<>(Collections.reverseOrder()). Iterating a heap is not sorted. | |
push / pop / peek (stack) | O(1) |
offer / poll / peek (queue) | O(1) |
addFirst / addLast / pollFirst / pollLast | O(1) |
contains | O(n) |
Prefer over Stack (legacy, synchronised) and LinkedList (slower, more memory). No null elements. | |
addFirst / addLast / removeFirst / removeLast | O(1) |
get(i) | O(n) |
contains, indexOf | O(n) |
length(), charAt(i) | O(1) |
substring, toCharArray, concat, + | O(n) |
equals, compareTo | O(n) |
hashCode | O(n) once, then cached |
indexOf, contains | O(n·m) worst |
sb.append, setCharAt, charAt | O(1) |
sb.insert(0,x), deleteCharAt(i), reverse | O(n) |
Strings are immutable. s += x in a loop is O(n²). Use StringBuilder. | |
Integer.MAX_VALUE | 2,147,483,647 (about 2.1 × 10⁹) |
Long.MAX_VALUE | about 9.2 × 10¹⁸ |
| int overflow wraps silently to negative. No exception. | |
| n ≤ 10⁵: aim for O(n) or O(n log n). n ≤ 10³ to 10⁴: O(n²) is usually fine. n ≤ 20: exponential is fine. | |
static void swap(int[] a, int i, int j) {
int t = a[i]; a[i] = a[j]; a[j] = t;
}
static void reverse(int[] a, int lo, int hi) { // inclusive on both ends
while (lo < hi) swap(a, lo++, hi--);
}All snippets assume import java.util.*; and are static methods, so you can paste them into a class and call them from main. Amortised means "averaged over many calls". Avg for hash structures assumes a decent hash function.
Spot it: You need a pair that adds up to a target. For each number the partner is target - x, and 'have I already seen the partner?' is a lookup question. That means a HashMap.
Try every pair (i, j). Slow, but it is your correctness baseline.
static int[] twoSumBrute(int[] nums, int target) {
for (int i = 0; i < nums.length; i++)
for (int j = i + 1; j < nums.length; j++)
if (nums[i] + nums[j] == target) return new int[]{i, j};
return new int[]{};
}Pass 1 stores value → index. Pass 2 looks up target - nums[i] for each i. You must check the partner is not the same index, otherwise [3] with target 6 would pair 3 with itself.
static int[] twoSumBetter(int[] nums, int target) {
Map<Integer, Integer> idx = new HashMap<>();
for (int i = 0; i < nums.length; i++) idx.put(nums[i], i);
for (int i = 0; i < nums.length; i++) {
Integer j = idx.get(target - nums[i]); // null if absent
if (j != null && j != i) return new int[]{i, j};
}
return new int[]{};
}Look in the map before inserting the current number. Because you check first, you can never pair an element with itself, so the extra index check disappears. Same big-O as the better version, but one loop and no second pass.
static int[] twoSumBest(int[] nums, int target) {
Map<Integer, Integer> seen = new HashMap<>(); // value -> index
for (int i = 0; i < nums.length; i++) {
Integer j = seen.get(target - nums[i]);
if (j != null) return new int[]{j, i};
seen.put(nums[i], i);
}
return new int[]{};
}Sort the numbers, put one pointer at each end, and move them inward: sum too small → move the left pointer up, sum too big → move the right pointer down. The problem wants the original indices, so you sort an array of indices instead of the numbers themselves.
When it fits: Worse than the HashMap here because of the sort and the index bookkeeping. It's the right tool when the array is already sorted (Two Sum II), where it needs O(1) space.
static int[] twoSumTwoPointers(int[] nums, int target) {
int n = nums.length;
Integer[] idx = new Integer[n];
for (int i = 0; i < n; i++) idx[i] = i;
Arrays.sort(idx, (a, b) -> Integer.compare(nums[a], nums[b])); // sort indices by value
int l = 0, r = n - 1;
while (l < r) {
int sum = nums[idx[l]] + nums[idx[r]];
if (sum == target) return new int[]{idx[l], idx[r]};
if (sum < target) l++;
else r--;
}
return new int[]{};
}new int[]{i, j}Map.get() returns Integer, not intnull. Assigning that to an int auto-unboxes and throws NullPointerException. Use Integer j = map.get(k) and null-check.containsKey then get is two lookupsget plus a null check is a single lookup. Matters in tight loops.Integer == Integer compares references.equals() or unbox to int first. (j != i above is fine because i is an int, so j is unboxed.)| HashMap.put / get | O(1) avg |
| Array index access | O(1) |
Remember: Check the map first, then insert. This 'seen so far' map is the single most reused trick in array problems.
Spot it: 'Does any value appear twice?' A set remembers what you have seen. Or sort, so equal values become neighbours.
Compare every pair.
static boolean containsDuplicateBrute(int[] nums) {
for (int i = 0; i < nums.length; i++)
for (int j = i + 1; j < nums.length; j++)
if (nums[i] == nums[j]) return true;
return false;
}After sorting, any duplicates sit next to each other, so one scan comparing a[i] with a[i-1] is enough. Cloning keeps the caller's array untouched. If the interviewer lets you modify the input, sort in place and space drops to O(1).
static boolean containsDuplicateBetter(int[] nums) {
int[] a = nums.clone(); // don't mutate the caller's array
Arrays.sort(a);
for (int i = 1; i < a.length; i++)
if (a[i] == a[i - 1]) return true;
return false;
}Add each number to a set. add() returns false when the value was already there, so the check and the insert are one call.
static boolean containsDuplicateBest(int[] nums) {
Set<Integer> seen = new HashSet<>();
for (int x : nums)
if (!seen.add(x)) return true; // false means "already present"
return false;
}distinct() drops repeats, so if the count after distinct() is smaller than the array length there was a duplicate. Same idea as the HashSet, hidden inside the stream. Good to know, but it always processes the whole array, while the HashSet version returns as soon as it finds the first duplicate.
When it fits: Fine for quick code. Avoid when you want an early exit.
static boolean containsDuplicateStream(int[] nums) {
return Arrays.stream(nums).distinct().count() != nums.length;
}If the problem says values are between 0 and some small maximum, a boolean[] indexed by the value replaces the HashSet: no hashing, no boxing.
When it fits: Only when the value range is small and known (for example 0 to 10⁵). With values up to 10⁹ the array would be huge.
static boolean containsDuplicateRange(int[] nums, int maxValue) { // values are in 0..maxValue
boolean[] seen = new boolean[maxValue + 1];
for (int x : nums) {
if (seen[x]) return true;
seen[x] = true;
}
return false;
}Set.add() returns a booleancontains() call. List.add() always returns true, so this is a Set-specific trick.Arrays.sort(int[]) vs Arrays.sort(Integer[])array.clone() on a 1D array is a real copyfor (int x : nums)| HashSet.add / contains | O(1) avg |
| Arrays.sort(int[]) | O(n log n) |
| array.clone() | O(n) |
Remember: Sorting turns 'find equal values' into 'check neighbours'. You will reuse that in Longest Consecutive Sequence and 3Sum.
Spot it: 'Same letters, same counts, any order.' Either make both strings canonical (sort) or compare letter counts.
For every character in s, find an unused matching character in t and tick it off. If any character has no match, it is not an anagram.
static boolean isAnagramBrute(String s, String t) {
if (s.length() != t.length()) return false;
char[] b = t.toCharArray();
boolean[] used = new boolean[b.length];
for (char c : s.toCharArray()) {
boolean found = false;
for (int j = 0; j < b.length; j++) {
if (!used[j] && b[j] == c) { used[j] = true; found = true; break; }
}
if (!found) return false;
}
return true;
}Anagrams become the exact same string once sorted. Compare the two sorted char arrays.
static boolean isAnagramBetter(String s, String t) {
if (s.length() != t.length()) return false;
char[] a = s.toCharArray(), b = t.toCharArray();
Arrays.sort(a);
Arrays.sort(b);
return Arrays.equals(a, b);
}Add 1 for each letter of s and subtract 1 for each letter of t in the same loop. If every slot ends at zero the counts match. For all of Unicode, swap the int[26] for a HashMap<Character,Integer>.
static boolean isAnagramBest(String s, String t) {
if (s.length() != t.length()) return false;
int[] count = new int[26];
for (int i = 0; i < s.length(); i++) {
count[s.charAt(i) - 'a']++;
count[t.charAt(i) - 'a']--;
}
for (int c : count) if (c != 0) return false;
return true;
}This is the follow-up question: what if the strings contain Unicode, not just a to z? A fixed int[26] no longer works, so count with a HashMap<Character, Integer>. Count up for s, then count down for t, and fail if a letter runs out.
When it fits: Use when the alphabet is large or unknown. For plain lowercase letters, the int[26] is faster.
static boolean isAnagramMap(String s, String t) {
if (s.length() != t.length()) return false;
Map<Character, Integer> count = new HashMap<>();
for (char c : s.toCharArray()) {
count.put(c, count.getOrDefault(c, 0) + 1);
}
for (char c : t.toCharArray()) {
int have = count.getOrDefault(c, 0);
if (have == 0) return false; // t has a letter s doesn't have enough of
count.put(c, have - 1);
}
return true;
}c - 'a' turns a letter into an index 0 to 25char is a number, so subtracting gives an int. 'a'-'a' = 0, 'z'-'a' = 25. Only works for lowercase a to z.Arrays.equals(a, b) vs a.equals(b).equals() is identity (same object), not content. Use Arrays.equals for content. Same trap with ==.s.equals(t), never s == t== on Strings compares references. Contents comparison is .equals().toCharArray() copies into a mutable array so you can sort it. new String(chars) goes back.int[26] is all zerosfalse for boolean, null for objects.| String.charAt(i) / length() | O(1) |
| String.toCharArray() | O(n) |
| Arrays.sort(char[]) | O(n log n) |
| Arrays.equals | O(n) |
| int[26] access | O(1) |
Remember: Fixed alphabet means a plain int[26] beats a HashMap: no hashing, no boxing, and the space is O(1).
Spot it: 'Group things that are equivalent.' Find a signature that is identical for every member of a group, then use HashMap<signature, List>. Every grouping problem is this.
Keep a list of groups. For each word, compare it with the first word of each existing group using an anagram check. Join the first group that matches, otherwise start a new group. (k = longest word length.)
static boolean sameLetters(String a, String b) {
if (a.length() != b.length()) return false;
int[] c = new int[26];
for (int i = 0; i < a.length(); i++) { c[a.charAt(i) - 'a']++; c[b.charAt(i) - 'a']--; }
for (int x : c) if (x != 0) return false;
return true;
}
static List<List<String>> groupAnagramsBrute(String[] strs) {
List<List<String>> groups = new ArrayList<>();
for (String s : strs) {
boolean placed = false;
for (List<String> g : groups) {
if (sameLetters(g.get(0), s)) { g.add(s); placed = true; break; }
}
if (!placed) {
List<String> g = new ArrayList<>();
g.add(s);
groups.add(g);
}
}
return groups;
}Sorting the letters of a word gives the same string for every anagram (eat, tea, ate all become aet). Use that as the map key.
static List<List<String>> groupAnagramsBetter(String[] strs) {
Map<String, List<String>> map = new HashMap<>();
for (String s : strs) {
char[] ch = s.toCharArray();
Arrays.sort(ch);
String key = new String(ch);
if (!map.containsKey(key)) {
map.put(key, new ArrayList<>());
}
map.get(key).add(s);
}
return new ArrayList<>(map.values());
}Skip the sort. Count the 26 letters and turn the counts into a string key. The # separator matters: without it, counts 1,11 and 11,1 would both read 111.
static List<List<String>> groupAnagramsBest(String[] strs) {
Map<String, List<String>> map = new HashMap<>();
for (String s : strs) {
int[] count = new int[26];
for (char c : s.toCharArray()) count[c - 'a']++;
StringBuilder sb = new StringBuilder();
for (int n : count) sb.append(n).append('#');
String key = sb.toString();
if (!map.containsKey(key)) {
map.put(key, new ArrayList<>());
}
map.get(key).add(s);
}
return new ArrayList<>(map.values());
}One more you'll see online: give each letter a prime number and use the product of a word's letters as the key. It's a neat idea but it overflows long on long words and can clash, so don't use it.
Same count idea as the best version, but you let Java build the key: Arrays.toString(count) gives text like [1, 0, 0, ..., 1]. Slightly slower than the hand-built key, but there's nothing to get wrong, no delimiter to remember.
When it fits: Good default in an interview where clarity matters more than the last bit of speed.
static List<List<String>> groupAnagramsArrayKey(String[] strs) {
Map<String, List<String>> map = new HashMap<>();
for (String s : strs) {
int[] count = new int[26];
for (char c : s.toCharArray()) count[c - 'a']++;
String key = Arrays.toString(count);
if (!map.containsKey(key)) {
map.put(key, new ArrayList<>());
}
map.get(key).add(s);
}
return new ArrayList<>(map.values());
}map.get(key).add(x). Three map calls per word, all O(1) average.new ArrayList<>(map.values())values() is a Collection, not a List. Wrapping it in an ArrayList converts it. LeetCode wants List<List<String>>.new String(char[]) or String.valueOf(char[])char[].toString(): it prints something like [C@1b6d3586.int[] uses identity hashCode, so two arrays with the same contents are different keys. Convert to a String (as above) or a List<Integer>, whose equals and hashCode use contents.StringBuilder for building strings in a loops += x in a loop copies the string every time (O(n²) total). sb.append(x) is amortised O(1).| HashMap.containsKey / put / get | O(1) avg + hashing the key |
| String.hashCode() | O(k), cached after first call |
| Arrays.sort(char[]) | O(k log k) |
| map.values() | O(1) (a view) |
| new ArrayList<>(collection) | O(size) |
| StringBuilder.append | O(1) amortised |
Remember: Signature + HashMap is the grouping template. Pick the cheapest signature that is the same for equivalent items and different for everything else.
Spot it: 'Top K' or 'K most common': count first, then pick K. Picking can be a full sort (n log n), a size-K heap (n log k), or buckets indexed by frequency (n), since a frequency can never exceed n.
Count with a HashMap, put the entries in a list, sort by count descending, take the first K. (m = number of distinct values, m ≤ n.)
static int[] topKFrequentBrute(int[] nums, int k) {
Map<Integer, Integer> freq = new HashMap<>();
for (int x : nums) {
freq.put(x, freq.getOrDefault(x, 0) + 1);
}
List<Map.Entry<Integer, Integer>> entries = new ArrayList<>(freq.entrySet());
entries.sort((a, b) -> Integer.compare(b.getValue(), a.getValue())); // biggest count first
int[] res = new int[k];
for (int i = 0; i < k; i++) res[i] = entries.get(i).getKey();
return res;
}Keep a min-heap ordered by frequency. Push every entry, and whenever the heap grows past K, pop the smallest. What remains are the K most frequent. Each push or pop costs O(log k), not O(log m).
static int[] topKFrequentBetter(int[] nums, int k) {
Map<Integer, Integer> freq = new HashMap<>();
for (int x : nums) {
freq.put(x, freq.getOrDefault(x, 0) + 1);
}
PriorityQueue<Map.Entry<Integer, Integer>> heap =
new PriorityQueue<>((a, b) -> Integer.compare(a.getValue(), b.getValue())); // min-heap
for (Map.Entry<Integer, Integer> e : freq.entrySet()) {
heap.offer(e);
if (heap.size() > k) heap.poll(); // evict the least frequent
}
int[] res = new int[k];
for (int i = 0; i < k; i++) res[i] = heap.poll().getKey();
return res;
}Make an array of lists where index = frequency. Drop each number in the bucket for its count, then walk from the highest bucket down until you have K numbers. No comparisons needed.
@SuppressWarnings({"unchecked", "rawtypes"})
static int[] topKFrequentBest(int[] nums, int k) {
Map<Integer, Integer> freq = new HashMap<>();
for (int x : nums) {
freq.put(x, freq.getOrDefault(x, 0) + 1);
}
List<Integer>[] bucket = new List[nums.length + 1]; // index = frequency
for (Map.Entry<Integer, Integer> e : freq.entrySet()) {
int f = e.getValue();
if (bucket[f] == null) bucket[f] = new ArrayList<>();
bucket[f].add(e.getKey());
}
int[] res = new int[k];
int p = 0;
for (int f = bucket.length - 1; f > 0 && p < k; f--) {
if (bucket[f] == null) continue;
for (int x : bucket[f]) if (p < k) res[p++] = x;
}
return res;
}Quicksort's partition step, but only recurse into the side that contains position K. After each partition the pivot sits at its final place: everything to its left has a higher frequency, everything to its right has a lower or equal one. Stop when the pivot lands at index K-1, and the first K values are the answer.
When it fits: O(n) on average, but O(m²) if the pivots are unlucky. The bucket sort is safer. Quickselect is the classic answer for 'K-th largest element' too.
static int[] topKFrequentQuickselect(int[] nums, int k) {
Map<Integer, Integer> freq = new HashMap<>();
for (int x : nums) {
freq.put(x, freq.getOrDefault(x, 0) + 1);
}
int m = freq.size();
int[] vals = new int[m];
int p = 0;
for (int key : freq.keySet()) vals[p++] = key;
int lo = 0, hi = m - 1, target = k - 1;
while (lo < hi) {
int pivotPos = partitionByFreq(vals, freq, lo, hi);
if (pivotPos == target) break;
if (pivotPos < target) lo = pivotPos + 1;
else hi = pivotPos - 1;
}
return Arrays.copyOf(vals, k);
}
// Moves values with a HIGHER frequency than the pivot to the left. Returns the pivot's final index.
private static int partitionByFreq(int[] vals, Map<Integer, Integer> freq, int lo, int hi) {
int pivotFreq = freq.get(vals[hi]);
int store = lo;
for (int i = lo; i < hi; i++) {
if (freq.get(vals[i]) > pivotFreq) swap(vals, store++, i);
}
swap(vals, store, hi);
return store;
}getOrDefaultfreq.put(x, freq.getOrDefault(x, 0) + 1): read the current count (0 if the key is new), add 1, write it back.PriorityQueue is a MIN-heap by defaultpoll() gives the smallest. For a max-heap pass Collections.reverseOrder() or a comparator that flips the order.Integer.compare(a, b)a - b. Subtraction can overflow for large or negative values and silently give the wrong order.Map.Entry<K,V>map.entrySet(). getKey() and getValue() read it. Looping over entries beats looping over keys and calling get() each time.new List<Integer>[n] does not compile, so you write new List[n] and silence the compiler warnings with @SuppressWarnings. The alternative is a List<List<Integer>> filled with n empty lists.poll() and peek() respect the order. Do not print or loop over a heap and expect sorted output.| HashMap.getOrDefault / put | O(1) avg |
| PriorityQueue.offer / poll | O(log n) |
| PriorityQueue.peek | O(1) |
| PriorityQueue.remove(Object) / contains | O(n) |
| List.sort | O(m log m) |
| ArrayList.add | O(1) amortised |
Remember: K small and n large? Heap of size K. Values bounded by n (like counts)? Buckets. Say both out loud in an interview.
Spot it: 'Everything except me' and division is banned (or the array has zeros). Split the answer into the product of everything to the left times the product of everything to the right. That is the prefix and suffix idea.
For each index, multiply every other element.
static int[] productExceptSelfBrute(int[] nums) {
int n = nums.length;
int[] res = new int[n];
for (int i = 0; i < n; i++) {
int p = 1;
for (int j = 0; j < n; j++) if (j != i) p *= nums[j];
res[i] = p;
}
return res;
}left[i] is the product of everything before i. right[i] is the product of everything after i. The answer at i is left[i] * right[i]. Easy to reason about, but it uses two extra arrays.
static int[] productExceptSelfBetter(int[] nums) {
int n = nums.length;
int[] left = new int[n], right = new int[n], res = new int[n];
left[0] = 1;
for (int i = 1; i < n; i++) left[i] = left[i - 1] * nums[i - 1];
right[n - 1] = 1;
for (int i = n - 2; i >= 0; i--) right[i] = right[i + 1] * nums[i + 1];
for (int i = 0; i < n; i++) res[i] = left[i] * right[i];
return res;
}Store the left products straight into res. Then sweep from the right with one running variable right and multiply it in. The output array is required anyway, so extra space is O(1).
static int[] productExceptSelfBest(int[] nums) {
int n = nums.length;
int[] res = new int[n];
res[0] = 1;
for (int i = 1; i < n; i++) res[i] = res[i - 1] * nums[i - 1]; // product of everything left of i
int right = 1;
for (int i = n - 1; i >= 0; i--) {
res[i] *= right; // multiply in everything right of i
right *= nums[i];
}
return res;
}Multiply everything except zeros, and count the zeros. No zeros: divide the total by each number. Exactly one zero: only that position gets the product, all others are 0. Two or more zeros: everything is 0.
When it fits: The problem forbids division, so this won't be accepted. It's the first idea most people have, and the zero cases are what trips them. It also breaks once the product overflows, because a wrapped-around product can't be divided back.
static int[] productExceptSelfDivision(int[] nums) {
int n = nums.length, product = 1, zeros = 0;
for (int x : nums) {
if (x == 0) zeros++;
else product *= x;
}
int[] res = new int[n];
for (int i = 0; i < n; i++) {
if (zeros > 1) res[i] = 0;
else if (zeros == 1) res[i] = (nums[i] == 0) ? product : 0;
else res[i] = product / nums[i];
}
return res;
}int[] left = new int[n], right = new int[n]; is legal. Each name gets its own array.int overflow is silentint * int overflows, it wraps around. Use long, or Math.multiplyExact if you want an exception.*= and friendsres[i] *= right means res[i] = res[i] * right. Same for +=, -=, %=.Array allocate new int[n] | O(n) |
| Array index access | O(1) |
Remember: Prefix × suffix. Whenever a problem says 'excluding the current element', think left side and right side separately.
Spot it: Needs O(n), so no sorting. Put everything in a HashSet, then only start counting from numbers that have no x - 1 in the set. Those are the starts of a sequence.
For each number, keep asking 'is x+1 in the array?' by scanning the whole array each time.
static boolean linearContains(int[] a, int v) {
for (int x : a) if (x == v) return true;
return false;
}
static int longestConsecutiveBrute(int[] nums) {
int best = 0;
for (int x : nums) {
int cur = x, len = 1;
while (linearContains(nums, cur + 1)) { cur++; len++; }
best = Math.max(best, len);
}
return best;
}Sorted, a consecutive run is a stretch where each value is the previous plus one. Skip equal neighbours (duplicates don't extend a run), and reset the run length on any bigger gap.
static int longestConsecutiveBetter(int[] nums) {
if (nums.length == 0) return 0;
int[] a = nums.clone();
Arrays.sort(a);
int best = 1, run = 1;
for (int i = 1; i < a.length; i++) {
if (a[i] == a[i - 1]) continue; // duplicate: ignore
if (a[i] == a[i - 1] + 1) run++; // extends the run
else run = 1; // gap: restart
best = Math.max(best, run);
}
return best;
}If x - 1 is in the set, x is in the middle of a sequence, so skip it. Otherwise x is a start: walk upward while cur + 1 is in the set. The inner loop looks like it could be O(n²), but each number is walked over at most once as part of one chain, so the total is O(n).
static int longestConsecutiveBest(int[] nums) {
Set<Integer> set = new HashSet<>();
for (int x : nums) set.add(x);
int best = 0;
for (int x : set) {
if (set.contains(x - 1)) continue; // not a start, skip
int cur = x, len = 1;
while (set.contains(cur + 1)) { cur++; len++; }
best = Math.max(best, len);
}
return best;
}Store, for each number, the length of the sequence it belongs to, but only keep it correct at the two ends of each sequence. When a new number x arrives, read the lengths of its neighbours (x-1 and x+1), add them up with 1, and write the new total at the two new ends. Processes each number once with no inner loop.
When it fits: Same O(n) as the best version. Nice trick to know; harder to come up with in an interview.
static int longestConsecutiveLengthMap(int[] nums) {
Map<Integer, Integer> len = new HashMap<>(); // number -> length of its sequence (valid at the ends)
int best = 0;
for (int x : nums) {
if (len.containsKey(x)) continue; // duplicate
int left = len.getOrDefault(x - 1, 0);
int right = len.getOrDefault(x + 1, 0);
int total = left + right + 1;
len.put(x, total);
len.put(x - left, total); // new left end
len.put(x + right, total); // new right end
best = Math.max(best, total);
}
return best;
}Each number starts in its own group. For every number x, if x+1 exists, join their groups. Track the size of each group; the biggest group is the longest consecutive sequence. find uses path halving so the trees stay flat.
When it fits: Overkill here, but it's the pattern you'll need for Number of Provinces, Redundant Connection and Accounts Merge. Practise it on an easy case first.
private static int ufFind(Map<Integer, Integer> parent, int x) {
while (parent.get(x) != x) {
parent.put(x, parent.get(parent.get(x))); // path halving
x = parent.get(x);
}
return x;
}
static int longestConsecutiveUnionFind(int[] nums) {
Map<Integer, Integer> parent = new HashMap<>();
Map<Integer, Integer> size = new HashMap<>();
for (int x : nums) {
if (!parent.containsKey(x)) { parent.put(x, x); size.put(x, 1); }
}
int best = parent.isEmpty() ? 0 : 1;
for (int x : parent.keySet()) {
if (parent.containsKey(x + 1)) {
int a = ufFind(parent, x), b = ufFind(parent, x + 1);
if (a != b) {
parent.put(a, b);
size.put(b, size.get(a) + size.get(b));
best = Math.max(best, size.get(b));
}
}
}
return best;
}for (int x : set)Set<Integer> straight into an int; Java unboxes. Looping the set (not the array) also skips duplicates for free.continue skips to the next loop iterationif.x + 1 can overflow at Integer.MAX_VALUE| HashSet.add / contains | O(1) avg |
| Arrays.sort(int[]) | O(n log n) |
| Linear scan of an array | O(n) |
Remember: 'Only start from the beginning of a chain' turns a nested loop into amortised O(n). Same idea as skipping duplicates in 3Sum.
Spot it: 'Left sum equals right sum.' That is a prefix sum question. You never need to re-add anything, because right = total - left - nums[i].
For each index, add up everything to its left and everything to its right.
static int pivotIndexBrute(int[] nums) {
for (int i = 0; i < nums.length; i++) {
int left = 0, right = 0;
for (int j = 0; j < i; j++) left += nums[j];
for (int j = i + 1; j < nums.length; j++) right += nums[j];
if (left == right) return i;
}
return -1;
}prefix[i] = sum of the first i elements. Left of index i is prefix[i], right is prefix[n] - prefix[i+1]. The extra leading 0 in prefix means index 0 needs no special case.
static int pivotIndexBetter(int[] nums) {
int n = nums.length;
int[] prefix = new int[n + 1]; // prefix[i] = sum of nums[0..i-1]
for (int i = 0; i < n; i++) prefix[i + 1] = prefix[i] + nums[i];
for (int i = 0; i < n; i++) {
int left = prefix[i];
int right = prefix[n] - prefix[i + 1];
if (left == right) return i;
}
return -1;
}Compute the total once. While scanning, keep the running left sum. The right sum is total - left - nums[i], so no array is needed.
static int pivotIndexBest(int[] nums) {
int total = 0;
for (int x : nums) total += x;
int left = 0;
for (int i = 0; i < nums.length; i++) {
if (left == total - left - nums[i]) return i;
left += nums[i];
}
return -1;
}Nothing else to add. Prefix sums are the only real idea. It is not a sliding-window or Kadane problem because the condition (left sum = right sum) depends on both sides of the index, not on a window.
Arrays.stream(nums).sum()int[]. Fine for readability; a plain loop is just as fast.long when sums can get biglong.prefix[n+1] padding trick| Array index access | O(1) |
| Arrays.stream(a).sum() | O(n) |
Remember: Running total beats a prefix array when you only need the sum up to the current point. Keep the array only if you need arbitrary range queries.
Spot it: 'Count subarrays with sum exactly K', and negatives are allowed, so a sliding window will not work. Use prefix sums: sum(i..j) = P[j] - P[i-1], so at each j you need to know how many earlier prefixes equal P[j] - k.
Try every start and end, and add up the elements inside each time.
static int subarraySumBrute(int[] nums, int k) {
int count = 0;
for (int i = 0; i < nums.length; i++)
for (int j = i; j < nums.length; j++) {
int sum = 0;
for (int t = i; t <= j; t++) sum += nums[t];
if (sum == k) count++;
}
return count;
}Fix the start i and extend j one step at a time, adding nums[j] to a running sum. That removes the innermost loop.
static int subarraySumBetter(int[] nums, int k) {
int count = 0;
for (int i = 0; i < nums.length; i++) {
int sum = 0;
for (int j = i; j < nums.length; j++) {
sum += nums[j];
if (sum == k) count++;
}
}
return count;
}Walk once, keeping the running prefix sum. If an earlier prefix equalled sum - k, then the stretch between that point and here sums to k. The map stores how many times each prefix value has appeared. Seed it with {0: 1} so subarrays that start at index 0 get counted.
static int subarraySumBest(int[] nums, int k) {
Map<Integer, Integer> seen = new HashMap<>(); // prefix sum -> how many times
seen.put(0, 1); // empty prefix
int sum = 0, count = 0;
for (int x : nums) {
sum += x;
count += seen.getOrDefault(sum - k, 0);
seen.put(sum, seen.getOrDefault(sum, 0) + 1);
}
return count;
}If every number is 0 or more, the sum only grows as the window grows, so a two-pointer window works. Count subarrays with sum at most k, minus those with sum at most k-1: what's left is exactly k. This 'at most K minus at most K-1' trick is reused in many sliding-window questions.
When it fits: Breaks completely with negative numbers: shrinking the window no longer reduces the sum in a predictable way. Example: [-1, 1, 1] with k = 0 has 1 matching subarray, but this code returns 3. The real problem allows negatives, so this is NOT a valid answer to it. Say it only as the 'what if all numbers were non-negative' follow-up.
// ONLY valid when nums has no negative numbers
static int subarraySumSlidingWindow(int[] nums, int k) {
return atMostSum(nums, k) - atMostSum(nums, k - 1);
}
private static int atMostSum(int[] nums, int limit) { // count subarrays with sum <= limit
if (limit < 0) return 0;
int count = 0, sum = 0, left = 0;
for (int right = 0; right < nums.length; right++) {
sum += nums[right];
while (sum > limit) sum -= nums[left++]; // shrink from the left
count += right - left + 1; // every window ending at `right`
}
return count;
}map.getOrDefault(key, 0)seen.put(0, 1) firstsum - k before inserting the current sum. When k is 0, inserting first would count an empty subarray.| HashMap.getOrDefault | O(1) avg |
| HashMap.put | O(1) avg |
Remember: Negatives in the array means no sliding window. Reach for prefix sums plus a count map. This exact pattern also solves Contiguous Array, and the 'subarray divisible by K' family.
Spot it: 'Longest subarray with equal 0s and 1s.' Treat each 0 as -1. Equal counts means the subarray sums to 0, so two equal prefix sums mark a balanced stretch between them. Keep the earliest index of each prefix to get the longest.
For every subarray, count the zeros and ones from scratch.
static int findMaxLengthBrute(int[] nums) {
int best = 0;
for (int i = 0; i < nums.length; i++)
for (int j = i; j < nums.length; j++) {
int zeros = 0, ones = 0;
for (int t = i; t <= j; t++) {
if (nums[t] == 0) zeros++; else ones++;
}
if (zeros == ones) best = Math.max(best, j - i + 1);
}
return best;
}Map 0 → -1 and 1 → +1 and keep a running balance as j extends. A balance of 0 means equal counts.
static int findMaxLengthBetter(int[] nums) {
int best = 0;
for (int i = 0; i < nums.length; i++) {
int bal = 0;
for (int j = i; j < nums.length; j++) {
bal += nums[j] == 1 ? 1 : -1;
if (bal == 0) best = Math.max(best, j - i + 1);
}
}
return best;
}Track the running balance for the whole array. The first time you see a balance, record its index. If you see the same balance again at index i, everything between has net zero, so the length is i - firstIndex. Seed with balance 0 at index -1 so a balanced prefix is counted.
static int findMaxLengthBest(int[] nums) {
Map<Integer, Integer> first = new HashMap<>(); // balance -> earliest index
first.put(0, -1);
int bal = 0, best = 0;
for (int i = 0; i < nums.length; i++) {
bal += nums[i] == 1 ? 1 : -1;
Integer prev = first.get(bal);
if (prev != null) best = Math.max(best, i - prev);
else first.put(bal, i); // only store the FIRST time
}
return best;
}Sliding window, two pointers and Kadane do NOT work here. Adding a 0 or 1 to the window doesn't move 'balance' in one direction, so you can't tell when to shrink. The prefix-balance trick is the real solution.
The running balance can only be between -n and +n, so shift it by n and use an int[2n+1] as the 'first index seen' table. Filled with a marker meaning 'not seen'. Same algorithm as the best version, just faster in practice (no hashing, no boxing).
When it fits: Handy when the range of the key is small and known.
static int findMaxLengthArray(int[] nums) {
int n = nums.length;
int[] first = new int[2 * n + 1]; // balance + n -> earliest index
Arrays.fill(first, -2); // -2 means "not seen yet"
first[n] = -1; // balance 0 before the array starts
int bal = 0, best = 0;
for (int i = 0; i < n; i++) {
bal += nums[i] == 1 ? 1 : -1;
int slot = bal + n;
if (first[slot] != -2) best = Math.max(best, i - first[slot]);
else first[slot] = i;
}
return best;
}cond ? a : bbal += nums[i] == 1 ? 1 : -1;.[-n, n], so int[] first = new int[2n+1] filled with a sentinel (Arrays.fill(first, -2)) and offset by n is faster than a HashMap.| HashMap.get / put | O(1) avg |
| Arrays.fill | O(n) |
Remember: Convert to ±1, then it is 'longest subarray with sum 0'. Store the first index of each prefix, never overwrite it.
Spot it: 'Best contiguous chunk' where a number can be negative. At each index decide: extend the chunk I had, or start fresh here. That decision is Kadane's algorithm.
Try every start; extend the end one step at a time with a running sum and track the max.
static int maxSubArrayBrute(int[] nums) {
int best = Integer.MIN_VALUE;
for (int i = 0; i < nums.length; i++) {
int sum = 0;
for (int j = i; j < nums.length; j++) {
sum += nums[j];
best = Math.max(best, sum);
}
}
return best;
}Split in half. The best subarray is entirely in the left half, entirely in the right half, or crosses the middle. The crossing case is the best suffix of the left half plus the best prefix of the right half. Not what you'd normally write, but it is a classic follow-up question.
static int maxSubArrayBetter(int[] nums) {
return maxSubArrayDC(nums, 0, nums.length - 1);
}
private static int maxSubArrayDC(int[] a, int lo, int hi) {
if (lo == hi) return a[lo];
int mid = (lo + hi) >>> 1;
int leftBest = maxSubArrayDC(a, lo, mid);
int rightBest = maxSubArrayDC(a, mid + 1, hi);
int s = 0, leftCross = Integer.MIN_VALUE;
for (int i = mid; i >= lo; i--) { s += a[i]; leftCross = Math.max(leftCross, s); }
s = 0;
int rightCross = Integer.MIN_VALUE;
for (int i = mid + 1; i <= hi; i++) { s += a[i]; rightCross = Math.max(rightCross, s); }
return Math.max(Math.max(leftBest, rightBest), leftCross + rightCross);
}Keep a running sum and add each number to it. After every addition, record the best total seen so far in maxsum. If sum ever drops below 0, reset it to 0: a negative running total can only drag down whatever comes next, so starting fresh is always better. The order matters: update maxsum first, then reset. That is what makes all-negative arrays work, because the best (least negative) single value is recorded before the reset throws it away.
static int maxSubArrayBest(int[] nums) {
int sum = 0;
int maxsum = Integer.MIN_VALUE;
for (int i = 0; i < nums.length; i++) {
sum += nums[i]; // add the current number to the running sum
maxsum = Math.max(maxsum, sum); // record the best BEFORE any reset
if (sum < 0) {
sum = 0; // negative running sum only hurts: start fresh
}
}
return maxsum;
}dp[i] is the best sum of a subarray that ends exactly at i. Either it extends the one ending at i-1, or it starts fresh at i. The answer is the biggest dp[i]. This is Kadane before you notice that only dp[i-1] is ever needed.
When it fits: The textbook DP form. Interviewers like seeing this first, then you optimise the array away.
static int maxSubArrayDpArray(int[] nums) {
int n = nums.length;
int[] dp = new int[n]; // dp[i] = best sum of a subarray ending at i
dp[0] = nums[0];
int best = dp[0];
for (int i = 1; i < n; i++) {
dp[i] = Math.max(nums[i], dp[i - 1] + nums[i]);
best = Math.max(best, dp[i]);
}
return best;
}A subarray sum is prefix[j] - prefix[i] with i < j. For each j, the best i is the one with the smallest earlier prefix. So keep a running minimum of prefix sums, starting with 0 for the empty prefix.
When it fits: A different way to see the same O(n) solution. Reuses the stock-profit idea: best 'sell' minus lowest earlier 'buy'.
static int maxSubArrayPrefixMin(int[] nums) {
int prefix = 0, minPrefix = 0, best = Integer.MIN_VALUE;
for (int x : nums) {
prefix += x;
best = Math.max(best, prefix - minPrefix); // best subarray ending here
minPrefix = Math.min(minPrefix, prefix); // update AFTER using it
}
return best;
}A very common follow-up: 'return the subarray, not just the sum'. Track where the current run started. When you restart (the new element beats extending), the start moves to i. When you beat the best, save the start and end.
When it fits: Returns {sum, startIndex, endIndex}.
static int[] maxSubArrayWithIndices(int[] nums) { // returns {sum, start, end}
int sum = 0;
int maxsum = Integer.MIN_VALUE;
int start = 0, bestStart = 0, bestEnd = 0; // start = where the current run began
for (int i = 0; i < nums.length; i++) {
sum += nums[i];
if (sum > maxsum) { // new best: remember where it began and ended
maxsum = sum;
bestStart = start;
bestEnd = i;
}
if (sum < 0) {
sum = 0;
start = i + 1; // fresh run starts at the next index
}
}
return new int[]{maxsum, bestStart, bestEnd};
}Integer.MIN_VALUE as the starting 'best'MIN_VALUE + (-1) wraps around.(lo + hi) >>> 1 for the midpoint(lo + hi) / 2 has when both are huge. lo + (hi - lo) / 2 is the other safe form.Math.max only takes two argumentsMath.max(a, Math.max(b, c)).private static helper| Math.max / Math.min | O(1) |
| Array index access | O(1) |
Remember: 'Extend or restart' is the DP shape behind half the array problems (Maximum Product Subarray, House Robber, Best Time to Buy and Sell Stock).
Spot it: Maximise sell - buy where buy comes before sell. For each day as the sell day, the best buy day is the cheapest price so far.
Try every buy day and every later sell day.
static int maxProfitBrute(int[] prices) {
int best = 0;
for (int i = 0; i < prices.length; i++)
for (int j = i + 1; j < prices.length; j++)
best = Math.max(best, prices[j] - prices[i]);
return best;
}maxRight[i] = highest price from day i onward. For each buy day, the best profit is maxRight[i] - prices[i]. It works, but it needs an array when a single variable would do (see the best version).
static int maxProfitBetter(int[] prices) {
int n = prices.length;
int[] maxRight = new int[n];
maxRight[n - 1] = prices[n - 1];
for (int i = n - 2; i >= 0; i--) maxRight[i] = Math.max(maxRight[i + 1], prices[i]);
int best = 0;
for (int i = 0; i < n; i++) best = Math.max(best, maxRight[i] - prices[i]);
return best;
}Walk left to right keeping the lowest price seen so far. Treat today as the sell day: profit = today - lowest. Keep the max.
static int maxProfitBest(int[] prices) {
int min = Integer.MAX_VALUE, best = 0;
for (int p : prices) {
min = Math.min(min, p);
best = Math.max(best, p - min);
}
return best;
}buy points to the cheapest day so far and sell scans ahead. If today is cheaper than the buy day, move buy to today (a better buy). Otherwise compute the profit. Exactly the same logic as 'track the minimum', but in two-pointer language, which is how it's usually taught.
When it fits: Same cost as the best version. Know this name for it.
static int maxProfitTwoPointers(int[] prices) {
int buy = 0, best = 0; // buy = index of the cheapest day so far
for (int sell = 1; sell < prices.length; sell++) {
if (prices[sell] < prices[buy]) buy = sell; // found a cheaper day to buy
else best = Math.max(best, prices[sell] - prices[buy]);
}
return best;
}Profit from buying on day i and selling on day j equals the sum of the daily changes from i+1 to j. So the question becomes Maximum Subarray on the array of differences. The only change from plain Kadane: never go below 0, because 'do nothing' is allowed.
When it fits: This is the link between this problem and Maximum Subarray. Interviewers sometimes ask for it.
static int maxProfitKadane(int[] prices) {
int sum = 0, maxsum = 0;
for (int i = 1; i < prices.length; i++) {
sum += prices[i] - prices[i - 1]; // today's price change
maxsum = Math.max(maxsum, sum);
if (sum < 0) {
sum = 0; // losing run: give up and start fresh
}
}
return maxsum;
}Integer.MAX_VALUE as the 'no minimum yet' starting valueMath.min replaces it. Mirror of the MIN_VALUE trick for max.| Math.min / Math.max | O(1) |
| Array index access | O(1) |
Remember: 'Best so far to my left' as a single running variable shows up everywhere: min price, max height, running sum.
Spot it: Only three distinct values (0, 1, 2) and in-place. That's counting sort, or the Dutch National Flag with three pointers for a single pass.
Call the library sort. Correct, but it ignores the fact that there are only three values, so it does more work than needed (and the problem says not to use it).
static void sortColorsBrute(int[] nums) {
Arrays.sort(nums);
}Pass 1 counts how many 0s, 1s and 2s there are. Pass 2 overwrites the array with that many of each in order.
static void sortColorsBetter(int[] nums) {
int[] count = new int[3];
for (int x : nums) count[x]++;
int idx = 0;
for (int color = 0; color < 3; color++)
for (int c = 0; c < count[color]; c++) nums[idx++] = color;
}low is where the next 0 goes, high is where the next 2 goes, and mid scans. A 0 swaps to the front (and both low and mid advance). A 1 stays (mid advances). A 2 swaps to the back (only high moves). Don't advance mid after a 2 swap: the value that came from the back hasn't been looked at yet.
static void sortColorsBest(int[] nums) {
int low = 0, mid = 0, high = nums.length - 1;
while (mid <= high) {
if (nums[mid] == 0) swap(nums, low++, mid++);
else if (nums[mid] == 1) mid++;
else swap(nums, mid, high--); // don't advance mid
}
}Same trick as quicksort's partition, done twice. Pass 1: swap every 0 to the front. Pass 2: starting where the 0s end, swap every 1 to the front of what's left. The 2s end up at the back by themselves. Two passes, but each is trivially simple.
When it fits: Easier to get right than the three-pointer version. The Dutch flag still wins on a single pass.
static void sortColorsTwoPartitions(int[] nums) {
int next = 0;
for (int i = 0; i < nums.length; i++)
if (nums[i] == 0) swap(nums, next++, i); // all 0s to the front
for (int i = next; i < nums.length; i++)
if (nums[i] == 1) swap(nums, next++, i); // then all 1s
}nums = new int[5] inside the method only changes the local variable. Why void works for in-place problems.swap(nums, low++, mid++)swap helper is on the cheat sheet at the top of the page.count[x]++ uses the colour itself as the index. Fast counting when values are small and non-negative.| Arrays.sort(int[]) | O(n log n) |
| int[3] count array | O(1) access |
| swap two elements | O(1) |
Remember: Three pointers partition an array in one pass. The same idea drives quicksort's partition step and 'move zeroes'.
Spot it: Shift everything right by k with wraparound. Think of the index formula (i + k) % n. For in-place, reverse the whole array, then reverse the first k, then the rest.
Remember the last element, shift everyone right by one, drop the saved element at the front. Repeat k times. k %= n first, because rotating by n does nothing.
static void rotateBrute(int[] nums, int k) {
int n = nums.length;
k %= n;
for (int step = 0; step < k; step++) {
int last = nums[n - 1];
for (int i = n - 1; i > 0; i--) nums[i] = nums[i - 1];
nums[0] = last;
}
}Element at index i lands at (i + k) % n. Write each one to its new place in a copy, then copy the result back.
static void rotateBetter(int[] nums, int k) {
int n = nums.length;
k %= n;
int[] copy = new int[n];
for (int i = 0; i < n; i++) copy[(i + k) % n] = nums[i];
for (int i = 0; i < n; i++) {
nums[i] = copy[i]; // copy the result back
}
}Rotating right by k = reverse everything, then reverse the first k elements, then reverse the remaining n-k. Try it on [1,2,3,4,5] with k=2: [5,4,3,2,1] → [4,5,3,2,1] → [4,5,1,2,3].
static void rotateBest(int[] nums, int k) {
int n = nums.length;
k %= n;
reverse(nums, 0, n - 1);
reverse(nums, 0, k - 1);
reverse(nums, k, n - 1);
}Each element has a fixed destination (i + k) % n. Pick up the element at start, drop it at its destination, pick up whatever was there, and keep going until you loop back to start. If the loop closes before all n elements have moved (when gcd(n, k) > 1), start again from the next index. Count the moves so you know when you're done.
When it fits: O(n) time, O(1) space, one pass. Trickier than three reversals, but a favourite 'in-place' trick.
static void rotateCyclic(int[] nums, int k) {
int n = nums.length;
k %= n;
int moved = 0;
for (int start = 0; moved < n; start++) {
int cur = start, carry = nums[start];
do {
int next = (cur + k) % n;
int tmp = nums[next];
nums[next] = carry; // drop the carried value at its destination
carry = tmp; // pick up what was there
cur = next;
moved++;
} while (cur != start);
}
}k %= nk = k % n. Rotating by k and by k + n gives the same result. If n could be 0, guard it first or you get ArithmeticException (division by zero).for (int i = 0; i < n; i++) nums[i] = copy[i];. Assigning nums = copy would only change the local variable, the caller's array stays as it was.Arrays.copyOf and Arrays.copyOfRangecopyOfRange(a, from, to) has to exclusive.(i + k) % n turns 'past the end' into 'back to the start'. Same trick for circular buffers.| Copy back with a loop | O(n) |
| Arrays.copyOf | O(n) |
| reverse(a, lo, hi) helper | O(hi - lo) |
Remember: Three reversals is a trick worth memorising: it rotates in place with no extra space.
Spot it: 'The next arrangement in dictionary order.' Find the longest descending tail, bump the digit just before it up to the next larger value from the tail, then make the tail as small as possible (sorted ascending).
Generate all distinct permutations in a TreeSet (which keeps them sorted), find the one just above the current, and wrap to the smallest if the current is the largest. Factorial time: fine to describe, unusable beyond n≈10.
static void nextPermutationBrute(int[] nums) {
TreeSet<List<Integer>> all = new TreeSet<>((a, b) -> {
for (int i = 0; i < a.size(); i++) {
int c = Integer.compare(a.get(i), b.get(i));
if (c != 0) return c;
}
return 0;
});
permuteNP(nums.clone(), 0, all);
List<Integer> cur = new ArrayList<>();
for (int x : nums) cur.add(x);
List<Integer> next = all.higher(cur); // strictly greater
if (next == null) next = all.first(); // was the largest: wrap around
for (int i = 0; i < nums.length; i++) nums[i] = next.get(i);
}
private static void permuteNP(int[] a, int idx, TreeSet<List<Integer>> out) {
if (idx == a.length) {
List<Integer> l = new ArrayList<>();
for (int x : a) l.add(x);
out.add(l);
return;
}
for (int i = idx; i < a.length; i++) {
swap(a, idx, i);
permuteNP(a, idx + 1, out);
swap(a, idx, i); // undo (backtrack)
}
}1) From the right, find the first index i where nums[i] < nums[i+1] (the pivot). 2) From the right, find the first j with nums[j] > nums[i] and swap them. 3) The part after i is still descending; sort it ascending to make it the smallest possible. If no pivot exists the array is the largest permutation: sorting the whole thing gives the smallest.
static void nextPermutationBetter(int[] nums) {
int i = nums.length - 2;
while (i >= 0 && nums[i] >= nums[i + 1]) i--; // find pivot
if (i >= 0) {
int j = nums.length - 1;
while (nums[j] <= nums[i]) j--; // just-larger value from the right
swap(nums, i, j);
}
Arrays.sort(nums, i + 1, nums.length); // smallest tail
}After the swap, the tail is still in descending order (that's why the swap works). Reversing a descending run gives an ascending run in O(n), so the sort is unnecessary.
static void nextPermutationBest(int[] nums) {
int i = nums.length - 2;
while (i >= 0 && nums[i] >= nums[i + 1]) i--;
if (i >= 0) {
int j = nums.length - 1;
while (nums[j] <= nums[i]) j--;
swap(nums, i, j);
}
reverse(nums, i + 1, nums.length - 1);
}Nothing else to add. There are only two real ideas: generate all permutations (brute force), or the pivot, swap, reverse algorithm. No sorting, window or DP shortcut exists.
Arrays.sort(a, fromIndex, toIndex)toIndex is exclusive. Handy for 'sort the tail'.TreeSet.higher(e) / lower(e) / ceiling(e) / floor(e)higher is strictly greater, ceiling is greater or equal.Comparator for a List<Integer> key>= vs > in the pivot search>= when skipping the descending tail. Using > makes [1,5,1]-style inputs go wrong.swap in permuteNP. Same shape in Subsets and Permutations.| TreeSet.add / higher / first | O(log n) × comparator cost |
| Arrays.sort(a, from, to) | O((to-from) log) |
| reverse(a, lo, hi) | O(hi - lo) |
Remember: Tail descending means it's already the 'biggest' arrangement of those digits. To step forward, change the digit before it, then reset the tail to smallest.
Spot it: Overlapping ranges: sort by start, then sweep once. If the next start is within the last merged end, extend the end; otherwise start a new interval.
There's no natural middle step here. It jumps from 'keep merging pairs until nothing changes' straight to 'sort and sweep'. Treat the sort as the key insight.
Look for any two intervals that overlap, merge them into one, and start over. Stop when a full scan finds no overlap. Sort at the end so the output order is predictable.
static int[][] mergeBrute(int[][] intervals) {
List<int[]> list = new ArrayList<>();
for (int[] iv : intervals) list.add(new int[]{iv[0], iv[1]});
boolean changed = true;
while (changed) {
changed = false;
outer:
for (int i = 0; i < list.size(); i++) {
for (int j = i + 1; j < list.size(); j++) {
int[] a = list.get(i), b = list.get(j);
if (a[0] <= b[1] && b[0] <= a[1]) { // overlap test
a[0] = Math.min(a[0], b[0]);
a[1] = Math.max(a[1], b[1]);
list.remove(j);
changed = true;
break outer; // restart the scan
}
}
}
}
list.sort((x, y) -> Integer.compare(x[0], y[0]));
return list.toArray(new int[0][]);
}Sort by start. Hold the interval you are currently building in cur. For each next interval: if it starts inside cur (its start is at or before cur's end), stretch cur's end. Otherwise cur is finished, so save it and start a new cur from this interval. Save the last cur after the loop. Sorting is what guarantees one pass is enough.
static int[][] mergeBest(int[][] intervals) {
if (intervals.length == 0) return new int[0][]; // guard: sorted[0] below needs at least one interval
int[][] sorted = intervals.clone();
Arrays.sort(sorted, (a, b) -> Integer.compare(a[0], b[0]));
ArrayList<int[]> res = new ArrayList<>();
int[] cur = sorted[0].clone(); // the interval being built
for (int i = 1; i < sorted.length; i++) {
if (sorted[i][0] >= cur[0] && sorted[i][0] <= cur[1]) {
cur[1] = Math.max(cur[1], sorted[i][1]); // overlaps: stretch the end
} else {
res.add(cur); // gap: cur is done
cur = sorted[i].clone();
}
}
res.add(cur); // don't forget the last one
return res.toArray(new int[0][]);
}Turn each interval into two events: a start and an end. Sort the events by position (starts before ends at the same position, so touching intervals merge). Walk through them keeping a count of 'currently open' intervals. When the count goes from 0 to 1 a merged interval begins; when it returns to 0 it ends.
When it fits: Same O(n log n). This is the pattern behind Meeting Rooms II, Car Pooling and My Calendar, so it is worth knowing here.
static int[][] mergeSweepLine(int[][] intervals) {
int n = intervals.length;
int[][] events = new int[2 * n][];
for (int i = 0; i < n; i++) {
events[2 * i] = new int[]{intervals[i][0], 0}; // 0 = start
events[2 * i + 1] = new int[]{intervals[i][1], 1}; // 1 = end
}
Arrays.sort(events, (a, b) -> a[0] != b[0] ? Integer.compare(a[0], b[0])
: Integer.compare(a[1], b[1])); // starts before ends
List<int[]> res = new ArrayList<>();
int open = 0, start = 0;
for (int[] e : events) {
if (e[1] == 0) {
if (open == 0) start = e[0]; // a new merged block begins
open++;
} else {
open--;
if (open == 0) res.add(new int[]{start, e[0]}); // block ends
}
}
return res.toArray(new int[0][]);
}Arrays.sort(T[], Comparator) on int[][]int[], so the comparator sees two rows: (a, b) -> Integer.compare(a[0], b[0]). Needs an object array; it won't work on a flat int[].a[0] - b[0] in comparatorsInteger.compare is always safe.list.toArray(new int[0][])List<int[]> into int[][]. The empty array just tells Java the target type.res.get(res.size() - 1) is the 'peek at the last element' idiomgetLast() before Java 21; size() - 1 works everywhere.break outer;list.remove(int) vs list.remove(Object)List<Integer>, remove(2) removes the element at index 2, not the value 2. Use remove(Integer.valueOf(2)) for the value.clone() on a 2D array is shallow| Arrays.sort(Object[]) (TimSort) | O(n log n), stable |
| ArrayList.get / set | O(1) |
| ArrayList.add (end) | O(1) amortised |
| ArrayList.remove(index) | O(n) |
| list.toArray | O(n) |
Remember: Sort first and the problem collapses to one pass. Same move in Meeting Rooms, Non-overlapping Intervals and Minimum Arrows.
Spot it: The list is already sorted and non-overlapping, so you don't need to sort. Three phases in one pass: copy intervals that end before the new one starts, merge everything that overlaps, copy the rest.
Two tiers only. Binary search could find the position in O(log n), but you still have to copy the list, so the total stays O(n).
Throw the new interval into the list, sort by start, and run the same cur merge as Merge Intervals. It ignores that the input is already sorted, so it pays for an unnecessary sort.
static int[][] insertBrute(int[][] intervals, int[] newInterval) {
int[][] sorted = new int[intervals.length + 1][];
for (int i = 0; i < intervals.length; i++) {
sorted[i] = intervals[i];
}
sorted[intervals.length] = newInterval; // add the new interval at the end
Arrays.sort(sorted, (a, b) -> Integer.compare(a[0], b[0]));
ArrayList<int[]> res = new ArrayList<>();
int[] cur = sorted[0].clone(); // the interval being built
for (int i = 1; i < sorted.length; i++) {
if (sorted[i][0] >= cur[0] && sorted[i][0] <= cur[1]) {
cur[1] = Math.max(cur[1], sorted[i][1]); // overlaps: stretch the end
} else {
res.add(cur); // gap: cur is done
cur = sorted[i].clone();
}
}
res.add(cur);
return res.toArray(new int[0][]);
}Hold the new interval in cur. Phase 1: copy every interval that ends before cur starts. Phase 2: while an interval starts at or before cur's end, it overlaps, so stretch cur to cover it. Then save cur. Phase 3: copy the remaining intervals. The three while loops share one index i, so each picks up where the last stopped. No sort needed because the input is already sorted.
static int[][] insertBest(int[][] intervals, int[] newInterval) {
ArrayList<int[]> res = new ArrayList<>();
int[] cur = newInterval.clone(); // the interval being built
int i = 0, n = intervals.length;
while (i < n && intervals[i][1] < cur[0]) { // phase 1: entirely before cur
res.add(intervals[i]);
i++;
}
while (i < n && intervals[i][0] <= cur[1]) { // phase 2: overlaps cur
cur[0] = Math.min(cur[0], intervals[i][0]);
cur[1] = Math.max(cur[1], intervals[i][1]);
i++;
}
res.add(cur);
while (i < n) { // phase 3: entirely after cur
res.add(intervals[i]);
i++;
}
return res.toArray(new int[0][]);
}Nothing else to add. Binary search can find where the new interval goes in O(log n), but you still copy the whole list into the result, so the total stays O(n).
cur holds the interval being builtnewInterval.clone()) so stretching cur never changes the caller's arrays.sorted is one slot longer than intervals. Copy with a loop, then put the new interval in the last slot.while picks up where the last one stopped. No resetting needed.| ArrayList.add (end) | O(1) amortised |
| Arrays.sort(Object[]) | O(n log n) |
| list.toArray | O(n) |
Remember: When the input is already sorted, find the way to avoid sorting again. It's usually what the interviewer is checking.
Spot it: Any zero should zero its whole row and column, in place. The danger is zeroing as you go and then mistaking your own new zeros for original ones. So record first, apply later.
Scan a copy for zeros. Every time the copy has a zero, wipe that row and column in the original. Because you read from the copy, newly created zeros can't cause chain reactions.
static void setZeroesBrute(int[][] m) {
int rows = m.length, cols = m[0].length;
int[][] copy = new int[rows][];
for (int i = 0; i < rows; i++) copy[i] = m[i].clone(); // deep copy, row by row
for (int i = 0; i < rows; i++)
for (int j = 0; j < cols; j++)
if (copy[i][j] == 0) {
for (int c = 0; c < cols; c++) m[i][c] = 0;
for (int r = 0; r < rows; r++) m[r][j] = 0;
}
}Pass 1: note which rows and columns contain a zero in two boolean arrays. Pass 2: zero any cell whose row or column is flagged.
static void setZeroesBetter(int[][] m) {
int rows = m.length, cols = m[0].length;
boolean[] zeroRow = new boolean[rows], zeroCol = new boolean[cols];
for (int i = 0; i < rows; i++)
for (int j = 0; j < cols; j++)
if (m[i][j] == 0) { zeroRow[i] = true; zeroCol[j] = true; }
for (int i = 0; i < rows; i++)
for (int j = 0; j < cols; j++)
if (zeroRow[i] || zeroCol[j]) m[i][j] = 0;
}The matrix's own first row and first column can store the flags, so no extra arrays. But those first-row and first-column cells may themselves hold original zeros, so remember that in two booleans before you start. Process the inner cells, then finally handle the first row and column.
static void setZeroesBest(int[][] m) {
int rows = m.length, cols = m[0].length;
boolean firstRowZero = false, firstColZero = false;
for (int j = 0; j < cols; j++) if (m[0][j] == 0) firstRowZero = true;
for (int i = 0; i < rows; i++) if (m[i][0] == 0) firstColZero = true;
for (int i = 1; i < rows; i++) // mark flags in row 0 / col 0
for (int j = 1; j < cols; j++)
if (m[i][j] == 0) { m[i][0] = 0; m[0][j] = 0; }
for (int i = 1; i < rows; i++) // apply to the inner cells
for (int j = 1; j < cols; j++)
if (m[i][0] == 0 || m[0][j] == 0) m[i][j] = 0;
if (firstRowZero) for (int j = 0; j < cols; j++) m[0][j] = 0;
if (firstColZero) for (int i = 0; i < rows; i++) m[i][0] = 0;
}When you find a zero, don't write 0 into its row and column yet. Write a special marker (here Integer.MIN_VALUE) into every non-zero cell of that row and column. A final pass turns every marker into 0. Markers can't be mistaken for original zeros.
When it fits: O(1) extra space, but it only works if the marker value never appears in the input, and it re-walks rows and columns, so it is slower: O(m·n·(m+n)).
static void setZeroesSentinel(int[][] m) {
int rows = m.length, cols = m[0].length;
final int MARK = Integer.MIN_VALUE; // assumes this never appears in the input
for (int i = 0; i < rows; i++)
for (int j = 0; j < cols; j++)
if (m[i][j] == 0) { // only ORIGINAL zeros match, markers aren't 0
for (int c = 0; c < cols; c++) if (m[i][c] != 0) m[i][c] = MARK;
for (int r = 0; r < rows; r++) if (m[r][j] != 0) m[r][j] = MARK;
}
for (int i = 0; i < rows; i++)
for (int j = 0; j < cols; j++)
if (m[i][j] == MARK) m[i][j] = 0;
}m.length is the number of rows, m[0].length is the number of columns. Rows can even have different lengths (jagged).clone() on int[][] is shallowcopy[0][0] also changes m[0][0]. Clone every row to get a true copy.new int[rows][]null until you assign it.boolean[] starts all false| 2D array access m[i][j] | O(1) |
| array.clone() (one row) | O(cols) |
| boolean[] flags | O(1) access |
Remember: When in-place edits would corrupt your reading, store the plan somewhere first. The cheapest 'somewhere' is often a spare row or column.
Spot it: Walk the matrix in spiral order. Either walk and turn right whenever you hit the edge or a visited cell, or shrink four boundaries (top, bottom, left, right) after finishing each side.
Two tiers: the visited-grid simulation and the boundary shrink. Both are O(m·n) time; the best one saves the extra grid.
Keep a direction (right, down, left, up). Move one step; if the next cell is off the grid or already visited, turn clockwise first. Mark each cell visited as you collect it.
static List<Integer> spiralOrderBrute(int[][] m) {
int rows = m.length, cols = m[0].length;
boolean[][] seen = new boolean[rows][cols];
int[] dr = {0, 1, 0, -1}, dc = {1, 0, -1, 0}; // right, down, left, up
List<Integer> res = new ArrayList<>();
int r = 0, c = 0, d = 0;
for (int step = 0; step < rows * cols; step++) {
res.add(m[r][c]);
seen[r][c] = true;
int nr = r + dr[d], nc = c + dc[d];
if (nr < 0 || nr >= rows || nc < 0 || nc >= cols || seen[nr][nc]) {
d = (d + 1) % 4; // turn clockwise
nr = r + dr[d];
nc = c + dc[d];
}
r = nr;
c = nc;
}
return res;
}Walk the top row left to right, then shrink top. Walk the right column down, shrink right. Walk the bottom row right to left, shrink bottom. Walk the left column up, shrink left. The two if guards stop you re-walking a row or column when only one is left.
static List<Integer> spiralOrderBest(int[][] m) {
List<Integer> res = new ArrayList<>();
int top = 0, bottom = m.length - 1, left = 0, right = m[0].length - 1;
while (top <= bottom && left <= right) {
for (int j = left; j <= right; j++) res.add(m[top][j]);
top++;
for (int i = top; i <= bottom; i++) res.add(m[i][right]);
right--;
if (top <= bottom) {
for (int j = right; j >= left; j--) res.add(m[bottom][j]);
bottom--;
}
if (left <= right) {
for (int i = bottom; i >= top; i--) res.add(m[i][left]);
left++;
}
}
return res;
}Walk right cols steps, then down rows-1 steps, then left cols-1 steps, then up rows-2 steps, and so on. After each side, the number of steps for that axis drops by one. Stop when a side has zero steps left. No visited grid and no boundary variables, just two counters.
When it fits: A neat alternative; less common but short and easy to dry-run on paper.
static List<Integer> spiralOrderRunLengths(int[][] m) {
int rows = m.length, cols = m[0].length;
List<Integer> res = new ArrayList<>();
int[] dr = {0, 1, 0, -1}, dc = {1, 0, -1, 0}; // right, down, left, up
int[] steps = {cols, rows - 1}; // [horizontal steps, vertical steps]
int r = 0, c = -1, d = 0; // start just left of the first cell
while (steps[d % 2] > 0) {
for (int i = 0; i < steps[d % 2]; i++) {
r += dr[d];
c += dc[d];
res.add(m[r][c]);
}
steps[d % 2]--;
d = (d + 1) % 4;
}
return res;
}dr and dc{0,1,0,-1} and {1,0,-1,0} give row/column deltas for right, down, left, up. d = (d + 1) % 4 rotates clockwise. Reuse in grid DFS/BFS (Number of Islands, Rotting Oranges).int[] dr = {0, 1, 0, -1};List<Integer>.add(int) autoboxesint is wrapped in an Integer for you. Costs a little memory versus int[], which is why LeetCode lists are slower.if (top <= bottom) guards| ArrayList.add (end) | O(1) amortised |
| boolean[][] access | O(1) |
| 2D array access | O(1) |
Remember: Four boundaries beats a visited grid. Check boundary crossing after each side, not just in the while condition.
Spot it: Rotate an n×n matrix 90° clockwise in place. Element (i, j) moves to (j, n-1-i). Either do the four-way cycle ring by ring, or notice that rotation = transpose + reverse each row.
Better and best have the same big-O. The best one wins on simplicity: fewer index formulas to get wrong under interview pressure.
Cell (i, j) goes to (j, n-1-i) in a fresh matrix. Then copy it back. Uses n² extra memory, which the problem tells you not to.
static void rotateImageBrute(int[][] m) {
int n = m.length;
int[][] res = new int[n][n];
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
res[j][n - 1 - i] = m[i][j];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
m[i][j] = res[i][j]; // copy back into the original matrix
}
}
}For each ring from the outside in, and each position along its top edge, rotate four cells at once: left → top → right → bottom → left. Saves the top value in a temp first.
static void rotateImageBetter(int[][] m) {
int n = m.length;
for (int layer = 0; layer < n / 2; layer++) {
int first = layer, last = n - 1 - layer;
for (int i = first; i < last; i++) {
int offset = i - first;
int top = m[first][i];
m[first][i] = m[last - offset][first]; // left -> top
m[last - offset][first] = m[last][last - offset]; // bottom -> left
m[last][last - offset] = m[i][last]; // right -> bottom
m[i][last] = top; // top -> right
}
}
}Transpose swaps m[i][j] with m[j][i] (reflect over the main diagonal). Reversing every row then finishes the 90° clockwise turn. Only the upper triangle is swapped (j starts at i+1), otherwise you'd swap everything back.
static void rotateImageBest(int[][] m) {
int n = m.length;
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++) {
int t = m[i][j];
m[i][j] = m[j][i];
m[j][i] = t;
}
for (int[] row : m) reverse(row, 0, n - 1);
}Another way to compose 90° clockwise out of two simple moves: first swap the row order (row 0 with row n-1, and so on), then transpose. Compare with the best version, which transposes first and then reverses every row.
When it fits: Same cost. Swapping row references is cheap because it only swaps the pointers, not the values.
static void rotateImageFlipTranspose(int[][] m) {
int n = m.length;
for (int i = 0; i < n / 2; i++) { // flip top-to-bottom (swap row references)
int[] t = m[i];
m[i] = m[n - 1 - i];
m[n - 1 - i] = t;
}
for (int i = 0; i < n; i++) // transpose
for (int j = i + 1; j < n; j++) {
int t = m[i][j];
m[i][j] = m[j][i];
m[j][i] = t;
}
}for (int[] row : m)int[] reference. Changing row contents changes m because it's the same object.res into the existing m. Assigning m[i] = res[i] would replace the row object instead of changing the values.j = i + 1 in the transpose| 2D array access | O(1) |
| Copy matrix back (double loop) | O(n²) |
| reverse(row, 0, n-1) | O(n) |
Remember: Complex index maths usually has a cleaner composition of simple moves. Transpose + reverse is one for rotation.
| Seen-map: check, then insert | Two Sum, Contains Duplicate, Longest Consecutive Sequence (as a set) |
| Signature + HashMap | Group Anagrams, Top K Frequent (count map), Valid Anagram (count array) |
| Prefix sums (+ map when counting or finding longest) | Find Pivot Index, Subarray Sum Equals K, Contiguous Array, Product of Array Except Self |
| One running best variable | Maximum Subarray (Kadane), Best Time to Buy and Sell Stock |
| Pointers that partition in place | Sort Colors |
| Reverse / transpose tricks | Rotate Array, Next Permutation, Rotate Image |
| Sort first, then sweep once | Merge Intervals (and Insert Interval, which skips the sort because the input is already sorted) |
| Record first, apply later | Set Matrix Zeroes; Spiral Matrix (boundaries) |