LeetCode Cheat Sheet — DSA in Java

1Brute force — try every pair

The first idea anyone has: pick each number, then check it against every number after it. If a pair adds up to the target, return their positions.

int[] twoSum(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[]{};   // problem says an answer always exists
}

Time O(n²)Space O(1)

It works, but with 10,000 numbers that's about 50 million pair checks. The interviewer will ask: "can you do better?"

2Optimal — remember what you've seen in a HashMap

int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> seen = new HashMap<>();   // number -> its index
    for (int i = 0; i < nums.length; i++) {
        int need = target - nums[i];                // the partner we are looking for
        if (seen.containsKey(need)) {
            return new int[]{seen.get(need), i};
        }
        seen.put(nums[i], i);                       // store AFTER checking
    }
    return new int[]{};
}

Time O(n)Space O(n)

We trade memory for speed: the map can hold up to n numbers, but every lookup is instant, so one pass is enough.

Pattern notes: Hashing · Open on LeetCode

1Brute force — compare every pair

Take each number and compare it with every number after it. If two are equal, we found a duplicate.

boolean containsDuplicate(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;
}

Time O(n²)Space O(1)

Correct, but LeetCode gives up to 100,000 numbers. That is about 5 billion comparisons, so it times out.

2Optimal — keep a HashSet of numbers you've seen

boolean containsDuplicate(int[] nums) {
    Set<Integer> seen = new HashSet<>();
    for (int x : nums) {
        // add() returns false if x was already in the set
        if (!seen.add(x)) return true;
    }
    return false;   // every number was new
}

Time O(n)Space O(n)

Each number is looked up and added once, and both take O(1). The set may hold all n numbers, so we pay O(n) memory to get the speed.

Pattern notes: Hashing · Open on LeetCode

1Brute force — try every buy day with every later sell day

For each buy day i, try every sell day j > i and keep the biggest difference.

int maxProfit(int[] prices) {
    int best = 0;
    for (int i = 0; i < prices.length; i++) {          // buy day
        for (int j = i + 1; j < prices.length; j++) {  // sell day, always later
            best = Math.max(best, prices[j] - prices[i]);
        }
    }
    return best;
}

Time O(n²)Space O(1)

With 100,000 days this is billions of pairs. It times out.

2Optimal — one pass, remember the cheapest day so far

int maxProfit(int[] prices) {
    int minPrice = Integer.MAX_VALUE;   // cheapest price seen so far
    int best = 0;                       // best profit so far (0 = don't trade)
    for (int p : prices) {
        if (p < minPrice) {
            minPrice = p;               // a new cheapest day to buy
        } else {
            best = Math.max(best, p - minPrice);   // sell today?
        }
    }
    return best;
}

Time O(n)Space O(1)

We never look back: the minimum so far already sums up everything the past days can offer.

Pattern notes: Arrays & Strings · Open on LeetCode

1Brute force — copy the non-zeros into a new array

Make a new array (Java fills it with zeros). Copy the non-zero numbers into it from the left, then copy everything back.

void moveZeroes(int[] nums) {
    int[] tmp = new int[nums.length];   // starts as all zeros
    int k = 0;
    for (int x : nums) {
        if (x != 0) tmp[k++] = x;       // keep non-zeros in order
    }
    for (int i = 0; i < nums.length; i++) nums[i] = tmp[i];
}

Time O(n)Space O(n)

Fast, but it uses a whole second array. The problem asks for in place, so the interviewer wants O(1) extra memory.

2Optimal — a read pointer and a write pointer

void moveZeroes(int[] nums) {
    int write = 0;                        // next slot for a non-zero
    for (int read = 0; read < nums.length; read++) {
        if (nums[read] != 0) {
            int t = nums[write];          // swap nums[read] into the write slot
            nums[write] = nums[read];
            nums[read] = t;
            write++;
        }
    }
}

Time O(n)Space O(1)

One pass and only two index variables. Because write never passes read, we never overwrite a number we still need.

Pattern notes: Two Pointers · Open on LeetCode

1Brute force — collect the unique values in a set

Put every number into a LinkedHashSet (it drops duplicates and keeps insertion order), then write the set back into the front of the array.

int removeDuplicates(int[] nums) {
    Set<Integer> set = new LinkedHashSet<>();
    for (int x : nums) set.add(x);     // duplicates are ignored
    int k = 0;
    for (int x : set) nums[k++] = x;   // write the unique values back
    return k;
}

Time O(n)Space O(n)

It works on any array, sorted or not, but it ignores the big hint (sorted) and uses extra memory the problem does not want you to use.

2Optimal — write pointer, compare with the last kept value

int removeDuplicates(int[] nums) {
    if (nums.length == 0) return 0;
    int write = 1;                                // slot 0 is always unique
    for (int read = 1; read < nums.length; read++) {
        if (nums[read] != nums[write - 1]) {      // new value?
            nums[write] = nums[read];
            write++;
        }
    }
    return write;                                 // number of unique values
}

Time O(n)Space O(1)

One pass, no extra array. Sorting did the hard work for us: duplicates are grouped, so one comparison per number is enough.

Pattern notes: Two Pointers · Open on LeetCode

1Brute force — copy the keepers into a new array

Copy every number that is not val into a temporary array, then copy those back to the front.

int removeElement(int[] nums, int val) {
    int[] tmp = new int[nums.length];
    int k = 0;
    for (int x : nums) {
        if (x != val) tmp[k++] = x;     // keep it
    }
    for (int i = 0; i < k; i++) nums[i] = tmp[i];
    return k;
}

Time O(n)Space O(n)

The extra array is not needed: we can write the keepers straight into the front of nums.

2Optimal — read pointer and write pointer

int removeElement(int[] nums, int val) {
    int write = 0;                          // next free slot for a keeper
    for (int read = 0; read < nums.length; read++) {
        if (nums[read] != val) {
            nums[write] = nums[read];       // keep it
            write++;
        }
    }
    return write;                           // how many we kept
}

Time O(n)Space O(1)

Each number is read once and written at most once, with no second array.

Pattern notes: Two Pointers · Open on LeetCode

1Brute force — paste nums2 at the end and sort

Copy nums2 into the empty slots, then let Java sort the whole thing.

void merge(int[] nums1, int m, int[] nums2, int n) {
    for (int j = 0; j < n; j++) {
        nums1[m + j] = nums2[j];     // fill the empty slots
    }
    Arrays.sort(nums1);
}

Time O((m+n) log(m+n))Space O(1)*

Short and correct, but it throws away the fact that both arrays are already sorted. We can merge in one linear pass. (*Java's sort for int[] uses a little stack space.)

2Optimal — three pointers, fill from the back

void merge(int[] nums1, int m, int[] nums2, int n) {
    int i = m - 1;          // last real number in nums1
    int j = n - 1;          // last number in nums2
    int k = m + n - 1;      // last free slot in nums1
    while (j >= 0) {        // stop when nums2 is used up
        if (i >= 0 && nums1[i] > nums2[j]) {
            nums1[k--] = nums1[i--];   // nums1's number is bigger
        } else {
            nums1[k--] = nums2[j--];   // nums2's number is bigger (or equal)
        }
    }
}

Time O(m + n)Space O(1)

Every number is placed once. When nums2 runs out, whatever is left of nums1 is already in the right spot.

Pattern notes: Two Pointers · Open on LeetCode

1Brute force — count every number

For each number, count how many times it appears in the whole array. The first one with a count above n / 2 is the answer.

int majorityElement(int[] nums) {
    for (int x : nums) {
        int count = 0;
        for (int y : nums) {
            if (y == x) count++;
        }
        if (count > nums.length / 2) return x;
    }
    return -1;   // never happens: the majority always exists
}

Time O(n²)Space O(1)

Too slow for big inputs. A HashMap of counts gets O(n) time but needs O(n) memory. Sorting and taking the middle element also works in O(n log n). Can we get O(n) time and O(1) memory?

2Optimal — Boyer-Moore voting

int majorityElement(int[] nums) {
    int candidate = 0;
    int count = 0;
    for (int x : nums) {
        if (count == 0) candidate = x;   // no leader: x takes over
        if (x == candidate) count++;     // a vote for the leader
        else count--;                    // a vote against: they cancel
    }
    return candidate;
}

Time O(n)Space O(1)

Only two variables, one pass. It works because every "against" vote can cancel at most one majority vote, and the majority has more than all others together.

Pattern notes: Arrays & Strings · Open on LeetCode

1Brute force — sort, then look for the gap

After sorting, the number at index i should be i. The first index where it isn't is the missing number. If every index matches, the missing number is n.

int missingNumber(int[] nums) {
    Arrays.sort(nums);
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] != i) return i;   // i should be here but isn't
    }
    return nums.length;               // 0..n-1 all present, so n is missing
}

Time O(n log n)Space O(1)*

Sorting is the slow part, and it's more work than needed: we only want one number. (*Plus the sort's small stack space.)

2Optimal — expected sum minus actual sum

int missingNumber(int[] nums) {
    int n = nums.length;
    int expected = n * (n + 1) / 2;   // sum of 0..n
    int actual = 0;
    for (int x : nums) actual += x;
    return expected - actual;
}

Time O(n)Space O(1)

One pass to add the numbers, one formula. Another O(n), O(1) way: XOR every index and every value together; pairs cancel (a ^ a = 0) and only the missing number is left (see LC 136).

Pattern notes: Math & Number Theory · Open on LeetCode

1Brute force — count each number

For each number, count how often it appears. The one with a count of 1 is the answer.

int singleNumber(int[] nums) {
    for (int x : nums) {
        int count = 0;
        for (int y : nums) {
            if (y == x) count++;
        }
        if (count == 1) return x;
    }
    return -1;   // never happens
}

Time O(n²)Space O(1)

Too slow. A HashMap of counts (or a HashSet where you add, then remove on the second sighting) is O(n) time, but it needs O(n) memory, which the problem forbids.

2Optimal — XOR everything together

int singleNumber(int[] nums) {
    int result = 0;            // x ^ 0 = x, so 0 is a safe start
    for (int x : nums) {
        result ^= x;           // pairs cancel out: a ^ a = 0
    }
    return result;             // only the single number is left
}

Time O(n)Space O(1)

One variable, one pass. It also works with negative numbers, because XOR just works on the bits.

Pattern notes: Bit Manipulation · Open on LeetCode

1Brute force — copy it backwards

Make a new array, fill it from the back of s, then copy it back into s. Easy to think of, but it needs a whole second array.

void reverseString(char[] s) {
    char[] copy = new char[s.length];
    for (int i = 0; i < s.length; i++) copy[i] = s[s.length - 1 - i];
    for (int i = 0; i < s.length; i++) s[i] = copy[i];
}

Time O(n)Space O(n)

The speed is fine, but the problem asks for O(1) extra memory, and the copy breaks that rule.

2Optimal — swap from both ends

