Coding Drills · 01

Arrays & Hashing

Twelve drills that teach the single most useful trade in interview coding: spend O(n) memory on a hash map, set, or counting array so that every "have I seen this before?" question costs O(1) instead of a nested loop. Each drill has the reasoning, a traced diagram, a compilable Java solution, and the bugs people actually write.

Drills

Easy

Medium

Hard

01 Arrays & Hashing · 02 Two Pointers · 03 Strings & Sliding Window · 04 Binary Search & Intervals · 05 Linked Lists · 06 Binary Trees & BST · 07 Grids & Matrices · 08 Graphs · 09 Dynamic Programming · 10 Backtracking & Design

Chapter One · Core Idea

Trade Memory for Lookups

An array gives you O(1) access by position. A hash table gives you O(1) access by value: it turns a key into an array index with a hash function, so "is 7 in here?" or "how many times have I seen 'a'?" no longer needs a scan. Almost every drill on this page is a nested-loop brute force (O(n²)) that collapses to a single pass (O(n)) the moment you remember the right fact about the elements you already walked past.

Java gives you three tools for this. HashSet<Integer> answers membership ("seen it?"). HashMap<K,V> remembers something about each value — its index, its count, its group. And when keys are tiny and dense (lowercase letters, digits), a plain int[26] is a perfect hash table with no hashing, no boxing, and guaranteed O(1).

Java HashMap with 8 buckets — Integer.hashCode(k) = k, index = hash & (8 − 1)

Analogy: A hash map is a cloakroom. You hand over your coat (the value), receive ticket number hash(coat) & 7, and later the attendant walks straight to hook 7 instead of searching every hook. Two coats on the same hook (a collision) just means checking two coats on that hook — still nowhere near checking all of them.

What "O(1)" really means here:

Average-case O(1) for get, put, contains; Java 8+ turns long bucket chains into balanced trees, so the worst case is O(log n), not O(n).
Boxing matters: HashMap<Integer,Integer> allocates objects. When keys are bounded (letters, small ints) an int[] is 5–10× faster.
Never rely on HashMap / HashSet iteration order — it depends on hash codes and capacity, not insertion order. Use LinkedHashMap if order matters.

Chapter Two · Mental Model

How to Think About These Problems

The brute force compares every element with every other element (two nested loops)

▶

Ask: what does the inner loop actually look for? Usually one specific value (a complement, a duplicate) — that is a hash lookup, not a loop

You walk the array left to right and remember what you passed

▶

Everything to the left of index i is "history". Store just enough of it (a set, an index map, a count) to answer the question at i in O(1)

The question is about multisets: "same letters?", "same counts?"

▶

Count frequencies. Two strings are anagrams exactly when their 26-slot count arrays are equal — order disappears

The question is about a contiguous range: sum, product, "everything except me"

▶

Precompute running totals. sum(i..j) = P[j+1] − P[i]; a range question becomes a difference of two prefixes

Prefix differences need a partner prefix

▶

Combine both ideas: store each prefix sum in a hash map and look up P − k — subarray counting in one pass

The answer is a single number and you must use O(1) extra space

▶

Keep a running state that folds each element in: min-so-far, a vote counter, an XOR accumulator

Before writing code, classify the question. The diagram below is the order in which to ask — the first "yes" usually names the template from Chapter 03.

Chapter Three · Pattern Toolkit

Four Reusable Templates

Learn these four shapes and the twelve drills become variations. Each template is a single left-to-right pass; what changes is what you remember about the prefix you already walked.

Template A — Complement Lookup

"Does some earlier element complete the current one?" Store earlier elements (or their indices) in a set/map; ask for the complement before inserting yourself.

Pseudocode

function findPair(nums, target):
  seen = empty map              // value -> index
  for i in 0 .. n-1:
      need = target - nums[i]
      if need in seen:
          return (seen[need], i)
      seen[nums[i]] = i         // insert AFTER the lookup
  return none
  

Template A — complement lookup on [5, 3, 8, 2], target = 10

Template B — Frequency Counting

"Same contents regardless of order?" Count how many of each value appear. Use int[26] for lowercase letters, HashMap for anything else.

Pseudocode

function counts(s):
  count = int[26]               // all zeros
  for each c in s:
      count[c - 'a'] += 1
  return count                  // compare / scan / use as a key
  

Template B — frequency count of "banana"

Template C — Prefix Accumulation

"Something about a contiguous range?" Precompute running totals so any range is one subtraction. Add a hash map of earlier prefixes to count ranges with a given sum.

