Arrays & Strings

10 cards, about a minute. Read them the night before an interview, or right after the chapter to lock it in.

1. ◆what it is

   An array is one block of equal-sized slots: arr[i] lives at base + i × size, so reading any index is O(1).

   #1
2. O( )cost

   Index O(1) · ArrayList append O(1) amortized · insert/delete in the middle O(n) · search unsorted O(n).

   #2
3. ↯use it when

   Subarray max → Kadane. Except-self → prefix/suffix. Letters → int[26]. More than n/2 → vote. Values 1..n → index v − 1.

   #3
4. { }template

   Kadane: cur = Math.max(x, cur + x); best = Math.max(best, cur); — start both at nums[0].

   #4
5. { }template

   Next permutation: pivot = first dip from the right → swap with the rightmost bigger value → reverse the suffix.

   #5
6. !trap

   s += c in a loop is O(n²): every += copies the whole string. Build with StringBuilder, call toString() once.

   #6
7. !trap

   list.remove(7) on a List<Integer> removes index 7, not the value 7. Write remove(Integer.valueOf(7)).

   #7
8. !trap

   Rotate by k: k %= n first. Circular max: all-negative input must return the Kadane max, not total − min.

   #8
9. ✦pro tip

   Before a nested loop, ask: one pass + a few running variables? Running min, best-ending-here, a vote counter.

   #9
10. ✦pro tip

    O(1) space asked? Reverse in place, use the output array as scratch, or let index v − 1 remember value v.

    #10

Shaky on a card? Open the chapter or flip its recall cards.