void reverseString(char[] s) {
    int left = 0, right = s.length - 1;
    while (left < right) {          // stop when the pointers meet or cross
        char tmp = s[left];         // classic swap with a temp variable
        s[left] = s[right];
        s[right] = tmp;
        left++;                     // both ends move one step inward
        right--;
    }
}

Time O(n)Space O(1)

Only two index variables and one temp character, no matter how long the string is.

Pattern notes: Two Pointers · Open on LeetCode

1Brute force — clean it, reverse it, compare

Build a new string with only the lowercase letters and digits. Then reverse it and check if it equals itself.

boolean isPalindrome(String s) {
    StringBuilder clean = new StringBuilder();
    for (char c : s.toCharArray()) {
        if (Character.isLetterOrDigit(c)) clean.append(Character.toLowerCase(c));
    }
    String forward = clean.toString();
    String backward = clean.reverse().toString();
    return forward.equals(backward);
}

Time O(n)Space O(n)

Correct and readable, but it builds two extra strings. An interviewer will ask you to do it without the copies.

2Optimal — two pointers that skip the junk

boolean isPalindrome(String s) {
    int left = 0, right = s.length() - 1;
    while (left < right) {
        // skip anything that is not a letter or digit (keep left < right!)
        while (left < right && !Character.isLetterOrDigit(s.charAt(left))) left++;
        while (left < right && !Character.isLetterOrDigit(s.charAt(right))) right--;
        // compare ignoring case
        if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) {
            return false;
        }
        left++;
        right--;
    }
    return true;
}

Time O(n)Space O(1)

Each pointer only moves forward (or backward), so every character is looked at once, and nothing is copied.

Pattern notes: Two Pointers · Open on LeetCode

1Brute force — sort both and compare

If two words have the same letters, sorting them gives the same result: "anagram" and "nagaram" both become "aaagmnr".

boolean isAnagram(String s, String t) {
    if (s.length() != t.length()) return false;
    char[] a = s.toCharArray();
    char[] b = t.toCharArray();
    Arrays.sort(a);
    Arrays.sort(b);
    return Arrays.equals(a, b);
}

Time O(n log n)Space O(n)

Nice and short, but sorting does more work than needed. We don't care about order, only about how many of each letter.

2Optimal — count the letters

boolean isAnagram(String s, String t) {
    if (s.length() != t.length()) return false;   // different sizes can't match
    int[] count = new int[26];                    // count[0] is 'a', count[25] is 'z'
    for (int i = 0; i < s.length(); i++) {
        count[s.charAt(i) - 'a']++;               // letter from s: +1
        count[t.charAt(i) - 'a']--;               // letter from t: -1
    }
    for (int c : count) {
        if (c != 0) return false;                 // some letter didn't cancel out
    }
    return true;
}

Time O(n)Space O(1)

The array always has 26 slots, whatever the input size, so the extra memory counts as constant.

Pattern notes: Hashing · Open on LeetCode

1Brute force — check every letter against all others

For each position, scan the whole string to see if the same letter shows up anywhere else. The first letter with no twin is the answer.

int firstUniqChar(String s) {
    for (int i = 0; i < s.length(); i++) {
        boolean repeated = false;
        for (int j = 0; j < s.length(); j++) {
            if (i != j && s.charAt(i) == s.charAt(j)) { repeated = true; break; }
        }
        if (!repeated) return i;
    }
    return -1;
}

Time O(n²)Space O(1)

For a long string with no unique letter, every position scans the whole string again. That's a lot of repeated work.

2Optimal — count first, then find

int firstUniqChar(String s) {
    int[] count = new int[26];
    for (int i = 0; i < s.length(); i++) {
        count[s.charAt(i) - 'a']++;               // pass 1: how many of each letter
    }
    for (int i = 0; i < s.length(); i++) {
        if (count[s.charAt(i) - 'a'] == 1) return i;   // pass 2: first with count 1
    }
    return -1;                                    // every letter repeats
}

Time O(n)Space O(1)

Two passes of n steps is still O(n), and the count array is a fixed 26 slots.

Pattern notes: Hashing · Open on LeetCode

1Brute force — try longer and longer prefixes

Take the first word. Try its first 1 letter, then first 2 letters, and so on. For each try, check that every word starts with it. Stop at the first try that fails.

String longestCommonPrefix(String[] strs) {
    String best = "";
    for (int len = 1; len <= strs[0].length(); len++) {
        String candidate = strs[0].substring(0, len);   // builds a new string each time
        boolean all = true;
        for (String w : strs) {
            if (!w.startsWith(candidate)) { all = false; break; }
        }
        if (!all) break;
        best = candidate;
    }
    return best;
}

Time O(n · m²)Space O(m)

(n words, prefix length m.) Every try re-checks the letters the previous try already confirmed, and builds a new substring each time.

2Optimal — compare column by column

String longestCommonPrefix(String[] strs) {
    String first = strs[0];
    for (int i = 0; i < first.length(); i++) {       // column i
        char c = first.charAt(i);
        for (int k = 1; k < strs.length; k++) {         // every other word
            // this word is too short, or has a different letter here
            if (i == strs[k].length() || strs[k].charAt(i) != c) {
                return first.substring(0, i);
            }
        }
    }
    return first;   // the whole first word is a common prefix
}

Time O(S)Space O(1)

S is the total number of letters. In the worst case we look at every letter once, and we build only one substring at the very end.

Pattern notes: Arrays & Strings · Open on LeetCode

1Brute force — compare every pair of positions

Renaming keeps "same" and "different" intact. So for every pair of positions i and j: if s has the same letter at both, t must too, and if s has different letters, t must too.

boolean isIsomorphic(String s, String t) {
    for (int i = 0; i < s.length(); i++) {
        for (int j = i + 1; j < s.length(); j++) {
            boolean sameInS = s.charAt(i) == s.charAt(j);
            boolean sameInT = t.charAt(i) == t.charAt(j);
            if (sameInS != sameInT) return false;
        }
    }
    return true;
}

Time O(n²)Space O(1)

Correct, but with 50,000 letters that's over a billion pair checks.

2Optimal — two maps, one for each direction

boolean isIsomorphic(String s, String t) {
    char[] sToT = new char[256];   // 0 means "no mapping yet" (works for ASCII)
    char[] tToS = new char[256];
    for (int i = 0; i < s.length(); i++) {
        char a = s.charAt(i), b = t.charAt(i);
        if (sToT[a] == 0 && tToS[b] == 0) {   // both letters are new: record the pair
            sToT[a] = b;
            tToS[b] = a;
        } else if (sToT[a] != b || tToS[b] != a) {
            return false;                      // pair disagrees with what we recorded
        }
    }
    return true;
}

Time O(n)Space O(1)

One pass, and the two arrays have a fixed 256 slots (one per ASCII character), so memory doesn't grow with n.

Pattern notes: Hashing · Open on LeetCode

1Brute force — try every choice

At each letter of t we have a choice: use it (if it matches the next letter of s) or skip it. Recursion can try both options and see if any path works.

boolean isSubsequence(String s, String t) {
    return tryMatch(s, t, 0, 0);
}
boolean tryMatch(String s, String t, int i, int j) {
    if (i == s.length()) return true;      // matched all of s
    if (j == t.length()) return false;     // t ran out first
    if (s.charAt(i) == t.charAt(j) && tryMatch(s, t, i + 1, j + 1)) return true;  // use t[j]
    return tryMatch(s, t, i, j + 1);       // skip t[j]
}

Time O(2ⁿ)Space O(n)

With inputs like s = "aaab", t = "aaaaaaaa" the "use it or skip it" branches explode. We are exploring choices that never needed exploring.

2Optimal — greedy two pointers

boolean isSubsequence(String s, String t) {
    int i = 0;                                      // next letter of s we need
    for (int j = 0; j < t.length() && i < s.length(); j++) {
        if (s.charAt(i) == t.charAt(j)) i++;        // match: move on in s
    }                                               // j always moves on in t
    return i == s.length();                         // did we match all of s?
}

Time O(n)Space O(1)

n is the length of t. Each letter of t is looked at once, and there's no recursion stack.

Pattern notes: Two Pointers · Open on LeetCode

1First try — a table of all 13 symbols and pairs

List the six special pairs (CM, CD, XC, XL, IX, IV) and the seven single symbols. At each position, try the pairs first, then the singles, add the value and jump ahead.

int romanToInt(String s) {
    String[] symbols = {"CM","CD","XC","XL","IX","IV","M","D","C","L","X","V","I"};
    int[] values     = { 900, 400,  90,  40,   9,   4,1000,500,100, 50, 10,  5,  1};
    int total = 0, i = 0;
    while (i < s.length()) {
        for (int k = 0; k < symbols.length; k++) {
            if (s.startsWith(symbols[k], i)) {    // pairs are listed first on purpose
                total += values[k];
                i += symbols[k].length();
                break;
            }
        }
    }
    return total;
}

Time O(n)Space O(1)

This is already O(n), so there's no faster solution. But it tries up to 13 entries per position, and the table order must be exactly right. There is a much simpler rule.

2Cleaner — look at the next symbol

int romanToInt(String s) {
    Map<Character, Integer> value = Map.of(
        'I', 1, 'V', 5, 'X', 10, 'L', 50, 'C', 100, 'D', 500, 'M', 1000);
    int total = 0;
    for (int i = 0; i < s.length(); i++) {
        int cur = value.get(s.charAt(i));
        // smaller than the next symbol? then it is the "minus" part of a pair
        if (i + 1 < s.length() && cur < value.get(s.charAt(i + 1))) {
            total -= cur;
        } else {
            total += cur;
        }
    }
    return total;
}

Time O(n)Space O(1)

One pass with one comparison per symbol. The map always holds 7 entries, so it's constant memory.

Pattern notes: Arrays & Strings · Open on LeetCode

1Brute force — find and cross out each letter

For each letter of the note, search the magazine for it. If found, delete it so it can't be used again. If not found, return false.

boolean canConstruct(String ransomNote, String magazine) {
    StringBuilder mag = new StringBuilder(magazine);
    for (char c : ransomNote.toCharArray()) {
        int pos = mag.indexOf(String.valueOf(c));   // linear search
        if (pos == -1) return false;
        mag.deleteCharAt(pos);                      // shifts the rest: also linear
    }
    return true;
}

Time O(m · n)Space O(n)

(m = note length, n = magazine length.) Each note letter searches and shifts the whole magazine again.

2Optimal — count the magazine, spend from the count

boolean canConstruct(String ransomNote, String magazine) {
    int[] count = new int[26];
    for (char c : magazine.toCharArray()) count[c - 'a']++;   // what we have
    for (char c : ransomNote.toCharArray()) {
        if (--count[c - 'a'] < 0) return false;             // spend one; ran out?
    }
    return true;
}

Time O(m + n)Space O(1)

One pass over each string, and the counter array is always 26 slots.

Pattern notes: Hashing · Open on LeetCode

1Brute force — nested loops

For every number in nums1, scan nums2. If you find it, add it to a result set (the set removes duplicates for you).