Pseudocode

function prefix(nums):
  P = int[n + 1]                // P[0] = 0
  for i in 0 .. n-1:
      P[i + 1] = P[i] + nums[i]
  return P                      // sum(i..j) = P[j+1] - P[i]
  

Template C — prefix sums: a range is the difference of two prefixes

Template D — Running State (O(1) Space)

"One answer, no extra memory." Fold each element into a constant-size state. The art is choosing the state: min-so-far, a vote, an XOR.

Pseudocode

function fold(nums):
  state = initial
  for each x in nums:
      state = combine(state, x)   // O(1) work
  return answer(state)
  

Template D — running state on [4, 2, 9, 1, 7]: largest x[j] − x[i] with i < j

Drill 01 · Complement Lookup

Two Sum

Drill 01 · Two Sum

Easy complement map LeetCode #1 ↗ Full write-up →

Given an integer array nums and an integer target, return the indices of the two numbers that add up to target. Exactly one answer exists and you may not use the same element twice.

Example

Input:  nums = [2, 7, 11, 15], target = 9
Output: [0, 1]            // nums[0] + nums[1] = 2 + 7 = 9
  

💡 Key insight: For each number x you are not looking for "any pair" — you are looking for exactly one value, target − x. A specific-value search over earlier elements is a hash lookup.

Brute force → optimal. Checking every pair (i, j) is O(n²). Sorting + two pointers is O(n log n) but loses the original indices unless you sort index pairs. A single pass with a HashMap<value, index> does it in O(n): at index i, every earlier element is already in the map, so if a partner exists to the left you find it immediately; if the partner is to the right, it will find you when its turn comes.

Trace — nums = [4, 1, 6, 9, 3], target = 12

Java — one-pass HashMap

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class TwoSum {
  // One pass: before storing nums[i], ask "have I already seen target - nums[i]?"
  public static int[] twoSum(int[] nums, int target) {
      Map<Integer, Integer> seen = new HashMap<>(); // value -> index
      for (int i = 0; i < nums.length; i++) {
          int complement = target - nums[i];
          Integer j = seen.get(complement);
          if (j != null) return new int[]{j, i};
          seen.put(nums[i], i);              // store AFTER the lookup
      }
      throw new IllegalArgumentException("no two numbers sum to " + target);
  }

  public static void main(String[] args) {
      int[] nums = {2, 7, 11, 15};
      System.out.println(Arrays.toString(twoSum(nums, 9)));            // [0, 1]
      System.out.println(Arrays.toString(twoSum(new int[]{4, 1, 6, 9, 3}, 12))); // [3, 4]
  }
}
  

Complexity

Approach	Time	Space	Notes
Nested loops	O(n²)	O(1)	Every pair
Sort + two pointers	O(n log n)	O(n)	Must carry original indices
One-pass HashMap ← optimal	O(n)	O(n)	One lookup + one insert per element

⚠ Common bugs & edge cases:

Inserting nums[i] before looking up its complement: with target 12 and a single 6, the code returns [2, 2] — using one element twice.
Duplicates such as [3, 3], target 6, still work with lookup-then-insert: index 1 finds index 0. Overwriting the map entry for repeated values is harmless.
Returning values instead of indices, or 1-based indices (that is Two Sum II, Drill 18).
Returning an empty array when nothing is found hides bugs; the problem guarantees an answer, so throwing is clearer.

Drills 02–03 · Hash Set & Counting

Contains Duplicate · Valid Anagram

Drill 02 · Contains Duplicate

Easy hash set LeetCode #217 ↗ Full write-up →

Given an integer array nums, return true if any value appears at least twice, and false if every element is distinct.

Example

Input:  nums = [1, 2, 3, 1]
Output: true              // 1 appears at index 0 and index 3
Input:  nums = [1, 2, 3, 4]
Output: false
  

💡 Key insight: Set.add() already tells you the answer: it returns false when the element was present. The membership test and the insert are one call.

Brute force → optimal. Comparing all pairs is O(n²). Sorting and checking neighbours is O(n log n) time and O(1) extra space (if you may mutate the input) — a fine answer when memory is tight. A HashSet gives O(n) time and stops at the first repeat.

Step	num	set before	add() returns	Action
1	1	{ }	true	continue
2	2	{1}	true	continue
3	3	{1, 2}	true	continue
4	1	{1, 2, 3}	false	return true

Java — HashSet early exit