int[] intersection(int[] nums1, int[] nums2) {
    Set<Integer> result = new HashSet<>();
    for (int a : nums1) {
        for (int b : nums2) {
            if (a == b) { result.add(a); break; }
        }
    }
    int[] out = new int[result.size()];
    int k = 0;
    for (int v : result) out[k++] = v;
    return out;
}

Time O(n · m)Space O(n)

The inner loop searches nums2 again for every number. A set can do that search in O(1).

2Optimal — put one array in a set

int[] intersection(int[] nums1, int[] nums2) {
    Set<Integer> set1 = new HashSet<>();
    for (int n : nums1) set1.add(n);            // duplicates in nums1 vanish here
    List<Integer> result = new ArrayList<>();
    for (int n : nums2) {
        if (set1.remove(n)) result.add(n);      // remove() returns true if it was there
    }
    int[] out = new int[result.size()];
    for (int i = 0; i < out.length; i++) out[i] = result.get(i);
    return out;
}

Time O(n + m)Space O(n)

Building the set is one pass, checking is another, and every set operation is O(1) on average.

Pattern notes: Hashing · Open on LeetCode

1Brute force — match and mark as used

For each number in nums1, look for an unused equal number in nums2. When you find one, mark it used so it can't be matched twice.

int[] intersect(int[] nums1, int[] nums2) {
    boolean[] used = new boolean[nums2.length];
    List<Integer> result = new ArrayList<>();
    for (int a : nums1) {
        for (int j = 0; j < nums2.length; j++) {
            if (!used[j] && nums2[j] == a) {
                used[j] = true;
                result.add(a);
                break;
            }
        }
    }
    int[] out = new int[result.size()];
    for (int i = 0; i < out.length; i++) out[i] = result.get(i);
    return out;
}

Time O(n · m)Space O(m)

Again, every number re-scans the other array. A set isn't enough anymore (it forgets how many), but a map can remember counts.

2Optimal — a count map

int[] intersect(int[] nums1, int[] nums2) {
    Map<Integer, Integer> count = new HashMap<>();
    for (int n : nums1) count.put(n, count.getOrDefault(n, 0) + 1);
    List<Integer> result = new ArrayList<>();
    for (int n : nums2) {
        int left = count.getOrDefault(n, 0);   // copies still available
        if (left > 0) {
            result.add(n);
            count.put(n, left - 1);           // use one up
        }
    }
    int[] out = new int[result.size()];
    for (int i = 0; i < out.length; i++) out[i] = result.get(i);
    return out;
}

Time O(n + m)Space O(n)

One pass to count, one pass to match, each map operation O(1) on average.

Pattern notes: Hashing · Open on LeetCode

1Brute force — compare every pair of positions

Split the sentence into words. For every pair of positions, the letters must be equal exactly when the words are equal.

boolean wordPattern(String pattern, String s) {
    String[] words = s.split(" ");
    if (words.length != pattern.length()) return false;
    for (int i = 0; i < words.length; i++) {
        for (int j = i + 1; j < words.length; j++) {
            boolean sameLetter = pattern.charAt(i) == pattern.charAt(j);
            boolean sameWord = words[i].equals(words[j]);
            if (sameLetter != sameWord) return false;
        }
    }
    return true;
}

Time O(n²)Space O(n)

It checks every pair, even though one pass with a record of what each letter means is enough.

2Optimal — two maps, letter→word and word→letter

boolean wordPattern(String pattern, String s) {
    String[] words = s.split(" ");
    if (words.length != pattern.length()) return false;   // counts must match
    Map<Character, String> letterToWord = new HashMap<>();
    Map<String, Character> wordToLetter = new HashMap<>();
    for (int i = 0; i < words.length; i++) {
        char c = pattern.charAt(i);
        String w = words[i];
        // compare Strings with equals(), never ==
        if (letterToWord.containsKey(c) && !letterToWord.get(c).equals(w)) return false;
        if (wordToLetter.containsKey(w) && wordToLetter.get(w) != c) return false;
        letterToWord.put(c, w);
        wordToLetter.put(w, c);
    }
    return true;
}

Time O(n)Space O(n)

n is the length of s. Splitting and the single loop each touch every character a constant number of times.

Pattern notes: Hashing · Open on LeetCode

1Good first answer — remember every number in a set

The only hard part is knowing when to give up. If a number shows up a second time, we are in a loop and will never reach 1. A HashSet remembers what we've seen.

boolean isHappy(int n) {
    Set<Integer> seen = new HashSet<>();
    while (n != 1 && !seen.contains(n)) {
        seen.add(n);
        n = next(n);
    }
    return n == 1;
}
int next(int n) {                 // sum of the squares of the digits
    int sum = 0;
    while (n > 0) {
        int d = n % 10;           // last digit
        sum += d * d;
        n /= 10;                  // drop the last digit
    }
    return sum;
}

Time O(log n)Space O(log n)

This is already fast and a perfectly good interview answer. The follow-up is: can you detect the loop without storing the numbers?

2Optimal — fast and slow pointers, no set

boolean isHappy(int n) {
    int slow = n, fast = next(n);
    while (fast != 1 && slow != fast) {
        slow = next(slow);           // one step
        fast = next(next(fast));     // two steps
    }
    return fast == 1;                // stopped at 1, or runners met in a loop
}
// next(n) is the same digit-square helper as above

Time O(log n)Space O(1)

The numbers shrink to at most three digits very quickly, so there are only a handful of steps, and we keep just two variables.

Pattern notes: Fast & Slow Pointers · Open on LeetCode

1Brute force — count with loops, compare with loops

For every position, count how often its value appears by scanning the whole array. Then compare every pair: two different values must not share a count.

boolean uniqueOccurrences(int[] arr) {
    int n = arr.length;
    int[] cnt = new int[n];                  // cnt[i] = how often arr[i] appears
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (arr[j] == arr[i]) cnt[i]++;
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (arr[i] != arr[j] && cnt[i] == cnt[j]) return false;
        }
    }
    return true;
}

Time O(n²)Space O(n)

Two nested loops, both doing work a HashMap and a HashSet can do in one pass each.

2Optimal — count map, then a set of counts

boolean uniqueOccurrences(int[] arr) {
    Map<Integer, Integer> count = new HashMap<>();
    for (int n : arr) count.put(n, count.getOrDefault(n, 0) + 1);   // value -> count
    Set<Integer> seenCounts = new HashSet<>(count.values());       // duplicates vanish
    return seenCounts.size() == count.size();    // no count was lost?
}

Time O(n)Space O(n)

One pass to count, and building the set touches each distinct value once.

Pattern notes: Hashing · Open on LeetCode

1Brute force — square, then sort

Square each number into a new array, then call Arrays.sort. Simple and correct.

int[] sortedSquares(int[] nums) {
    int[] res = new int[nums.length];
    for (int i = 0; i < nums.length; i++) res[i] = nums[i] * nums[i];
    Arrays.sort(res);
    return res;
}

Time O(n log n)Space O(n)

Sorting costs n log n, but the input was already sorted. We are throwing that order away and paying to rebuild it.

2Optimal — the biggest square is always at an end

int[] sortedSquares(int[] nums) {
    int n = nums.length;
    int[] res = new int[n];
    int left = 0, right = n - 1;
    for (int pos = n - 1; pos >= 0; pos--) {       // fill from the back
        int l = nums[left] * nums[left];
        int r = nums[right] * nums[right];
        if (l > r) { res[pos] = l; left++; }     // left end is bigger
        else       { res[pos] = r; right--; }    // right end is bigger (or equal)
    }
    return res;
}

Time O(n)Space O(n)

One pass, one comparison per slot. The O(n) space is only the output array, which the problem asks for anyway.

Pattern notes: Two Pointers · Open on LeetCode

1Brute force — add up every block from scratch

For each starting position, loop over the next k numbers and add them up. Keep the biggest sum and divide by k at the end.

double findMaxAverage(int[] nums, int k) {
    double best = Double.NEGATIVE_INFINITY;
    for (int i = 0; i + k <= nums.length; i++) {
        int sum = 0;
        for (int j = i; j < i + k; j++) sum += nums[j];
        best = Math.max(best, sum);
    }
    return best / k;
}

Time O(n·k)Space O(1)

Two neighbouring blocks share k − 1 numbers, yet we add all of them again every time. That repeated work is what we remove next.

2Optimal — slide the window, keep a running sum

double findMaxAverage(int[] nums, int k) {
    int sum = 0;
    for (int i = 0; i < k; i++) sum += nums[i];   // build the first window
    int best = sum;
    for (int i = k; i < nums.length; i++) {
        sum += nums[i] - nums[i - k];               // nums[i] enters, nums[i-k] leaves
        best = Math.max(best, sum);
    }
    return (double) best / k;                       // divide once, at the end
}

Time O(n)Space O(1)

Every number is added once and removed once, so the whole scan is linear.

Pattern notes: Sliding Window · Open on LeetCode

1Brute force — compare each number with the next k

For each position, look at the next k positions and check for an equal number.

boolean containsNearbyDuplicate(int[] nums, int k) {
    for (int i = 0; i < nums.length; i++) {
        for (int j = i + 1; j < nums.length && j - i <= k; j++) {
            if (nums[i] == nums[j]) return true;
        }
    }
    return false;
}

Time O(n·k)Space O(1)

When k is as big as n this is O(n²). We keep re-reading the same neighbours for every i.

2Optimal — keep the last k numbers in a HashSet

boolean containsNearbyDuplicate(int[] nums, int k) {
    Set<Integer> window = new HashSet<>();   // the last k numbers
    for (int i = 0; i < nums.length; i++) {
        if (window.contains(nums[i])) return true;   // a copy within k steps
        window.add(nums[i]);
        if (window.size() > k) {
            window.remove(nums[i - k]);        // too far behind now: slide it out
        }
    }
    return false;
}

Time O(n)Space O(min(n, k))

Each number enters and leaves the set once, and the set never holds more than k numbers.

Pattern notes: Sliding Window · Open on LeetCode

1Brute force — put each piece into a HashSet

For every start position, add the 3 characters to a set. If the set ends up with 3 items, they were all different.

int countGoodSubstrings(String s) {
    int count = 0;
    for (int i = 0; i + 3 <= s.length(); i++) {
        Set<Character> seen = new HashSet<>();
        for (int j = i; j < i + 3; j++) seen.add(s.charAt(j));
        if (seen.size() == 3) count++;
    }
    return count;
}

Time O(n)Space O(1)

Because the window is always size 3, this is already linear. But it creates a new set for every position, which is heavy for such a tiny check, and it hides the sliding-window shape.

2Cleaner — slide a 3-wide window and compare directly

int countGoodSubstrings(String s) {
    int count = 0;
    for (int i = 2; i < s.length(); i++) {       // window = s[i-2..i]
        char a = s.charAt(i - 2), b = s.charAt(i - 1), c = s.charAt(i);
        if (a != b && b != c && a != c) count++;  // all three different
    }
    return count;
}

Time O(n)Space O(1)

Same big-O as step 1, but no objects are created, and the code states the rule directly.

Pattern notes: Sliding Window · Open on LeetCode

1Brute force — add up from the start for every position

For each position i, loop from 0 to i and add everything.

int[] runningSum(int[] nums) {
    int[] ans = new int[nums.length];
    for (int i = 0; i < nums.length; i++) {
        int sum = 0;
        for (int j = 0; j <= i; j++) sum += nums[j];   // re-add everything
        ans[i] = sum;
    }
    return ans;
}

Time O(n²)Space O(n)

We keep re-adding the same numbers: to get position 3 we add 1 + 2 + 3 again, even though we already know 1 + 2 + 3 = 6 from the step before.

2Optimal — reuse the previous total

int[] runningSum(int[] nums) {
    for (int i = 1; i < nums.length; i++) {
        nums[i] += nums[i - 1];   // previous total + this number
    }
    return nums;
}

Time O(n)Space O(1)

Each number is added once. Space is O(1) extra because we reuse the input array (make a new array instead if you must not change the input).

Pattern notes: Prefix Sum · Open on LeetCode

1Brute force — add both sides for every index

For each index, loop over the left part and the right part separately and compare the two sums.

int pivotIndex(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;
}

Time O(n²)Space O(1)

Every index re-adds almost the whole array. With 10,000 numbers that's about 100 million additions.

2Optimal — total sum and a running left sum

int pivotIndex(int[] nums) {
    int total = 0;
    for (int x : nums) total += x;              // pass 1: whole sum
    int left = 0;                               // sum of nums[0..i-1]
    for (int i = 0; i < nums.length; i++) {
        int right = total - left - nums[i];     // everything after i
        if (left == right) return i;
        left += nums[i];                        // i moves into the left side
    }
    return -1;
}

Time O(n)Space O(1)

Two simple passes instead of a loop inside a loop, and no extra array: left is a prefix sum we keep in one variable.

Pattern notes: Prefix Sum · Open on LeetCode

1Brute force — loop over the range for every query

Keep the array and add up the requested range each time someone asks.

class NumArray {
    private final int[] nums;

    public NumArray(int[] nums) {
        this.nums = nums;
    }

    public int sumRange(int left, int right) {
        int sum = 0;
        for (int i = left; i <= right; i++) sum += nums[i];
        return sum;
    }
}

Time O(n) per querySpace O(1)

One query is fine, but there can be up to 10,000 queries on 10,000 numbers: about 100 million additions, mostly adding the same numbers again and again.

2Optimal — precompute a prefix sum array

class NumArray {
    private final int[] prefix;   // prefix[k] = sum of the first k numbers

    public NumArray(int[] nums) {
        prefix = new int[nums.length + 1];          // prefix[0] = 0
        for (int i = 0; i < nums.length; i++) {
            prefix[i + 1] = prefix[i] + nums[i];
        }
    }

    public int sumRange(int left, int right) {
        return prefix[right + 1] - prefix[left];    // O(1) per query
    }
}

Time O(n) build, O(1) per querySpace O(n)

We pay once up front and every query after that is a single subtraction. Great trade when there are many queries.

Pattern notes: Prefix Sum · Open on LeetCode

1Brute force — delete matching pairs until nothing changes

A valid string always has at least one pair like (), [] or {} sitting right next to each other. Remove them and repeat. If the string becomes empty, it was valid.

boolean isValid(String s) {
    String prev = null;
    while (!s.equals(prev)) {              // stop when a round removes nothing
        prev = s;
        s = s.replace("()", "").replace("[]", "").replace("{}", "");
    }
    return s.isEmpty();
}

Time O(n²)Space O(n)

Deeply nested input like "(((...)))" needs about n/2 rounds, and each round copies the whole string.

2Optimal — a stack of the closers we are waiting for

boolean isValid(String s) {
    Deque<Character> stack = new ArrayDeque<>();
    for (char c : s.toCharArray()) {
        if (c == '(') stack.push(')');        // opener: remember which closer we need
        else if (c == '[') stack.push(']');
        else if (c == '{') stack.push('}');
        else if (stack.isEmpty() || stack.pop() != c) return false;  // wrong or no opener
    }
    return stack.isEmpty();                   // leftover openers were never closed
}

Time O(n)Space O(n)

One pass; each character is pushed or popped once.

Pattern notes: Stacks · Open on LeetCode

1Brute force — simulate with a list, sum at the end

Do exactly what the rules say using an ArrayList, always working with its last items, then add everything up.

int calPoints(String[] operations) {
    List<Integer> scores = new ArrayList<>();
    for (String op : operations) {
        int n = scores.size();
        if (op.equals("+")) scores.add(scores.get(n - 1) + scores.get(n - 2));
        else if (op.equals("D")) scores.add(2 * scores.get(n - 1));
        else if (op.equals("C")) scores.remove(n - 1);
        else scores.add(Integer.parseInt(op));
    }
    int total = 0;
    for (int s : scores) total += s;
    return total;
}

Time O(n)Space O(n)

This is already optimal: you must read every operation, and you must remember old scores because "C" can cancel back through them. Notice that we only ever touch the end of the list: that is a stack in disguise.

2Cleaner — a real stack plus a running total

int calPoints(String[] operations) {
    Deque<Integer> stack = new ArrayDeque<>();
    int total = 0;
    for (String op : operations) {
        if (op.equals("+")) {
            int top = stack.pop();           // take the top off to see the one below
            int sum = top + stack.peek();
            stack.push(top);                 // put it back
            stack.push(sum);
            total += sum;
        } else if (op.equals("D")) {
            int d = 2 * stack.peek();
            stack.push(d);
            total += d;
        } else if (op.equals("C")) {
            total -= stack.pop();            // undo the last score
        } else {
            int v = Integer.parseInt(op);    // a plain number, may be negative
            stack.push(v);
            total += v;
        }
    }
    return total;
}

Time O(n)Space O(n)

Same big-O as step 1; the stack just says clearly "we only care about the latest scores".

Pattern notes: Stacks · Open on LeetCode

1Brute force — actually type both strings, then compare

Use a StringBuilder as a stack: append normal characters, delete the last one on #. Build both final strings and compare them.

boolean backspaceCompare(String s, String t) {
    return build(s).equals(build(t));
}

String build(String str) {
    StringBuilder sb = new StringBuilder();          // works like a stack of chars
    for (char c : str.toCharArray()) {
        if (c != '#') sb.append(c);
        else if (sb.length() > 0) sb.deleteCharAt(sb.length() - 1);
    }
    return sb.toString();
}

Time O(n + m)Space O(n + m)

Fast and a great answer to start with. The follow-up asks for O(1) extra space, so we must avoid building new strings.

2Optimal — walk both strings backwards

boolean backspaceCompare(String s, String t) {
    int i = s.length() - 1, j = t.length() - 1;
    while (i >= 0 || j >= 0) {
        i = nextChar(s, i);              // jump to the next letter that survives
        j = nextChar(t, j);
        if (i < 0 && j < 0) return true;   // both finished at the same time
        if (i < 0 || j < 0) return false;  // one text is longer
        if (s.charAt(i) != t.charAt(j)) return false;
        i--; j--;
    }
    return true;
}

// Returns the index of the next surviving char at or before i, or -1.
int nextChar(String str, int i) {
    int skip = 0;
    while (i >= 0) {
        if (str.charAt(i) == '#') { skip++; i--; }   // one more letter to erase
        else if (skip > 0)        { skip--; i--; }   // this letter is erased
        else break;                                   // a real, surviving letter
    }
    return i;
}

Time O(n + m)Space O(1)

Each index moves left only, so both strings are read once, and we store just a few ints.

Pattern notes: Stacks · Open on LeetCode

1Simple design — keep the stack in queue order on every push

Keep one main stack with the oldest item on top. To push, pour everything into a temp stack, put the new item at the bottom, and pour everything back. Then pop and peek are just the top.

class MyQueue {
    private Deque<Integer> main = new ArrayDeque<>();   // oldest item on top
    private Deque<Integer> temp = new ArrayDeque<>();

    public MyQueue() {}

    public void push(int x) {
        while (!main.isEmpty()) temp.push(main.pop());  // move all out
        main.push(x);                                   // new item goes to the bottom
        while (!temp.isEmpty()) main.push(temp.pop());  // move all back on top of it
    }

    public int pop()  { return main.pop(); }
    public int peek() { return main.peek(); }
    public boolean empty() { return main.isEmpty(); }
}

push O(n)pop / peek O(1)Space O(n)

Correct, but every single push moves the whole queue twice. n pushes cost O(n²) in total.

2Better design — an "in" stack and an "out" stack

class MyQueue {
    private Deque<Integer> in = new ArrayDeque<>();    // new items land here
    private Deque<Integer> out = new ArrayDeque<>();   // oldest item on top

    public MyQueue() {}

    public void push(int x) { in.push(x); }

    public int pop()  { moveIfNeeded(); return out.pop(); }

    public int peek() { moveIfNeeded(); return out.peek(); }

    public boolean empty() { return in.isEmpty() && out.isEmpty(); }

    private void moveIfNeeded() {
        if (out.isEmpty()) {                             // only pour when out runs dry
            while (!in.isEmpty()) out.push(in.pop());
        }
    }
}

All operations O(1) amortizedSpace O(n)

A single pop can take O(n) when it pours, but each item is poured only once, so n operations cost O(n) in total: O(1) each on average ("amortized").

Pattern notes: Queues & Deques · Open on LeetCode

1Brute force — find it, then look right

For each number in nums1, find where it sits in nums2, then walk to the right until you hit something bigger.

int[] nextGreaterElement(int[] nums1, int[] nums2) {
    int[] res = new int[nums1.length];
    for (int i = 0; i < nums1.length; i++) {
        res[i] = -1;
        int j = 0;
        while (nums2[j] != nums1[i]) j++;            // find its position
        for (j = j + 1; j < nums2.length; j++) {    // scan to the right
            if (nums2[j] > nums1[i]) { res[i] = nums2[j]; break; }
        }
    }
    return res;
}

Time O(n1 · n2)Space O(1)

Fine for this small problem, but each query rescans the array. With many queries, or the harder versions of this problem, it becomes O(n²).

2Optimal — a monotonic stack answers everyone in one pass

int[] nextGreaterElement(int[] nums1, int[] nums2) {
    Map<Integer, Integer> nextGreater = new HashMap<>();   // number -> its next greater
    Deque<Integer> stack = new ArrayDeque<>();             // numbers still waiting
    for (int num : nums2) {
        while (!stack.isEmpty() && stack.peek() < num) {
            nextGreater.put(stack.pop(), num);   // num is the first bigger one to its right
        }
        stack.push(num);                         // now num waits for its own answer
    }
    int[] res = new int[nums1.length];
    for (int i = 0; i < nums1.length; i++) {
        res[i] = nextGreater.getOrDefault(nums1[i], -1);   // never answered = -1
    }
    return res;
}

Time O(n1 + n2)Space O(n2)

Each number of nums2 is pushed once and popped at most once, so the while loop adds only O(n2) work in total.