import java.util.HashSet;
import java.util.Set;

public class ContainsDuplicate {
  public static boolean containsDuplicate(int[] nums) {
      Set<Integer> seen = new HashSet<>(nums.length * 2);
      for (int num : nums) {
          if (!seen.add(num)) return true; // add() returns false if already present
      }
      return false;
  }

  public static void main(String[] args) {
      System.out.println(containsDuplicate(new int[]{1, 2, 3, 1})); // true
      System.out.println(containsDuplicate(new int[]{1, 2, 3, 4})); // false
  }
}
  

Complexity

Approach	Time	Space	Notes
Nested loops	O(n²)	O(1)
Sort + scan neighbours	O(n log n)	O(1)*	*mutates input; Arrays.sort on int[] is in-place
HashSet ← optimal	O(n)	O(n)	Stops at first duplicate

⚠ Common bugs & edge cases:

Writing if (set.contains(x)) return true; set.add(x); works, but hashes twice — add()'s boolean does both.
Comparing boxed Integer with == instead of equals (only safe in the cache range −128..127) — another reason to let the set compare.
Pre-size the set (new HashSet<>(2 * n)) for large inputs to avoid repeated rehashing.

Drill 03 · Valid Anagram

Easy frequency count LeetCode #242 ↗ Full write-up →

Given two strings s and t of lowercase English letters, return true if t is an anagram of s — the same letters with the same multiplicities, in any order.

Example

Input:  s = "anagram", t = "nagaram"
Output: true
Input:  s = "rat", t = "car"
Output: false
  

💡 Key insight: An anagram is a permutation, and permutations preserve counts. So compare the counts, not the strings. One array is enough: let s increment and t decrement — equal multisets cancel to all zeros.

Brute force → optimal. Sorting both strings and comparing is O(n log n) and simple. Counting is O(n) with a fixed 26-slot array — O(1) extra space because the alphabet does not grow with n. A length check first rejects most non-anagrams for free.

Single count array: +1 for every char of s, −1 for every char of t (only non-empty slots shown)

Java — one int[26], add and subtract

public class ValidAnagram {
  // Assumes lowercase English letters (LeetCode constraint).
  public static boolean isAnagram(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']++;   // s adds
          count[t.charAt(i) - 'a']--;   // t removes
      }
      for (int c : count) {
          if (c != 0) return false;
      }
      return true;
  }

  public static void main(String[] args) {
      System.out.println(isAnagram("anagram", "nagaram")); // true
      System.out.println(isAnagram("rat", "car"));         // false
  }
}
  

Complexity

Approach	Time	Space	Notes
Sort both, compare	O(n log n)	O(n)	toCharArray copies
int[26] counts ← optimal	O(n)	O(1)	26 slots regardless of n

⚠ Common bugs & edge cases:

Skipping the length check: then "ab" vs "a" throws StringIndexOutOfBoundsException in the shared loop.
c - 'a' assumes lowercase ASCII. For Unicode input use HashMap<Integer,Integer> over s.codePoints().
Comparing Arrays.sorted char arrays with == (reference equality) instead of Arrays.equals.

Drills 04–05 · Count & Membership

First Unique Character · Intersection

Drill 04 · First Unique Character in a String

Easy frequency count LeetCode #387 ↗

Given a string s of lowercase letters, return the index of the first character that occurs exactly once. If there is none, return -1.

Example

Input:  s = "leetcode"      Output: 0
Input:  s = "loveleetcode"  Output: 2   // 'v'
Input:  s = "aabb"          Output: -1
  

💡 Key insight: "Unique" is a property of the whole string — you cannot know at index 0 whether 'l' repeats later. So split the work: pass 1 learns the counts, pass 2 uses them in the original order.

Brute force → optimal. For each index, scan the rest for a repeat: O(n²). Two passes with an int[26] are O(n). A LinkedHashMap also works (it remembers insertion order) but is slower and allocates.

Two passes over "loveleetcode"

Java — count, then scan in order

public class FirstUniqueChar {
  // Assumes lowercase English letters (LeetCode constraint).
  public static int firstUniqChar(String s) {
      int[] count = new int[26];
      for (int i = 0; i < s.length(); i++) count[s.charAt(i) - 'a']++;  // pass 1: count
      for (int i = 0; i < s.length(); i++) {                             // pass 2: first with count 1
          if (count[s.charAt(i) - 'a'] == 1) return i;
      }
      return -1;
  }

  public static void main(String[] args) {
      System.out.println(firstUniqChar("leetcode"));     // 0
      System.out.println(firstUniqChar("loveleetcode")); // 2
      System.out.println(firstUniqChar("aabb"));         // -1
  }
}
  

Complexity

Approach	Time	Space	Notes
Check each char against all others	O(n²)	O(1)
Two passes, int[26] ← optimal	O(n)	O(1)	26 counters

⚠ Common bugs & edge cases:

Scanning the count array in alphabet order in pass 2 — that returns the alphabetically first unique letter, not the first by position.
Returning the character instead of its index.
Empty string: both loops skip and -1 is returned — correct, but test it.

Drill 05 · Intersection of Two Arrays

Easy hash set LeetCode #349 ↗

Given two integer arrays, return their intersection: every value that appears in both, each value listed once, in any order.

Example

Input:  nums1 = [1, 2, 2, 1], nums2 = [2, 2]
Output: [2]
Input:  nums1 = [4, 9, 5], nums2 = [9, 4, 9, 8, 4]
Output: [9, 4]            // any order
  

💡 Key insight: Two sets, two jobs: the first answers "is this value in nums1?", the second de-duplicates the answer. A value that appears three times in nums2 is still reported once.

Brute force → optimal. Nested loops plus a "already added?" check is O(n·m). Sorting both and walking with two pointers is O((n + m) log) and O(1) extra — handy if the inputs are already sorted. Hash sets give O(n + m).

nums2[j]	in set(nums1) = {4, 9, 5}?	result set after
9	yes	{9}
4	yes	{9, 4}
9	yes (already in result)	{9, 4}
8	no	{9, 4}
4	yes (already in result)	{9, 4}

Java — two HashSets

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

public class IntersectionArrays {
  public static int[] intersection(int[] nums1, int[] nums2) {
      Set<Integer> inFirst = new HashSet<>();
      for (int num : nums1) inFirst.add(num);
      Set<Integer> common = new HashSet<>();
      for (int num : nums2) {
          if (inFirst.contains(num)) common.add(num); // set dedupes the result
      }
      int[] out = new int[common.size()];
      int i = 0;
      for (int num : common) out[i++] = num;
      return out;
  }

  public static void main(String[] args) {
      System.out.println(Arrays.toString(intersection(new int[]{1, 2, 2, 1}, new int[]{2, 2})));       // [2]
      int[] r = intersection(new int[]{4, 9, 5}, new int[]{9, 4, 9, 8, 4});
      Arrays.sort(r);                         // HashSet order is unspecified
      System.out.println(Arrays.toString(r)); // [4, 9]
  }
}
  

Complexity

Approach	Time	Space	Notes
Nested loops + contains check	O(n·m)	O(k)
Sort both + two pointers	O(n log n + m log m)	O(1)	extra beyond output
Two HashSets ← optimal	O(n + m)	O(n)

⚠ Common bugs & edge cases:

Using a List for the result: duplicates in nums2 (the two 4s) appear twice.
Printing HashSet contents and asserting a specific order in tests — iteration order is unspecified; sort before comparing.
Confusing this with Intersection II (LC 350), which keeps multiplicities — that one needs a count map, not a set.

Drill 06 · Canonical Keys

Group Anagrams

Drill 06 · Group Anagrams

Medium canonical key LeetCode #49 ↗ Full write-up →

Given an array of lowercase strings, group the anagrams together. Return the groups in any order.

Example

Input:  strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
Output: [["bat"], ["tan", "nat"], ["eat", "tea", "ate"]]   // any group order
  

💡 Key insight: Anagrams are "equal up to order". Map every word to a canonical form that forgets order — its sorted letters or its 26 counts — and anagrams collide on purpose in a HashMap<key, List>.

Brute force → optimal. Comparing every pair of words with Valid Anagram is O(n²·k). Sorting each word as the key gives O(n·k log k). Building a count-signature key is O(n·k) — linear in the total input size. Both are accepted; the sorted key is shorter to write in an interview.

Group anagrams — one key per multiset of letters