Pattern notes: Monotonic Stack & Queue · Open on LeetCode

1Brute force — copy the values, rebuild backwards

Walk the list and copy every value into an ArrayList. Then build a brand new list by reading that ArrayList from the end to the start.

ListNode reverseList(ListNode head) {
    List<Integer> vals = new ArrayList<>();
    for (ListNode n = head; n != null; n = n.next) vals.add(n.val);   // copy values out
    ListNode dummy = new ListNode(0), tail = dummy;
    for (int i = vals.size() - 1; i >= 0; i--) {                       // rebuild backwards
        tail.next = new ListNode(vals.get(i));
        tail = tail.next;
    }
    return dummy.next;
}

Time O(n)Space O(n)

The speed is already fine, but we made a full copy of the list. The interviewer wants you to reverse it in place, using only a few pointers.

2Optimal — flip the arrows one by one with prev / curr

ListNode reverseList(ListNode head) {
    ListNode prev = null;          // the part already reversed
    ListNode curr = head;          // the node we are fixing now
    while (curr != null) {
        ListNode next = curr.next; // 1. save the rest of the list
        curr.next = prev;          // 2. flip the arrow backwards
        prev = curr;               // 3. move prev forward
        curr = next;               // 4. move curr forward
    }
    return prev;                   // prev is the new head
}

Time O(n)Space O(1)

Every node is visited once and we only ever hold three pointers, no matter how long the list is.

Pattern notes: In-place Linked List Reversal · Open on LeetCode

1Brute force — dump everything, sort, rebuild

Copy all values from both lists into one ArrayList, sort it, and build a new list from the sorted values.

ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    List<Integer> vals = new ArrayList<>();
    for (ListNode n = list1; n != null; n = n.next) vals.add(n.val);
    for (ListNode n = list2; n != null; n = n.next) vals.add(n.val);
    Collections.sort(vals);                        // ignores that both are already sorted
    ListNode dummy = new ListNode(0), tail = dummy;
    for (int v : vals) { tail.next = new ListNode(v); tail = tail.next; }
    return dummy.next;
}

Time O((n+m) log(n+m))Space O(n+m)

We throw away the most useful fact we were given: both lists are already sorted. Sorting again is wasted work, and so is the copy.

2Optimal — zip the two lists with a dummy node

ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    ListNode dummy = new ListNode(0);   // fake start, so we never special-case the head
    ListNode tail = dummy;              // last node of the merged list
    while (list1 != null && list2 != null) {
        if (list1.val <= list2.val) {   // take the smaller front node
            tail.next = list1;
            list1 = list1.next;
        } else {
            tail.next = list2;
            list2 = list2.next;
        }
        tail = tail.next;
    }
    tail.next = (list1 != null) ? list1 : list2;   // glue on whatever is left
    return dummy.next;
}

Time O(n+m)Space O(1)

Each node is looked at once, and we only re-point arrows, so no extra memory is needed.

Pattern notes: Linked Lists · Open on LeetCode

1Brute force — copy nodes into an array

A list has no index, but an array does. Put every node into an ArrayList, then return the one at position size / 2.

ListNode middleNode(ListNode head) {
    List<ListNode> nodes = new ArrayList<>();
    for (ListNode n = head; n != null; n = n.next) nodes.add(n);   // copy nodes into an array
    return nodes.get(nodes.size() / 2);                             // index n/2 = second middle
}

Time O(n)Space O(n)

Fast enough, but it stores every node. We can find the middle in one walk with no extra memory.

2Optimal — slow and fast pointers

ListNode middleNode(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {   // fast can still take 2 steps
        slow = slow.next;                         // 1 step
        fast = fast.next.next;                    // 2 steps
    }
    return slow;                                  // fast hit the end, slow is halfway
}

Time O(n)Space O(1)

One pass, two pointers. For even length, fast lands on null, which leaves slow on the second middle, exactly what the problem asks.

Pattern notes: Fast & Slow Pointers · Open on LeetCode

1Brute force — remember every node you visit

Walk the list and put each node into a HashSet. If you ever meet a node that is already in the set, you have gone around a loop.

boolean hasCycle(ListNode head) {
    Set<ListNode> seen = new HashSet<>();      // stores NODES, not values
    for (ListNode n = head; n != null; n = n.next) {
        if (!seen.add(n)) return true;         // add() returns false if already there
    }
    return false;                              // reached null: no loop
}

Time O(n)Space O(n)

Correct, but the set can hold every node. LeetCode's follow-up asks for O(1) memory.

2Optimal — Floyd's tortoise and hare

boolean hasCycle(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;          // tortoise: 1 step
        fast = fast.next.next;     // hare: 2 steps
        if (slow == fast) return true;   // same NODE: the hare lapped the tortoise
    }
    return false;                  // hare fell off the end: no loop
}

Time O(n)Space O(1)

Without a loop, fast reaches the end in n/2 steps. With a loop, they meet within about one lap. Either way it's linear, with just two pointers.

Pattern notes: Fast & Slow Pointers · Open on LeetCode

1Brute force — collect unique values, rebuild

Put every value into a LinkedHashSet (a set that remembers insertion order) to drop repeats, then build a fresh list from the set.

ListNode deleteDuplicates(ListNode head) {
    Set<Integer> seen = new LinkedHashSet<>();          // keeps first-seen order
    for (ListNode n = head; n != null; n = n.next) seen.add(n.val);
    ListNode dummy = new ListNode(0), tail = dummy;
    for (int v : seen) { tail.next = new ListNode(v); tail = tail.next; }
    return dummy.next;
}

Time O(n)Space O(n)

This would work even on an unsorted list, which is a hint that we are not using the "sorted" gift. Sorted means copies are neighbours, so we can just unlink them.

2Optimal — compare each node with its neighbour

ListNode deleteDuplicates(ListNode head) {
    ListNode curr = head;
    while (curr != null && curr.next != null) {
        if (curr.val == curr.next.val) {
            curr.next = curr.next.next;   // skip the copy, but DON'T move yet
        } else {
            curr = curr.next;             // next value is new, step forward
        }
    }
    return head;
}

Time O(n)Space O(1)

One walk, no extra structure. The head never changes because the first node is always kept.

Pattern notes: Linked Lists · Open on LeetCode

1Brute force — copy the values you keep, rebuild

Walk the list, copy every value that is not val into an ArrayList, then build a new list from it.

ListNode removeElements(ListNode head, int val) {
    List<Integer> keep = new ArrayList<>();
    for (ListNode n = head; n != null; n = n.next) {
        if (n.val != val) keep.add(n.val);          // copy only the good values
    }
    ListNode dummy = new ListNode(0), tail = dummy;
    for (int v : keep) { tail.next = new ListNode(v); tail = tail.next; }
    return dummy.next;
}

Time O(n)Space O(n)

It builds a whole second list. We can unlink the bad nodes in place instead.

2Optimal — dummy node, then unlink in place

ListNode removeElements(ListNode head, int val) {
    ListNode dummy = new ListNode(0, head);   // sits before the real head
    ListNode curr = dummy;                    // we always look at curr.next
    while (curr.next != null) {
        if (curr.next.val == val) {
            curr.next = curr.next.next;       // unlink it, stay put
        } else {
            curr = curr.next;                 // keep it, move on
        }
    }
    return dummy.next;                        // the head may have changed
}

Time O(n)Space O(1)

One pass, and only one extra node no matter how long the list is.

Pattern notes: Linked Lists · Open on LeetCode

1Brute force — check every pair of nodes

For each node in A, walk all of B and see if any node in B is the very same node.

ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    for (ListNode a = headA; a != null; a = a.next) {
        for (ListNode b = headB; b != null; b = b.next) {
            if (a == b) return a;          // same node object, not just same value
        }
    }
    return null;
}

Time O(m·n)Space O(1)

Two lists of 30,000 nodes means 900 million comparisons. (A HashSet of A's nodes gets O(m+n) time but costs O(m) memory.)

2Optimal — swap lists at the end so both walk the same distance

ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    ListNode a = headA, b = headB;
    while (a != b) {                       // stop when they point at the same node (or both null)
        a = (a == null) ? headB : a.next;  // A finished? jump to B's start
        b = (b == null) ? headA : b.next;  // B finished? jump to A's start
    }
    return a;                              // the meeting node, or null if none
}

Time O(m+n)Space O(1)

Each pointer walks at most m + n nodes, and we only store two pointers. The loop always ends: in the worst case both become null at the same moment.

Pattern notes: Two Pointers · Open on LeetCode

1Brute force — copy into an array, check from both ends

A list can't walk backwards, but an array can. Copy the values into an ArrayList, then compare the first with the last, the second with the second-last, and so on.

boolean isPalindrome(ListNode head) {
    List<Integer> vals = new ArrayList<>();
    for (ListNode n = head; n != null; n = n.next) vals.add(n.val);   // copy into an array
    int i = 0, j = vals.size() - 1;
    while (i < j) {
        if (!vals.get(i).equals(vals.get(j))) return false;   // equals, not == on Integer
        i++; j--;
    }
    return true;
}

Time O(n)Space O(n)

Simple and a fine first answer, but LeetCode's follow-up asks for O(1) extra space.

2Optimal — find the middle, reverse the second half, compare

boolean isPalindrome(ListNode head) {
    // 1. find the middle with slow / fast
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    // 2. reverse the second half (same code as LC 206)
    ListNode prev = null, curr = slow;
    while (curr != null) {
        ListNode next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }
    // 3. compare first half with reversed second half
    ListNode left = head, right = prev;
    while (right != null) {
        if (left.val != right.val) return false;
        left = left.next;
        right = right.next;
    }
    return true;
}

Time O(n)Space O(1)

Three linear walks, still O(n) total, and only a handful of pointers. (In an interview, mention that this changes the input list; you could reverse the half back afterwards.)

Pattern notes: Fast & Slow Pointers · Open on LeetCode

1Brute force — check every number

Walk from left to right and stop when you see the target.

int search(int[] nums, int target) {
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] == target) return i;
    }
    return -1;
}

Time O(n)Space O(1)

This ignores that the array is sorted, and the problem explicitly demands O(log n).

2Optimal — the binary search template

int search(int[] nums, int target) {
    int lo = 0, hi = nums.length - 1;          // the answer lives in [lo, hi]
    while (lo <= hi) {                         // range not empty yet
        int mid = lo + (hi - lo) / 2;          // middle, without overflow
        if (nums[mid] == target) return mid;   // found it
        else if (nums[mid] < target) lo = mid + 1;   // too small: throw away left half
        else hi = mid - 1;                     // too big: throw away right half
    }
    return -1;                                 // range became empty: not there
}

Time O(log n)Space O(1)

The range halves every round, so for n = 1,000,000 it takes at most about 20 rounds.

Pattern notes: Binary Search · Open on LeetCode

1Brute force — find the first number that is big enough

Both cases have the same answer: the first index whose number is >= target. If there is none, the target goes at the very end.