Java — count-signature key

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class GroupAnagrams {
  public static List<List<String>> groupAnagrams(String[] strs) {
      Map<String, List<String>> groups = new HashMap<>();
      for (String s : strs) {
          int[] count = new int[26];
          for (char c : s.toCharArray()) count[c - 'a']++;
          StringBuilder key = new StringBuilder();
          for (int n : count) key.append('#').append(n); // "#1#0#0#0#1..." - unambiguous
          groups.computeIfAbsent(key.toString(), k -> new ArrayList<>()).add(s);
      }
      return new ArrayList<>(groups.values());
  }

  public static void main(String[] args) {
      String[] strs = {"eat", "tea", "tan", "ate", "nat", "bat"};
      // Group order depends on HashMap iteration; words inside a group keep input order.
      System.out.println(groupAnagrams(strs)); // [[bat], [tan, nat], [eat, tea, ate]] (group order may vary)
  }
}
  

Alternative key — sorted letters (O(k log k) per word)

char[] chars = s.toCharArray();
Arrays.sort(chars);
String key = new String(chars);      // "eat", "tea", "ate" -> "aet"
  

Complexity

Approach	Time	Space	Notes
Pairwise isAnagram	O(n²·k)	O(n·k)
Sorted-string key	O(n·k log k)	O(n·k)	simplest to write
Count-signature key ← optimal	O(n·k)	O(n·k)	k = max word length

⚠ Common bugs & edge cases:

Concatenating counts without a separator: counts (1, 11) and (11, 1) both become "111". The # delimiter makes the key unambiguous.
Using chars.toString() as the key — that is the array's identity hash ([C@1b6d3586), never equal for two arrays. Use new String(chars).
Expecting the output in input order: HashMap.values() order is arbitrary. Use LinkedHashMap if a stable order is required.
Empty string "" is a valid word; it gets the all-zero key and forms its own group.

Drill 07 · Prefix & Suffix

Product of Array Except Self

Drill 07 · Product of Array Except Self

Medium prefix / suffix LeetCode #238 ↗ Full write-up →

Given nums, return answer where answer[i] is the product of every element except nums[i]. Do it in O(n) without the division operator.

Example

Input:  nums = [1, 2, 3, 4]
Output: [24, 12, 8, 6]
Input:  nums = [-1, 1, 0, -3, 3]
Output: [0, 0, 9, 0, 0]
  

💡 Key insight: "Everything except me" = "everything to my left" × "everything to my right". Both are prefix products — one computed forwards, one backwards.

Brute force → optimal. Multiplying all others for each i is O(n²). "Total product ÷ nums[i]" is O(n) but forbidden — and breaks on zeros. Two prefix-product passes are O(n); writing the left products directly into the output array and folding the right products in with a single variable makes the extra space O(1) (the output array does not count).

Product except self for [1, 2, 3, 4]

Java — left pass into output, right pass with one variable

import java.util.Arrays;

public class ProductExceptSelf {
  public static int[] productExceptSelf(int[] nums) {
      int n = nums.length;
      int[] answer = new int[n];
      answer[0] = 1;
      for (int i = 1; i < n; i++) {          // answer[i] = product of everything LEFT of i
          answer[i] = answer[i - 1] * nums[i - 1];
      }
      int right = 1;                         // running product of everything RIGHT of i
      for (int i = n - 1; i >= 0; i--) {
          answer[i] *= right;
          right *= nums[i];
      }
      return answer;
  }

  public static void main(String[] args) {
      System.out.println(Arrays.toString(productExceptSelf(new int[]{1, 2, 3, 4})));       // [24, 12, 8, 6]
      System.out.println(Arrays.toString(productExceptSelf(new int[]{-1, 1, 0, -3, 3}))); // [0, 0, 9, 0, 0]
  }
}
  

Complexity

Approach	Time	Space	Notes
Nested loops	O(n²)	O(1)
Separate left[] and right[] arrays	O(n)	O(n)	clearest first version
Output array + running right product ← optimal	O(n)	O(1) extra	output not counted

⚠ Common bugs & edge cases:

Using division: fails with a zero (divide by zero) and is disallowed by the problem anyway.
Updating right *= nums[i] before answer[i] *= right — then answer[i] includes nums[i] itself.
Overflow: the problem guarantees products fit in 32 bits; in general code use long.
Single element [5]: the empty product is 1, so the answer is [1].

Drill 08 · Prefix Sum + Hash Map

Subarray Sum Equals K

Drill 08 · Subarray Sum Equals K

Medium prefix sum + map LeetCode #560 ↗

Given an integer array nums (values may be negative) and an integer k, return the number of non-empty contiguous subarrays whose sum equals k.

Example

Input:  nums = [1, 1, 1], k = 2       Output: 2
Input:  nums = [1, 2, 3], k = 3       Output: 2     // [1,2] and [3]
Input:  nums = [3, 4, 7, -2, 2], k = 7  Output: 3   // [3,4] [7] [7,-2,2]
  

💡 Key insight: A subarray ending at j sums to k exactly when some earlier prefix equals P[j+1] − k. So it is Two Sum on prefix sums: "how many earlier prefixes are my complement?"

Brute force → optimal. All O(n²) subarrays with a running sum is O(n²). Sliding window does not work: with negative numbers, growing the window can shrink the sum, so there is no monotonic rule for moving the left edge. A hash map from prefix sum → how many times seen gives O(n).

Prefix sum + hash map on [1, 2, 3], k = 3

Java — prefix sums counted in a HashMap

import java.util.HashMap;
import java.util.Map;

public class SubarraySumK {
  public static int subarraySum(int[] nums, int k) {
      Map<Integer, Integer> prefixCount = new HashMap<>();
      prefixCount.put(0, 1);                 // empty prefix: lets a subarray start at index 0
      int sum = 0, count = 0;
      for (int num : nums) {
          sum += num;
          count += prefixCount.getOrDefault(sum - k, 0);   // look up BEFORE inserting
          prefixCount.merge(sum, 1, Integer::sum);
      }
      return count;
  }

  public static void main(String[] args) {
      System.out.println(subarraySum(new int[]{1, 1, 1}, 2));        // 2
      System.out.println(subarraySum(new int[]{1, 2, 3}, 3));        // 2
      System.out.println(subarraySum(new int[]{3, 4, 7, -2, 2}, 7)); // 3
  }
}
  

Complexity

Approach	Time	Space	Notes
All subarrays (running sum)	O(n²)	O(1)
Prefix sum + HashMap ← optimal	O(n)	O(n)	counts, not just presence

⚠ Common bugs & edge cases:

Forgetting map.put(0, 1): subarrays that start at index 0 (like [1, 2] above) are never counted.
Inserting the current prefix before the lookup: with k = 0 every position falsely matches itself.
Storing booleans/a set instead of counts — several earlier prefixes can share the same value (zeros, negatives) and each one is a different subarray.
Reaching for sliding window: correct only when all numbers are positive.

Drills 09–10 · Running State

Majority Element · Single Number

Drill 09 · Majority Element

Easy boyer-moore vote LeetCode #169 ↗

Given an array of size n, return the element that appears more than ⌊n / 2⌋ times. The majority element is guaranteed to exist.

Example

Input:  nums = [3, 2, 3]                Output: 3
Input:  nums = [2, 2, 1, 1, 1, 2, 2]    Output: 2
  

💡 Key insight: Pair every majority vote against a different value and cancel both. Because the majority has more than half the votes, it cannot be fully cancelled — whatever survives is the majority.

Brute force → optimal. Counting each value with a nested loop is O(n²). A HashMap count is O(n) time and O(n) space. Sorting and returning nums[n/2] is O(n log n). Boyer–Moore voting keeps two integers: O(n) time, O(1) space.

i	x	candidate	count	why
0	2	2	1	count was 0 → new candidate 2
1	2	2	2	vote for
2	1	2	1	cancel one vote
3	1	2	0	cancel one vote
4	1	1	1	count was 0 → new candidate 1
5	2	1	0	cancel one vote
6	2	2	1	count was 0 → new candidate 2

Java — Boyer–Moore voting

public class MajorityElement {
  // Boyer-Moore voting. Valid only because a majority (> n/2) is guaranteed.
  public static int majorityElement(int[] nums) {
      int candidate = 0, count = 0;
      for (int num : nums) {
          if (count == 0) candidate = num;
          count += (num == candidate) ? 1 : -1;
      }
      return candidate;
  }

  public static void main(String[] args) {
      System.out.println(majorityElement(new int[]{3, 2, 3}));             // 3
      System.out.println(majorityElement(new int[]{2, 2, 1, 1, 1, 2, 2})); // 2
  }
}
  

Complexity

Approach	Time	Space	Notes
Count each with nested loop	O(n²)	O(1)
HashMap counts	O(n)	O(n)
Sort, take middle	O(n log n)	O(1)	mutates input
Boyer–Moore ← optimal	O(n)	O(1)	needs the majority guarantee

⚠ Common bugs & edge cases:

Using Boyer–Moore when a majority is not guaranteed: the survivor is only a candidate; you must re-count it in a second pass.
Resetting the candidate when count hits zero but forgetting to count the current element for it — the check must happen before the vote, as in the code.
Confusing ">n/2" (majority) with "most frequent": [1,1,2,2,3] has no majority and the vote returns 3.