int searchInsert(int[] nums, int target) {
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] >= target) return i;   // first spot that is big enough
    }
    return nums.length;                    // bigger than everything: goes at the end
}

Time O(n)Space O(1)

Correct, but linear. The array is sorted, so we can binary search for that "first big enough" spot.

2Optimal — same template, plus an ans variable

int searchInsert(int[] nums, int target) {
    int lo = 0, hi = nums.length - 1;
    int ans = nums.length;                 // default: insert at the end
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] >= target) {         // mid is a valid spot...
            ans = mid;                     // ...remember it
            hi = mid - 1;                  // ...but look for an earlier one
        } else {
            lo = mid + 1;                  // mid too small: go right
        }
    }
    return ans;
}

Time O(log n)Space O(1)

Exactly the LC 704 loop. The only change: instead of returning on a match, we record ans and keep shrinking.

Pattern notes: Binary Search · Open on LeetCode

1Brute force — test versions one by one

Ask the API about version 1, 2, 3, ... and return the first one that says bad.

int firstBadVersion(int n) {
    for (int v = 1; v <= n; v++) {
        if (isBadVersion(v)) return v;     // first one that says "bad"
    }
    return n;
}

Time O(n)Space O(1)

n can be about 2 billion, so this can mean 2 billion API calls. Too slow (Time Limit Exceeded).

2Optimal — binary search for the first "bad"

int firstBadVersion(int n) {
    int lo = 1, hi = n;
    int ans = n;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;      // NOT (lo + hi) / 2: that can overflow
        if (isBadVersion(mid)) {
            ans = mid;                     // mid is bad: a candidate
            hi = mid - 1;                  // maybe an earlier one is bad too
        } else {
            lo = mid + 1;                  // mid is good: first bad is to the right
        }
    }
    return ans;
}

Time O(log n)Space O(1)

For n = 2,126,753,390 this makes 31 API calls instead of about 2 billion.

Pattern notes: Binary Search · Open on LeetCode

1Brute force — count up until the square is too big

Try 1, 2, 3, ... and stop just before the square passes x.

int mySqrt(int x) {
    long i = 0;
    while ((i + 1) * (i + 1) <= x) i++;    // grow while the next square still fits
    return (int) i;
}

Time O(√x)Space O(1)

For the biggest int that is about 46,000 steps. It passes, but binary search needs only about 31.

2Optimal — binary search for the last k that fits

int mySqrt(int x) {
    int lo = 0, hi = x;
    int ans = 0;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if ((long) mid * mid <= x) {       // long: mid * mid can overflow int
            ans = mid;                     // mid fits: a candidate
            lo = mid + 1;                  // try a bigger one
        } else {
            hi = mid - 1;                  // too big: go left
        }
    }
    return ans;
}

Time O(log x)Space O(1)

Same template again. "First yes" saves and goes left; "last yes" saves and goes right. That's the only difference.

Pattern notes: Binary Search · Open on LeetCode

1Brute force — try every k while k × k fits

Check 1 × 1, 2 × 2, 3 × 3, ... If one equals num, it is a square. Once the square passes num, stop.

boolean isPerfectSquare(int num) {
    for (long i = 1; i * i <= num; i++) {
        if (i * i == num) return true;
    }
    return false;
}

Time O(√n)Space O(1)

Fine for small numbers, but it walks one by one through a sorted range, which is exactly what binary search avoids.

2Optimal — exact-match binary search on k

boolean isPerfectSquare(int num) {
    int lo = 1, hi = num;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        long sq = (long) mid * mid;        // long, so it can't overflow
        if (sq == num) return true;        // exact hit
        else if (sq < num) lo = mid + 1;
        else hi = mid - 1;
    }
    return false;
}

Time O(log n)Space O(1)

At most about 31 rounds even for the largest int, and no floating-point rounding to worry about.

Pattern notes: Binary Search · Open on LeetCode

1Brute force — plain recursion, straight from the definition

The definition already says how to compute it: F(n) = F(n-1) + F(n-2), and the answer is known for n = 0 and n = 1 (the base cases, where the recursion stops).

int fib(int n) {
    if (n <= 1) return n;              // base cases: F(0) = 0, F(1) = 1
    return fib(n - 1) + fib(n - 2);    // two smaller calls
}

Time O(2ⁿ)Space O(n)

Every call makes two more calls, so the number of calls roughly doubles each level. fib(40) makes over 300 million calls, and most of them compute things that were already computed.

2Optimal — memoization: remember every answer once

int fib(int n) {
    int[] memo = new int[n + 1];
    Arrays.fill(memo, -1);              // -1 means "not computed yet"
    return solve(n, memo);
}

int solve(int n, int[] memo) {
    if (n <= 1) return n;
    if (memo[n] != -1) return memo[n];  // already in the notebook
    memo[n] = solve(n - 1, memo) + solve(n - 2, memo);
    return memo[n];                     // write it down, then return
}

Time O(n)Space O(n)

Each F(k) is computed once and then reused, so the work drops from exponential to a straight line. (You can even drop the array and keep only the last two values: see LC 70 below.)

Pattern notes: Recursion & the Call Stack · Open on LeetCode

1Brute force — keep dividing by 2

A power of two is 2 × 2 × ... × 2. So divide by 2 while the number is even. If you end up at exactly 1, it was a power of two.

boolean isPowerOfTwo(int n) {
    if (n <= 0) return false;           // 0 and negatives are never powers of two
    while (n % 2 == 0) n /= 2;          // strip every factor of 2
    return n == 1;
}

Time O(log n)Space O(1)

This is already fast (at most 31 divisions for an int). But there is a one-line answer that interviewers love, and it teaches a bit trick you will reuse.

2Optimal — one bit trick

boolean isPowerOfTwo(int n) {
    // n > 0 rules out 0 and negatives; the AND checks "exactly one 1-bit"
    return n > 0 && (n & (n - 1)) == 0;
}

Time O(1)Space O(1)

One subtraction and one AND, no loop at all.

Pattern notes: Bit Manipulation · Open on LeetCode

1Brute force — check all 32 bits one by one

An int has 32 bits. Shift each bit down to the last position and look at it with & 1.

int hammingWeight(int n) {
    int count = 0;
    for (int i = 0; i < 32; i++) {
        if (((n >>> i) & 1) == 1) count++;   // is bit i a 1?
    }
    return count;
}

Time O(32)Space O(1)

Always 32 steps, even for n = 128 which has a single 1-bit. We waste time looking at zeros.

2Optimal — jump straight from one 1-bit to the next

int hammingWeight(int n) {
    int count = 0;
    while (n != 0) {
        n &= n - 1;      // remove the lowest 1-bit
        count++;         // one 1-bit gone
    }
    return count;
}

Time O(number of 1s)Space O(1)

At most 32 turns, and far fewer when the number has few 1s. (Java also has Integer.bitCount(n), but interviewers want to see the trick.)

Pattern notes: Bit Manipulation · Open on LeetCode

1Brute force — count the bits of each number separately

For every i, peel off its bits one at a time and count the 1s, exactly like LC 191.

int[] countBits(int n) {
    int[] ans = new int[n + 1];
    for (int i = 0; i <= n; i++) {
        int x = i, count = 0;
        while (x != 0) {
            count += x & 1;   // last bit
            x >>= 1;          // drop it
        }
        ans[i] = count;
    }
    return ans;
}

Time O(n log n)Space O(1) extra

Each number costs about log n steps. The problem's follow-up asks for a single pass in O(n).

2Optimal — reuse the answer for i / 2

int[] countBits(int n) {
    int[] ans = new int[n + 1];          // ans[0] = 0 already
    for (int i = 1; i <= n; i++) {
        // bits of i = bits of (i without last bit) + the last bit
        ans[i] = ans[i >> 1] + (i & 1);
    }
    return ans;
}

Time O(n)Space O(1) extra

Because i >> 1 is always smaller than i, its answer is ready when we need it. This is a tiny Dynamic Programming problem.

Pattern notes: Bit Manipulation · Open on LeetCode

1Brute force — turn it into a String

Convert the number to text, then compare the first and last characters, moving inward with two pointers.

boolean isPalindrome(int x) {
    String s = String.valueOf(x);
    int l = 0, r = s.length() - 1;
    while (l < r) {
        if (s.charAt(l) != s.charAt(r)) return false;
        l++; r--;
    }
    return true;
}

Time O(d)Space O(d)

Here d is the number of digits. It works, but the follow-up asks: "could you solve it without converting the integer to a string?"

2Optimal — reverse only the second half of the digits

boolean isPalindrome(int x) {
    // negatives, and numbers ending in 0 (except 0 itself), can't be palindromes
    if (x < 0 || (x % 10 == 0 && x != 0)) return false;
    int rev = 0;
    while (x > rev) {
        rev = rev * 10 + x % 10;   // move the last digit of x onto rev
        x /= 10;                   // and remove it from x
    }
    // even length: x == rev; odd length: the middle digit sits at the end of rev
    return x == rev || x == rev / 10;
}

Time O(d)Space O(1)

We look at only half the digits and store just two ints, with no String and no overflow risk.

Pattern notes: Math & Number Theory · Open on LeetCode

1First way — recursion

The definition is already recursive: "left side, me, right side". So write a helper that does exactly that and let Java's call stack remember where to come back to.

List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> out = new ArrayList<>();
    walk(root, out);
    return out;
}

void walk(TreeNode node, List<Integer> out) {
    if (node == null) return;        // empty spot: nothing to do
    walk(node.left, out);            // 1. whole left side first
    out.add(node.val);               // 2. then me
    walk(node.right, out);           // 3. then whole right side
}

Time O(n)Space O(h)

This is already O(n) and perfectly fine. LeetCode's follow-up asks: "can you do it iteratively?" On a very deep tree (h close to n) recursion can overflow Java's stack, and interviewers like to see that you know what the recursion is doing behind the scenes.

2Iterative — your own stack

List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> out = new ArrayList<>();
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode cur = root;
    while (cur != null || !stack.isEmpty()) {
        while (cur != null) {          // slide left as far as possible,
            stack.push(cur);           // saving each node for later
            cur = cur.left;
        }
        cur = stack.pop();             // leftmost unvisited node
        out.add(cur.val);              // visit it
        cur = cur.right;               // then handle its right side
    }
    return out;
}

Time O(n)Space O(h)

Same big-O as recursion (be honest about that in an interview). The win is control: no risk of a StackOverflowError, and the same loop shape solves "kth smallest in a BST" and "BST iterator".

Pattern notes: Tree BFS & DFS · Open on LeetCode

1First way — recursion

Same helper as inorder, only the "visit me" line moves to the top.

List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> out = new ArrayList<>();
    walk(root, out);
    return out;
}

void walk(TreeNode node, List<Integer> out) {
    if (node == null) return;
    out.add(node.val);               // 1. me first
    walk(node.left, out);            // 2. then left side
    walk(node.right, out);           // 3. then right side
}

Time O(n)Space O(h)

Already O(n). As with inorder, the follow-up is "do it without recursion", which shows you understand the stack underneath.