Drill 10 · Single Number

Easy xor fold LeetCode #136 ↗ Full write-up →

Every element of a non-empty integer array appears exactly twice except one. Find that single element in O(n) time and O(1) extra space.

Example

Input:  nums = [4, 1, 2, 1, 2]
Output: 4
  

💡 Key insight: XOR is a light switch per bit: flipping a switch twice leaves it where it started. Every paired number flips its bits twice; only the single number's bits stay flipped.

Brute force → optimal. A HashSet that adds and removes (or a count map) is O(n) time but O(n) space. 2·sum(set) − sum(nums) is cute but also O(n) space and can overflow. XOR-ing everything is O(n) time and one int of space.

XOR fold of [4, 1, 2, 1, 2]

Java — XOR everything

public class SingleNumber {
  public static int singleNumber(int[] nums) {
      int result = 0;
      for (int num : nums) result ^= num;   // a ^ a = 0, a ^ 0 = a
      return result;
  }

  public static void main(String[] args) {
      System.out.println(singleNumber(new int[]{4, 1, 2, 1, 2})); // 4
      System.out.println(singleNumber(new int[]{-3, 7, 7}));      // -3
  }
}
  

Complexity

Approach	Time	Space	Notes
HashSet add/remove	O(n)	O(n)
XOR fold ← optimal	O(n)	O(1)	works for negatives too (two's complement)

⚠ Common bugs & edge cases:

Starting the accumulator at nums[0] and looping from 0 — XORs the first element twice and returns the wrong answer.
Applying XOR when duplicates appear three times (LC 137) — that variant needs per-bit counting mod 3.
Thinking XOR breaks on negatives: it operates on all 32 bits, so [-3, 7, 7] returns −3.

Drills 11–12 · Greedy Running State

Best Time to Buy and Sell Stock I & II

Drill 11 · Best Time to Buy and Sell Stock

Easy min so far LeetCode #121 ↗ Full write-up →

prices[i] is a stock's price on day i. Choose one day to buy and a later day to sell to maximise profit. Return the maximum profit, or 0 if no profit is possible.

Example

Input:  prices = [7, 1, 5, 3, 6, 4]
Output: 5                 // buy on day 1 at 1, sell on day 4 at 6
Input:  prices = [7, 6, 4, 3, 1]
Output: 0                 // prices only fall: do not trade
  

💡 Key insight: If you sell today, the best buy was the cheapest day before today. So walk forward carrying one number — the minimum so far — and ask each day "what if I sold now?"

Brute force → optimal. Every (buy, sell) pair with buy < sell is O(n²). Template D collapses it: the state is (minPrice, best), updated in O(1) per day, for O(n) time and O(1) space. (Equivalently: Kadane's algorithm on the day-to-day differences.)

prices = [7, 1, 5, 3, 6, 4] — profit if sold today = price − min so far

Java — one pass, min so far

public class StockI {
  public static int maxProfit(int[] prices) {
      int minPrice = Integer.MAX_VALUE, best = 0;
      for (int price : prices) {
          if (price < minPrice) minPrice = price;          // cheapest buy so far
          else best = Math.max(best, price - minPrice);    // sell today?
      }
      return best;
  }

  public static void main(String[] args) {
      System.out.println(maxProfit(new int[]{7, 1, 5, 3, 6, 4})); // 5
      System.out.println(maxProfit(new int[]{7, 6, 4, 3, 1}));    // 0
  }
}
  

Complexity

Approach	Time	Space	Notes
All buy/sell pairs	O(n²)	O(1)
Min so far ← optimal	O(n)	O(1)	one pass

⚠ Common bugs & edge cases:

Taking max(prices) − min(prices): in [7, 1, 5, 3, 6, 4] that happens to work, but in [3, 8, 1] the max comes before the min — answer 5, not 7.
Initialising best to Integer.MIN_VALUE — a falling market must return 0, not a negative profit.
Updating minPrice and profit in the wrong order is harmless here (profit 0 on the same day), but in variants with fees it matters — be deliberate.

Drill 12 · Best Time to Buy and Sell Stock II

Medium greedy · sum of gains LeetCode #122 ↗

Same prices, but now you may complete as many transactions as you like — holding at most one share at a time (sell before you buy again). Return the maximum total profit.

Example

Input:  prices = [7, 1, 5, 3, 6, 4]
Output: 7                 // buy 1 sell 5 (+4), buy 3 sell 6 (+3)
Input:  prices = [1, 2, 3, 4, 5]
Output: 4                 // one long hold = sum of daily +1 steps
  

💡 Key insight: Any rising run from low to high equals the sum of its daily up-steps (1→2→3 is +1 +1 = +2). So you never need to plan transactions: just bank every positive day-to-day difference.

Brute force → optimal. Trying every set of non-overlapping transactions is exponential; a two-state DP (holding / not holding) is O(n) and generalises to fees and cooldowns. For the plain version the greedy sum of positive differences is O(n), O(1), and provably optimal because a long trade can always be split into consecutive daily trades with the same total.

Collect every up-step: (5 − 1) + (6 − 3) = 7

Java — sum of positive differences

public class StockII {
  public static int maxProfit(int[] prices) {
      int profit = 0;
      for (int i = 1; i < prices.length; i++) {
          int gain = prices[i] - prices[i - 1];
          if (gain > 0) profit += gain;      // collect every upward step
      }
      return profit;
  }

  public static void main(String[] args) {
      System.out.println(maxProfit(new int[]{7, 1, 5, 3, 6, 4})); // 7
      System.out.println(maxProfit(new int[]{1, 2, 3, 4, 5}));    // 4
  }
}
  

Complexity

Approach	Time	Space	Notes
Enumerate transaction sets	O(2ⁿ)	O(n)
DP hold / free	O(n)	O(1)	extends to fee / cooldown
Greedy sum of gains ← optimal	O(n)	O(1)

⚠ Common bugs & edge cases:

Reusing Drill 11's single-trade logic — it returns 5, not 7.
Trying to find explicit valley/peak pairs with nested while-loops: correct but easy to get off-by-one at the array end. The difference sum has no edge cases.
The greedy shortcut stops working once a per-transaction fee exists (LC 714) — switch to the DP.

Chapter Twelve · Review

Summary & What to Practice Next

Drill	Problem	Pattern	Time	Space	Difficulty
01	Two Sum	complement map	O(n)	O(n)	Easy
02	Contains Duplicate	hash set	O(n)	O(n)	Easy
03	Valid Anagram	frequency count	O(n)	O(1)	Easy
04	First Unique Character	frequency count	O(n)	O(1)	Easy
05	Intersection of Two Arrays	hash set	O(n + m)	O(n)	Easy
06	Group Anagrams	canonical key	O(n·k)	O(n·k)	Medium
07	Product of Array Except Self	prefix / suffix	O(n)	O(1)*	Medium
08	Subarray Sum Equals K	prefix sum + map	O(n)	O(n)	Medium
09	Majority Element	boyer-moore	O(n)	O(1)	Easy
10	Single Number	xor fold	O(n)	O(1)	Easy
11	Best Time to Buy/Sell Stock	min so far	O(n)	O(1)	Easy
12	Best Time to Buy/Sell Stock II	greedy gains	O(n)	O(1)	Medium

* O(1) extra space — the output array is not counted.

∑ Arrays & Hashing — what to remember

Inner loop searches for one value? Replace it with a HashMap / HashSet lookup (Drills 01, 02, 05).
Order does not matter? Count. int[26] for letters; a count signature doubles as a grouping key (Drills 03, 04, 06).
Contiguous range? Prefix sums/products; add a map of earlier prefixes to count ranges (Drills 07, 08).
O(1) space? Find the running state: min-so-far, a vote, an XOR (Drills 09–12).
Lookup before insert — the single most common bug on this page (Drills 01, 08).

Practice next:

Continue to Coding Drills 02 · Two Pointers — the O(1)-space alternative when the input is sorted.
Refresh the data structures: HashMap, HashSet, Array.
More problems in the same family: LeetCode · Arrays & Hashing, LeetCode · Hash Map, LeetCode · Math & Bits.
Why the stock drills are greedy: Greedy algorithms; how to state the costs: Complexity.

  ← All drills (hub)
  All 100 drills
  Two Pointers →

LearningTree

Arrays & Hashing | Java Coding Drills

Arrays & Hashing

Trade Memory for Lookups

How to Think About These Problems

Four Reusable Templates

Two Sum

Contains Duplicate · Valid Anagram

First Unique Character · Intersection

Group Anagrams

Product of Array Except Self

Subarray Sum Equals K

Majority Element · Single Number

Best Time to Buy and Sell Stock I & II

Summary & What to Practice Next