2Iterative — push right, then left

List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> out = new ArrayList<>();
    if (root == null) return out;
    Deque<TreeNode> stack = new ArrayDeque<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        out.add(node.val);                              // visit on pop
        if (node.right != null) stack.push(node.right); // push RIGHT first...
        if (node.left != null) stack.push(node.left);   // ...so LEFT pops first
    }
    return out;
}

Time O(n)Space O(h)

Same O(n) as recursion, with an explicit stack instead of the call stack. Swap the stack for a queue and you get level-order (BFS) instead.

Pattern notes: Tree BFS & DFS · Open on LeetCode

1First way — count the levels (BFS)

Walk the tree one floor at a time with a queue, like counting floors in a building. Each time you finish a whole level, add one.

int maxDepth(TreeNode root) {
    if (root == null) return 0;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    int levels = 0;
    while (!queue.isEmpty()) {
        int size = queue.size();          // nodes on this level
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            if (node.left != null) queue.add(node.left);
            if (node.right != null) queue.add(node.right);
        }
        levels++;                         // finished one whole level
    }
    return levels;
}

Time O(n)Space O(w)

Correct and O(n), where w is the widest level. It just takes a lot of code for a simple question. Recursion says the same thing in three lines.

2Cleaner — ask the children (recursive DFS)

int maxDepth(TreeNode root) {
    if (root == null) return 0;                 // empty tree has depth 0
    int left = maxDepth(root.left);             // ask the left child
    int right = maxDepth(root.right);           // ask the right child
    return 1 + Math.max(left, right);           // me + the deeper side
}

Time O(n)Space O(h)

Both ways are O(n) time: every node must be seen once. The recursive version is shorter and uses O(h) stack instead of O(w) queue memory.

Pattern notes: Binary Trees · Open on LeetCode

1First way — build a mirrored copy

Make a brand new tree: each new node gets the mirror of the old right side as its left, and the mirror of the old left side as its right.

TreeNode invertTree(TreeNode root) {
    if (root == null) return null;
    TreeNode copy = new TreeNode(root.val);
    copy.left = invertTree(root.right);    // new left = mirrored old right
    copy.right = invertTree(root.left);    // new right = mirrored old left
    return copy;
}

Time O(n)Space O(n)

It works, but it allocates n new nodes. There's no need: we can just rewire the existing tree.

2Optimal — swap in place

TreeNode invertTree(TreeNode root) {
    if (root == null) return null;
    TreeNode temp = root.left;        // swap my two children
    root.left = root.right;
    root.right = temp;
    invertTree(root.left);            // then fix each subtree the same way
    invertTree(root.right);
    return root;
}

Time O(n)Space O(h)

Still O(n) time (every node must be swapped), but no new nodes: only the recursion stack, O(h).

Pattern notes: Binary Trees · Open on LeetCode

1Brute force — turn both trees into strings

Write each tree out as text in preorder, marking empty spots with #, then compare the two strings.

boolean isSameTree(TreeNode p, TreeNode q) {
    return serialize(p).equals(serialize(q));
}

String serialize(TreeNode node) {
    if (node == null) return "#";                  // mark empty spots!
    return node.val + "," + serialize(node.left) + "," + serialize(node.right);
}

Time O(n)Space O(n)

It builds two whole strings (and lots of temporary ones along the way) even when the roots already differ. We can compare directly and stop at the first difference.

2Optimal — walk both trees together

boolean isSameTree(TreeNode p, TreeNode q) {
    if (p == null && q == null) return true;     // both empty: same
    if (p == null || q == null) return false;    // only one empty: different
    if (p.val != q.val) return false;            // different values
    return isSameTree(p.left, q.left)            // left sides must match
        && isSameTree(p.right, q.right);         // and right sides too
}

Time O(n)Space O(h)

Worst case still visits every node (when the trees are equal), but it uses only the recursion stack and quits early on the first mismatch.

Pattern notes: Binary Trees · Open on LeetCode

1Brute force — every level must read the same both ways

Go level by level with a queue, write down each level's values (with null for gaps), and check each level is a palindrome.

boolean isSymmetric(TreeNode root) {
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    while (!queue.isEmpty()) {
        int size = queue.size();
        List<Integer> level = new ArrayList<>();
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            if (node == null) { level.add(null); continue; }   // keep gaps!
            level.add(node.val);
            queue.add(node.left);
            queue.add(node.right);
        }
        for (int i = 0, j = level.size() - 1; i < j; i++, j--) {
            if (!Objects.equals(level.get(i), level.get(j))) return false;
        }
    }
    return true;
}

Time O(n)Space O(n)

Correct, but it stores whole levels (including null placeholders) and always finishes a level before checking. The recursive mirror check is shorter and stops at the first mismatch.

2Optimal — compare the two halves as mirrors

boolean isSymmetric(TreeNode root) {
    return isMirror(root.left, root.right);
}

boolean isMirror(TreeNode a, TreeNode b) {
    if (a == null && b == null) return true;
    if (a == null || b == null) return false;
    return a.val == b.val
        && isMirror(a.left, b.right)     // outside pair
        && isMirror(a.right, b.left);    // inside pair
}

Time O(n)Space O(h)

Each node is compared once with its mirror partner. Memory is just the recursion depth.

Pattern notes: Binary Trees · Open on LeetCode

1Brute force — collect every path sum

Walk every root-to-leaf path, write each total into a list, and at the end ask the list whether it contains the target.

boolean hasPathSum(TreeNode root, int targetSum) {
    List<Integer> sums = new ArrayList<>();
    collect(root, 0, sums);
    return sums.contains(targetSum);
}

void collect(TreeNode node, int soFar, List<Integer> sums) {
    if (node == null) return;
    soFar += node.val;
    if (node.left == null && node.right == null) sums.add(soFar);  // a leaf: path done
    collect(node.left, soFar, sums);
    collect(node.right, soFar, sums);
}

Time O(n)Space O(n)

It stores one number per leaf (up to about n/2) and always walks the entire tree, even if the very first path already hits the target.

2Optimal — subtract as you go down

boolean hasPathSum(TreeNode root, int targetSum) {
    if (root == null) return false;                  // no path here
    int remaining = targetSum - root.val;            // pay for this node
    if (root.left == null && root.right == null) {   // leaf: path ends here
        return remaining == 0;
    }
    return hasPathSum(root.left, remaining)          // try left...
        || hasPathSum(root.right, remaining);        // ...or right (stops at first true)
}

Time O(n)Space O(h)

Worst case it still visits every node, but it keeps no list and returns the moment a good path is found.

Pattern notes: Binary Trees · Open on LeetCode

1Brute force — at every node, measure both heights

Any longest path "bends" at some top node. So for every node, compute the height of its left side plus the height of its right side, and keep the largest. Height is computed from scratch each time.

int diameterOfBinaryTree(TreeNode root) {
    if (root == null) return 0;
    int throughMe = height(root.left) + height(root.right);   // path bending at root
    int best = Math.max(diameterOfBinaryTree(root.left),
                        diameterOfBinaryTree(root.right));   // or entirely inside a subtree
    return Math.max(throughMe, best);
}

int height(TreeNode node) {          // counts nodes on the longest way down
    if (node == null) return 0;
    return 1 + Math.max(height(node.left), height(node.right));
}

Time O(n²)Space O(h)

Each call to height re-walks a whole subtree, and we call it at every node. On a long skinny tree that's about n²/2 steps: the same heights get recomputed over and over.

2Optimal — one pass: return height, record diameter

private int best = 0;                    // longest path found so far (in edges)

int diameterOfBinaryTree(TreeNode root) {
    height(root);
    return best;
}

int height(TreeNode node) {
    if (node == null) return 0;
    int left = height(node.left);        // how far down on the left
    int right = height(node.right);      // how far down on the right
    best = Math.max(best, left + right); // path that bends at this node
    return 1 + Math.max(left, right);    // tell my parent my height
}

Time O(n)Space O(h)

Every node is visited exactly once, and each height is computed once and reused by the parent.

Pattern notes: Binary Trees · Open on LeetCode

1First way — split the array into copies

The middle value must be the root (half the values are smaller, half bigger). Then do the same for the left half and the right half, making a new small array for each.

TreeNode sortedArrayToBST(int[] nums) {
    if (nums.length == 0) return null;
    int mid = nums.length / 2;
    TreeNode root = new TreeNode(nums[mid]);
    root.left = sortedArrayToBST(Arrays.copyOfRange(nums, 0, mid));                // new array
    root.right = sortedArrayToBST(Arrays.copyOfRange(nums, mid + 1, nums.length)); // new array
    return root;
}

Time O(n log n)Space O(n log n)

The idea is right, but every level of recursion copies about n numbers in total, and there are log n levels. Copying is wasted work: the numbers are already sitting in the original array.

2Optimal — same idea, with index bounds

TreeNode sortedArrayToBST(int[] nums) {
    return build(nums, 0, nums.length - 1);
}

TreeNode build(int[] nums, int lo, int hi) {
    if (lo > hi) return null;                 // empty range: no node
    int mid = lo + (hi - lo) / 2;             // middle = root of this range
    TreeNode root = new TreeNode(nums[mid]);
    root.left = build(nums, lo, mid - 1);     // left half builds left subtree
    root.right = build(nums, mid + 1, hi);    // right half builds right subtree
    return root;
}

Time O(n)Space O(log n)

Each value becomes exactly one node. Because we always split in the middle, the recursion is only log n deep.

Pattern notes: Binary Search Trees · Open on LeetCode

1Brute force — search everywhere

Treat it like any binary tree: check this node, then search the left side, and if that fails search the right side.

TreeNode searchBST(TreeNode root, int val) {
    if (root == null) return null;
    if (root.val == val) return root;
    TreeNode found = searchBST(root.left, val);   // look left...
    if (found != null) return found;
    return searchBST(root.right, val);            // ...and right, no matter what
}

Time O(n)Space O(h)

It ignores the one thing that makes a BST special: its ordering. It can end up looking at every node.

2Optimal — follow the BST rule down one path

TreeNode searchBST(TreeNode root, int val) {
    TreeNode cur = root;
    while (cur != null && cur.val != val) {
        cur = (val < cur.val) ? cur.left : cur.right;   // throw away the wrong half
    }
    return cur;   // the node, or null if we fell off the tree
}

Time O(h)Space O(1)

We follow a single path from the root, so the cost is the tree's height: about log n for a balanced BST. The loop needs no stack at all.

Pattern notes: Binary Search Trees · Open on LeetCode

1Brute force — sort before every smash

Keep the stones in a list. Each round, sort it, take the two at the end, and put the leftover back.

int lastStoneWeight(int[] stones) {
    List<Integer> list = new ArrayList<>();
    for (int s : stones) list.add(s);
    while (list.size() > 1) {
        Collections.sort(list);                          // sort EVERY round
        int y = list.remove(list.size() - 1);            // heaviest
        int x = list.remove(list.size() - 1);            // second heaviest
        if (y != x) list.add(y - x);
    }
    return list.isEmpty() ? 0 : list.get(0);
}

Time O(n² log n)Space O(n)

Up to n rounds, each with a full sort. We re-sort the whole list just to find the top two, even though only one number changed.

2Optimal — a max-heap

int lastStoneWeight(int[] stones) {
    PriorityQueue<Integer> heap = new PriorityQueue<>(Collections.reverseOrder()); // max-heap
    for (int s : stones) heap.add(s);
    while (heap.size() > 1) {
        int y = heap.poll();            // heaviest
        int x = heap.poll();            // second heaviest
        if (y != x) heap.add(y - x);    // leftover piece goes back in
    }
    return heap.isEmpty() ? 0 : heap.peek();
}

Time O(n log n)Space O(n)

At most n rounds, each doing a few O(log n) heap operations.

Pattern notes: Heaps & Priority Queues · Open on LeetCode

1Brute force — keep everything and sort

Store every number. On each add, sort the list and read the k-th from the end.

class KthLargest {
    private final int k;
    private final List<Integer> all = new ArrayList<>();

    public KthLargest(int k, int[] nums) {
        this.k = k;
        for (int n : nums) all.add(n);
    }

    public int add(int val) {
        all.add(val);
        Collections.sort(all);                 // re-sort everything each time
        return all.get(all.size() - k);        // k-th from the end
    }
}

Time O(n log n) per addSpace O(n)

The list keeps growing forever, and each add re-sorts all of it. But we only ever care about the top k numbers.

2Optimal — a min-heap that holds only the top k

class KthLargest {
    private final int k;
    private final PriorityQueue<Integer> heap = new PriorityQueue<>(); // min-heap

    public KthLargest(int k, int[] nums) {
        this.k = k;
        for (int n : nums) add(n);
    }

    public int add(int val) {
        heap.add(val);
        if (heap.size() > k) heap.poll();      // kick out the smallest
        return heap.peek();                    // smallest of the top k = k-th largest
    }
}

Time O(log k) per addSpace O(k)

The heap never grows past k + 1, so each add is O(log k) no matter how many numbers have streamed in.

Pattern notes: Heaps & Priority Queues · Open on LeetCode

1Brute force — sweep the whole grid again and again

Mark the start cell as "in the region". Then scan every cell: if it has the original colour and touches a marked cell, mark it too. Repeat full scans until one scan adds nothing. Finally, paint every marked cell.

int[][] floodFill(int[][] image, int sr, int sc, int color) {
    int m = image.length, n = image[0].length, start = image[sr][sc];
    boolean[][] inRegion = new boolean[m][n];
    inRegion[sr][sc] = true;
    boolean changed = true;
    while (changed) {                                // one full sweep per loop
        changed = false;
        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                if (inRegion[r][c] || image[r][c] != start) continue;
                boolean touches = (r > 0 && inRegion[r-1][c]) || (r < m-1 && inRegion[r+1][c])
                               || (c > 0 && inRegion[r][c-1]) || (c < n-1 && inRegion[r][c+1]);
                if (touches) { inRegion[r][c] = true; changed = true; }
            }
        }
    }
    for (int r = 0; r < m; r++)
        for (int c = 0; c < n; c++)
            if (inRegion[r][c]) image[r][c] = color;
    return image;
}

Time O((m·n)²)Space O(m·n)

A long snake-shaped region may grow by only one cell per sweep, so we can end up scanning the whole grid once for every cell.

2Optimal — DFS: spread from the start like paint

int[][] floodFill(int[][] image, int sr, int sc, int color) {
    int start = image[sr][sc];
    if (start == color) return image;      // nothing to do (and avoids an endless loop)
    dfs(image, sr, sc, start, color);
    return image;
}

void dfs(int[][] image, int r, int c, int start, int color) {
    if (r < 0 || r >= image.length || c < 0 || c >= image[0].length) return; // off the grid
    if (image[r][c] != start) return;      // wall, or already painted
    image[r][c] = color;                   // paint first = mark as visited
    dfs(image, r + 1, c, start, color);    // down
    dfs(image, r - 1, c, start, color);    // up
    dfs(image, r, c + 1, start, color);    // right
    dfs(image, r, c - 1, start, color);    // left
}

Time O(m·n)Space O(m·n)

Each cell is painted at most once. The space is the recursion stack, which in the worst case holds every cell.

Pattern notes: Matrix & Islands · Open on LeetCode

1Brute force — test every person as the judge

For each person, scan the whole trust list: do they trust anyone? How many people trust them? The judge trusts nobody and is trusted by n - 1 people.

int findJudge(int n, int[][] trust) {
    for (int cand = 1; cand <= n; cand++) {
        boolean trustsSomeone = false;
        int trustedBy = 0;
        for (int[] t : trust) {
            if (t[0] == cand) trustsSomeone = true;
            if (t[1] == cand) trustedBy++;
        }
        if (!trustsSomeone && trustedBy == n - 1) return cand;
    }
    return -1;
}

Time O(n · t)Space O(1)

Here t is the length of trust. We re-read the whole list for every person, even though one read already tells us everything.

2Optimal — one pass with a trust score

int findJudge(int n, int[][] trust) {
    int[] score = new int[n + 1];          // index = person label (1..n)
    for (int[] t : trust) {
        score[t[0]]--;                     // a trusts someone: can't be the judge
        score[t[1]]++;                     // b is trusted by one more person
    }
    for (int i = 1; i <= n; i++) {
        if (score[i] == n - 1) return i;
    }
    return -1;
}

Time O(n + t)Space O(n)

One pass over the pairs and one pass over the people. Any single "out" arrow drops a person below n − 1 for good.

Pattern notes: Graphs & Traversal · Open on LeetCode

1Brute force — keep sweeping the edge list

Mark the source as reachable. Go through every edge: if one end is reachable and the other is not, mark the other. Repeat full sweeps until nothing new gets marked.

boolean validPath(int n, int[][] edges, int source, int destination) {
    boolean[] reach = new boolean[n];
    reach[source] = true;
    boolean changed = true;
    while (changed) {
        changed = false;
        for (int[] e : edges) {
            if (reach[e[0]] != reach[e[1]]) {      // exactly one end reachable
                reach[e[0]] = reach[e[1]] = true;
                changed = true;
            }
        }
    }
    return reach[destination];
}

Time O(n · E)Space O(n)

Each sweep may add just one node, so we can sweep all E edges up to n times. With 200,000 nodes and edges that is far too slow.

2Optimal — adjacency list + BFS

boolean validPath(int n, int[][] edges, int source, int destination) {
    List<List<Integer>> adj = new ArrayList<>();
    for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
    for (int[] e : edges) {                // two-way road: add both directions
        adj.get(e[0]).add(e[1]);
        adj.get(e[1]).add(e[0]);
    }
    boolean[] visited = new boolean[n];
    Queue<Integer> queue = new ArrayDeque<>();
    queue.offer(source);
    visited[source] = true;                // mark when you ADD to the queue
    while (!queue.isEmpty()) {
        int node = queue.poll();
        if (node == destination) return true;
        for (int next : adj.get(node)) {
            if (!visited[next]) {
                visited[next] = true;
                queue.offer(next);
            }
        }
    }
    return false;                          // ran out of places to go
}

Time O(n + E)Space O(n + E)

Every node enters the queue at most once, and every edge is looked at twice (once from each end).

Pattern notes: Graphs & Traversal · Open on LeetCode

1Brute force — for each child, search all cookies

Go through the children from least to most greedy. For each one, scan every cookie and give them the smallest unused cookie that is big enough.

int findContentChildren(int[] g, int[] s) {
    Arrays.sort(g);                         // least greedy child first
    boolean[] used = new boolean[s.length];
    int content = 0;
    for (int child : g) {
        int best = -1;
        for (int j = 0; j < s.length; j++) {   // find the smallest cookie that fits
            if (!used[j] && s[j] >= child && (best == -1 || s[j] < s[best])) best = j;
        }
        if (best != -1) { used[best] = true; content++; }
    }
    return content;
}

Time O(n · m)Space O(m)

The choice is right, but finding the smallest fitting cookie costs a full scan of all m cookies for every child.

2Optimal — sort both, walk with two pointers

int findContentChildren(int[] g, int[] s) {
    Arrays.sort(g);
    Arrays.sort(s);
    int child = 0, cookie = 0;
    while (child < g.length && cookie < s.length) {
        if (s[cookie] >= g[child]) child++;   // fits: this child is happy
        cookie++;                             // this cookie is used or useless
    }
    return child;                             // number of happy children
}

Time O(n log n + m log m)Space O(1) extra

Sorting is the only expensive part; after that one walk over both arrays finishes the job.

Pattern notes: Greedy · Open on LeetCode

1Brute force — keep every bill in a list and search it

Put every bill you receive into a list (your cash drawer). When you owe change, search the drawer for the largest bill that still fits, remove it, and repeat until the change is paid.

boolean lemonadeChange(int[] bills) {
    List<Integer> drawer = new ArrayList<>();
    for (int bill : bills) {
        int change = bill - 5;
        while (change > 0) {                     // pay the change bill by bill
            int pick = -1;
            for (int i = 0; i < drawer.size(); i++) {
                int b = drawer.get(i);
                if (b <= change && (pick == -1 || b > drawer.get(pick))) pick = i;
            }
            if (pick == -1) return false;        // no bill fits: can't make change
            change -= drawer.remove(pick);
        }
        drawer.add(bill);
    }
    return true;
}

Time O(n²)Space O(n)

The drawer grows with every customer and we search all of it each time. But a $20 bill is never useful as change here, and all $5 bills are the same, so we only need to know how many of each we have.

2Optimal — count the $5 and $10 bills

boolean lemonadeChange(int[] bills) {
    int five = 0, ten = 0;
    for (int bill : bills) {
        if (bill == 5) {
            five++;                                // no change needed
        } else if (bill == 10) {
            if (five == 0) return false;           // need one $5 back
            five--; ten++;
        } else {                                   // $20: need $15 back
            if (ten > 0 && five > 0) { ten--; five--; }   // prefer 10 + 5
            else if (five >= 3) { five -= 3; }            // else 5 + 5 + 5
            else return false;
        }
    }
    return true;
}

Time O(n)Space O(1)

Two counters replace the whole drawer, and each customer takes a constant number of steps.

Pattern notes: Greedy · Open on LeetCode

1Brute force — plain recursion

Think about your last move. To stand on step n, you came either from step n − 1 (a 1-step) or from step n − 2 (a 2-step). So the ways to reach n = ways to reach n − 1 + ways to reach n − 2.

int climbStairs(int n) {
    if (n <= 2) return n;                        // 1 way to reach step 1, 2 ways to reach step 2
    return climbStairs(n - 1) + climbStairs(n - 2);
}

Time O(2ⁿ)Space O(n)

This is Fibonacci in disguise, with the same exploding recursion tree as LC 509: n = 45 makes over a billion calls.

2Optimal — bottom-up, keep only the last two answers