Arrays & Strings
One contiguous block of memory — the structure every other structure is built on.
▶ guided lesson⚡ 1-minute summary↻ 14 recall cards
before this: Big-O · Java Toolkit
01 · why it exists
Why this exists, and the weight it carries
since1957
Array (contiguous memory)
John Backus and the IBM FORTRAN team
Early programmers kept tables in numbered memory words and worked out every address by hand.
FORTRAN, built at IBM from 1954 and described in 1957, made the array part of the language: DIMENSION A(1000) declares 1000 slots, and A(I) reads one.
The compiler turns the subscript into an address, so programmers never do that arithmetic again.
C, Java and almost every language since kept the same idea: a numbered row of equal-sized slots.
the problem it solvedKeeping many values of one kind under one name and reaching any of them by its number, without hand-written address arithmetic.
its jobs today
- Every
ArrayList,ArrayDeque,HashMaptable andStringin Java stores its data in a plain array underneath. - Images and video frames are arrays of pixels: a 1920 × 1080 screen is 20,73,600 pixel slots, each found by row × width + column.
- Walking an array in order is the fastest memory access a CPU can do, because caches fetch neighbouring bytes together.
the weight it carries
Illustrative: an int[] of 10 lakh (1,000,000) order amounts. Reading index 7,43,210 is one multiply and one add: base + 743,210 × 4 bytes. Finding the value ₹4,999 instead means checking up to 1,000,000 slots, and inserting at the front shifts all 1,000,000.
without it
No O(1) access by position: every lookup would walk node by node, and everything built on arrays — hash tables, heaps, ArrayList — would lose its speed.
when · why · how
- when
- You know (or can bound) how many values there are, and you read or write them by position.
- why
- O(1) read/write by index and the best cache behaviour of any structure. The price: a fixed size, and O(n) to insert or delete in the middle.
- how
int[] a = new int[n];— filled with 0s;a.lengthis a field. UseArrays.fill,Arrays.sortandSystem.arraycopyfor bulk work.
since1985 · 1998
Dynamic array (ArrayList)
Robert E. Tarjan (amortized analysis); the JDK 1.2 Collections Framework team (ArrayList)
Arrays that copy themselves into a bigger block when full are older than any name for the trick.
In 1985 Robert Tarjan's survey "Amortized Computational Complexity" set out amortized analysis, the honest way to price arrays like these: spread the rare, expensive copy over the many cheap appends.
Java 1.2 (December 1998) shipped ArrayList in its new Collections Framework.
In OpenJDK it grows by about 1.5× when full, and since Java 8 (and 7u40) an empty list allocates its first 10 slots only on the first add.
the problem it solvedLists whose final size nobody knows in advance, with O(1) access by index and appends that are cheap on average.
its jobs today
ArrayListis the defaultListin Java code: query results, parsed JSON arrays, API responses.StringBuilder,ArrayDequeandHashMap's bucket table all grow the same way: allocate a bigger array, copy, carry on.
the weight it carries
Illustrative: appending 10 lakh items to a list that doubles from capacity 1. Copies happen at sizes 1, 2, 4, …, 524,288: 1 + 2 + … + 524,288 = 1,048,575 copied elements — about one extra copy per append. Pre-sizing with new ArrayList<>(1_000_000) makes it zero.
without it
You would guess every list's size up front, or copy on every single append: 10 lakh appends would copy 0 + 1 + … + 999,999 ≈ 5 × 10¹¹ elements.
when · why · how
- when
- The number of items isn't known up front, and you mostly append and read by index.
- why
- Amortized O(1) append and O(1) get/set. Inserting or removing in the middle is still O(n), and each element is a boxed object — more memory than
int[]. - how
List<Integer> list = new ArrayList<>(expected);thenadd,get(i),set(i, x). Remove a value withremove(Integer.valueOf(x));remove(i)removes an index.
since1996 · 2004
Immutable String & StringBuilder
Sun Microsystems' Java team (JDK 1.0 `String`); JDK 5 (`StringBuilder`)
Java 1.0 (1996) made String immutable: once created, its characters never change, so one string can be shared safely.
The mutable helper was StringBuffer, whose methods are synchronized.
Java 5 (2004) added StringBuilder: the same methods without the locking, meant for single-threaded code.
Later, Java 7u6 made substring copy its characters, and Java 9's Compact Strings store Latin-1 text in one byte per character.
the problem it solvedText that is safe to share and to use as a map key — plus a cheap way to build new text piece by piece.
its jobs today
- Log lines, JSON responses and CSV exports are built piece by piece —
StringBuilderkeeps that O(n). Stringkeys in aHashMap: because a string never changes, its hash code never changes after you insert it.
the weight it carries
Illustrative: building a 1 lakh (100,000)-character CSV line with s += c. Each += copies the whole string so far: 1 + 2 + … + 100,000 ≈ 5 × 10⁹ character copies. With StringBuilder (16 slots to start, then 2 × old + 2): 100,000 writes plus 1,47,412 characters copied across 13 growths — about 2.5 × 10⁵ in total, roughly 20,000 times less work.
without it
A mutable String used as a HashMap key could change and be lost in the wrong bucket; and without StringBuilder, building text in a loop would be quadratic.
when · why · how
- when
Stringfor text you store, compare or use as a key;StringBuilderwhenever you build text in a loop.- why
- A
Stringis safe to share and hash, but every change makes an O(n) copy.StringBuilderappends in amortized O(1), so building n characters costs O(n) instead of O(n²). - how
StringBuilder sb = new StringBuilder(); sb.append(x); … return sb.toString();Compare with.equals, read withcharAt(i), and usetoCharArray()when you need to modify characters.
since?
Counting array (int[26])
Indexing an array by the value itself is programming folklore with no single inventor. Its best-known relative is counting sort: CLRS (Chapter 8 notes) reports that Knuth credits H. H. Seward with inventing counting sort in 1954.
its jobs today
- Word games and anagram solvers compare letter counts to spot anagrams without sorting.
- Counting sort and radix sort count keys in an array instead of comparing them — that's how they beat O(n log n) for small key ranges.
the weight it carries
Illustrative: are two 50,000-letter strings anagrams? Sorting both: about 2 × 50,000 × log₂ 50,000 ≈ 16 lakh comparisons. Counting: 1,00,000 array updates plus a check of 26 slots.
without it
Every "same letters?" question would need a sort (O(n log n)) or a HashMap that hashes and boxes every single character.
when · why · how
- when
- The keys are small, dense integers: lowercase letters (26), ASCII (128), digits (10), or values in a known small range.
- why
- O(1) per update with no hashing or boxing and O(k) space for k possible keys — usually several times faster than a HashMap.
- how
int[] count = new int[26]; count[c - 'a']++;Useint[128]indexed by the char itself for mixed case, and aHashMapfor full Unicode.
since1977–1984
Kadane's algorithm
Ulf Grenander (posed it), Michael Shamos, Jay Kadane (linear scan); told by Jon Bentley
Ulf Grenander at Brown University met the maximum-subarray problem while working on pattern matching in digitised images; in 1977 he described it to Michael Shamos. Shamos found an O(n log n) divide-and-conquer solution overnight. When Shamos described the problem at a Carnegie Mellon seminar a few days later, statistician Jay Kadane designed the linear-time scan within about a minute — as Jon Bentley tells it. Bentley's Programming Pearls column (CACM, September 1984) made the story famous. Kadane published his own account in 2023, noting that the version taught today differs slightly from the one he intended (only on all-negative input).
the problem it solvedFinding the best contiguous stretch of numbers — positive and negative mixed — in one pass instead of trying every start and end.
its jobs today
- Analytics: the most profitable run of days in a profit-and-loss sheet, with loss days mixed in between.
- Any "best stretch" question over a stream — the running best-ending-here value needs only O(1) memory.
the weight it carries
Illustrative: 10 lakh daily profit/loss values. Trying every start and end: about n²/2 = 5 × 10¹¹ sums. Kadane: 10 lakh steps, one pass.
without it
"Best stretch" questions over big data would cost O(n²), or O(n log n) with the much longer divide-and-conquer code.
when · why · how
- when
- "Maximum (or minimum) sum of a contiguous subarray", or any best-ending-here running decision.
- why
- O(n) time and O(1) space versus O(n²) for all pairs — and, unlike a sliding window, it works with negative numbers.
- how
cur = Math.max(x, cur + x); best = Math.max(best, cur);— start both atnums[0], never at 0.
since?
Prefix & suffix passes
Running totals from the left and from the right are as old as bookkeeping; there is no single inventor to credit. In interviews the technique is known from problems like Product of Array Except Self and Trapping Rain Water.
its jobs today
- Answers of the form "everything except me" or "best to my left and best to my right" — products, maximums, sums.
- Spreadsheets do it every day: a running-total column from the top, and another from the bottom.
the weight it carries
Illustrative: 1 lakh numbers and the product of all the others for each one. Multiplying the other 99,999 for each index: about 10¹⁰ multiplications. One left pass plus one right pass: about 3 lakh.
without it
Every "except i" answer would redo the whole array for each i — O(n²) — or need division, which breaks on zeros.
when · why · how
- when
- The answer at i combines something about everything left of i with something about everything right of i.
- why
- Two O(n) passes replace an O(n²) double loop; the output array can hold one side, so extra space stays O(1).
- how
- Fill
answer[i]with the left product, then sweep from the right with one variable:answer[i] *= right; right *= nums[i];.
since1980
Boyer–Moore majority vote
Robert S. Boyer & J Strother Moore
Boyer and Moore devised the algorithm in 1980; a University of Texas technical report followed in 1981. They framed it as counting votes in an election, with fault-tolerant hardware — redundant units voting on an answer — as one use. The report notes it suits data on magnetic tape: it reads the votes in order and keeps just two variables. The paper was published in 1991, in a book of essays honouring Woody Bledsoe.
the problem it solvedFinding the value that more than half the votes agree on, in one pass with constant memory — no table of counts.
its jobs today
- Redundant systems: several replicas compute the same answer and the value most of them agree on wins.
- Streams too big to store: find a dominant item in one pass with constant memory (the n/k version is the Misra–Gries frequent-items algorithm).
the weight it carries
Illustrative: 10 crore (100,000,000) request ids streamed past, one of them a majority. A HashMap of counts may grow to millions of boxed entries; the vote keeps one candidate and one counter for the whole stream.
without it
Finding a majority in O(1) memory would mean sorting first (O(n log n)) or a linear-time median-finding algorithm — both rearrange the data and need values that can be ordered, while the vote only checks equality.
when · why · how
- when
- One value is guaranteed (or suspected) to fill more than half the input, and memory is tight or the data is a stream.
- why
- O(n) time and O(1) space; a HashMap count is also O(n) but needs O(n) memory. Without a guaranteed majority, add a second pass to verify the survivor.
- how
if (count == 0) candidate = x; count += (x == candidate) ? 1 : -1;— then returncandidate.
since1356
Next lexicographic permutation
Nārāyaṇa Paṇḍita (India); traced by Donald Knuth
In 1356 the Indian mathematician Nārāyaṇa Paṇḍita wrote Gaṇita Kaumudī, which gives rules for listing permutations one after another.
Donald Knuth's The Art of Computer Programming (§7.2.1.2, Algorithm L) traces the lexicographic-permutation algorithm back to Nārāyaṇa.
Knuth notes it has been rediscovered many times since — today C++ ships it as std::next_permutation.
the problem it solvedStepping through every ordering of a list in sorted order, one step at a time, with no extra memory.
its jobs today
- C++'s
std::next_permutationlets programs loop over every ordering of a container in sorted order. - Brute-force search over small orderings — seating plans, the order of 8 delivery stops, test cases — without recursion or extra memory.
the weight it carries
Illustrative: all orderings of 10 delivery stops = 10! = 36,28,800 arrangements. Each next-permutation step costs at most about 3 × 10 element touches and no extra memory; building all n! arrangements to pick one successor costs O(n! · n).
without it
"What comes next?" would mean generating and sorting every arrangement — impossible beyond about n = 10.
when · why · how
- when
- You need the next ordering in dictionary order: the next bigger number with the same digits, or a walk through all orderings.
- why
- O(n) per step and O(1) memory, versus O(n! · n) to list everything and search it.
- how
- Scan right-to-left for the pivot
nums[i] < nums[i + 1], swap it with the rightmost bigger value, then reversei + 1 .. n − 1with two pointers.
since?
Index as home (cyclic placement, sign markers)
Using an array's own indices as a lookup table for values 1..n is folklore from programming puzzles and interviews; we found no single inventor to credit.
its jobs today
- Memory-tight checks on numbers that should run 1..n: find missing or repeated ticket, seat or invoice numbers in place.
- Applying a permutation in place: follow each value to its home slot, cycle by cycle, instead of copying into a second array.
the weight it carries
Illustrative: 10 lakh invoice numbers that should run 1..10,00,000. A HashSet<Integer> holds up to 10 lakh boxed Integers — tens of megabytes. Cyclic placement reuses the array you already have, with at most 10 lakh swaps.
without it
Questions like First Missing Positive in O(1) extra memory would fall back to sorting the data first (O(n log n)) — or a HashSet with O(n) memory.
when · why · how
- when
- Values that matter lie in 1..n for an array of length n, and the problem asks for O(1) extra space.
- why
- O(n) time — every swap settles one value for good — and O(1) space, versus O(n) for a HashSet. The price: the input array is rearranged.
- how
while (nums[i] >= 1 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) swap(i, nums[i] - 1);then scan for the firstnums[i] != i + 1.
02 · plain english
The idea in 30 seconds
An array is a row of equal-sized boxes laid side by side in memory, numbered from 0.
Because every box is the same size, the computer calculates where box i is — so reading any index is O(1).
The price: the row can't stretch in the middle. Inserting or deleting means shifting everything after it — O(n).
picture this
An Excel column. Type A37 in the Name Box and you land on row 37 instantly — Excel never scrolls past rows 1 to 36. But right-click row 3 → Insert, and every row from 3 down has to move one step lower. Jump = O(1), insert in the middle = O(n).
03 · remember
What you must know
- Contiguous memory:
arr[i]lives atbase + i × elementSize. One multiply and one add — that's why indexing is O(1). - Static vs dynamic:
int[]has a fixed length.ArrayListwraps an array and copies it into a bigger one when full — appends are amortized O(1). - Shifting is the hidden cost: insert/delete at index i moves n − i elements. Front = O(n), end = O(1).
- Strings are immutable in Java.
s += xin a loop builds a new String each time → O(n²). UseStringBuilder→ O(n). - Characters are numbers:
c - 'a'maps 'a'..'z' to 0..25, so anint[26]is a tiny, fast hash map for letter counts. - 2D arrays in Java are arrays of row arrays:
grid[r][c]. The Matrices & Simulation chapter turns them into grids you rotate, spiral and simulate in place. - Running state beats nested loops: keep a running min, max, sum, product or vote while you scan (Kadane, stock, prefix products, Boyer–Moore) to turn O(n²) into O(n).
- In-place tricks: reversal, swapping, using the output array as scratch space, or letting index v − 1 remember value v give O(1) extra memory.
04 · see it
Play with it in 3D
Press Space to play, ←/→ to step, drag to move, ? for all shortcuts. Try your own input.
Why arr[i] is O(1) — memory addresses
Each slot sits 4 bytes after the previous one, so the address is computed, never searched for.
Insert in the middle — watch everything shift
To open a gap at index i, every element from i to the end moves one step right.
How a dynamic array grows (doubling)
Copies happen only at sizes 1, 2, 4, 8 … — the total stays under 2n, so each append is amortized O(1).
A frequency array int[26]
Letters become indices with `c - 'a'`. s adds one, t takes one away; anagrams end at all zeros.
Kadane's algorithm — extend or restart
A negative running sum can only hurt what comes next, so drop it and start fresh.
Boyer–Moore voting — different values cancel out
One candidate, one counter. Every different value knocks out one vote; the majority is the only value that can survive.
05 · cost
Time & space, explained
| int[] | ArrayList | why | |
|---|---|---|---|
| Read / write by index | O(1) | O(1) | The address is base + i × size: arithmetic, not a search. |
| Append at the end | — (fixed size) | O(1) amortized | Usually a free slot exists; the rare O(n) copy is spread over many appends. |
| Insert / delete at index i | O(n) | O(n) | Everything after i shifts (n − i moves to insert, n − i − 1 to delete). |
| Insert / delete at the front | O(n) | O(n) | Every element shifts. Need fast front operations? Use ArrayDeque. |
| Search by value (unsorted) | O(n) | O(n) | Nothing tells you where a value is — you must look at each slot. |
| Search by value (sorted) | O(log n) | O(log n) | Binary search halves the range each step. |
| Grow capacity | — (copy to a new array) | O(n) when it happens | Copy everything into a bigger array (ArrayList grows by ~1.5×). |
| String | StringBuilder | why | |
|---|---|---|---|
| charAt(i) / length() | O(1) | O(1) | Both store characters in an internal array and keep the length. |
| Append one char | O(n) — new copy | O(1) amortized | Strings are immutable, so + copies everything. A builder writes into spare capacity. |
| Build a string of n chars in a loop | O(n²) | O(n) | 1 + 2 + … + n characters copied vs one write per char. |
| substring(a, b) | O(b − a) | O(b − a) | Since Java 7u6 substring copies the characters into a new String. |
| equals / compareTo | O(n) | compareTo O(n) (Java 11+); equals = identity | Compares character by character (String.equals checks the length first). StringBuilder does not override equals — compare sb.toString() instead. |
| reverse / insert in the middle | O(n) via a copy | O(n) | Every character after the change point has to move. |
| Time | Extra space | why | |
|---|---|---|---|
| Kadane (max subarray, circular max) | O(n) | O(1) | One decision per element — extend or restart — kept in two or four variables. |
| Prefix × suffix (product except self) | O(n) | O(1) besides the output | Two passes; the left products live in the answer array, the right ones in a single variable. |
| Boyer–Moore majority vote | O(n) | O(1) | One pass with a candidate and a counter. Counting in a HashMap is also O(n) but needs O(n) memory. |
| Next permutation | O(n) | O(1) | At most three right-to-left passes over the suffix: find the pivot, find its successor, reverse. |
| Cyclic placement (first missing positive) | O(n) | O(1) | Every swap settles one value in its home slot for good, so there are at most n swaps in the whole run. |
| Three reversals (rotate by k) | O(n) | O(1) | Each element is swapped about twice. |
06 · java
Raw vs Collections Framework
Reading by index
class Indexing { /** arr[i] lives at base + i * 4 bytes (an int is 4 bytes): one multiply + add, no loop. */ static int read(int[] arr, int i) { if (i < 0 || i >= arr.length) { throw new ArrayIndexOutOfBoundsException(i); } return arr[i]; } static void write(int[] arr, int i, int value) { arr[i] = value; // also O(1) }}- Every Java array access is bounds-checked. A bad index throws
ArrayIndexOutOfBoundsException— it never reads random memory like C can. - New arrays are filled with defaults:
0for numbers,falsefor booleans,'\u0000'for chars,nullfor objects. arr.lengthis a field (no parentheses).s.length()is a method.list.size()is a method. Mixing them up is the #1 compile error.
Insert & delete by shifting
class Shifting { /** Inserts value at index among the first `size` slots (arr needs one free slot). Returns the new size. */ static int insert(int[] arr, int size, int index, int value) { for (int i = size; i > index; i--) { arr[i] = arr[i - 1]; // shift right to open a gap } arr[index] = value; return size + 1; } /** Removes arr[index]; everything after it moves one step left. Returns the new size. */ static int delete(int[] arr, int size, int index) { for (int i = index; i < size - 1; i++) { arr[i] = arr[i + 1]; // close the gap } return size - 1; }}- Shift from the back when inserting (or you overwrite values you still need), from the front when deleting.
System.arraycopy(src, from, dst, to, len)does the same shift natively and handles overlapping ranges correctly.ArrayList.add(i, x)uses it internally.
Fixed array vs growable list
class DynamicArray { private int[] data = new int[1]; private int size = 0; void add(int value) { if (size == data.length) { int[] bigger = new int[data.length * 2]; for (int i = 0; i < size; i++) bigger[i] = data[i]; data = bigger; } data[size++] = value; } int get(int i) { if (i < 0 || i >= size) throw new IndexOutOfBoundsException(i); return data[i]; } int size() { return size; } int capacity() { return data.length; }}class Lists { static List<Integer> demo() { List<Integer> list = new ArrayList<>(); // grows by itself (about 1.5x when full) list.add(3); // append: amortized O(1) list.add(7); list.add(0, 1); // insert at front: O(n) shift -> [1, 3, 7] list.set(1, 4); // overwrite: O(1) -> [1, 4, 7] list.remove(Integer.valueOf(7)); // remove by VALUE: O(n) -> [1, 4] int first = list.get(0); // index: O(1) list.add(first * 10); // -> [1, 4, 10] return list; } static int[] toIntArray(List<Integer> list) { int[] out = new int[list.size()]; for (int i = 0; i < out.length; i++) out[i] = list.get(i); // unboxing return out; }}- Our version doubles;
ArrayListgrows by about 1.5× (old + old/2). Any constant factor > 1 gives amortized O(1) appends. new ArrayList<>()starts empty and allocates a 10-slot array on the first add. If you know the size,new ArrayList<>(n)avoids every resize.list.remove(int index)andlist.remove(Object o)are different methods. With aList<Integer>,remove(7)removes index 7 — writeremove(Integer.valueOf(7))to remove the value.ArrayList<Integer>stores boxed objects (extra memory, slower). In hot loops preferint[].
Building strings
class SlowConcat { /** Each += builds a brand-new String and copies everything so far: O(n^2) characters copied. */ static String repeat(char c, int n) { String s = ""; for (int i = 0; i < n; i++) s += c; return s; }}class FastConcat { static String repeat(char c, int n) { StringBuilder sb = new StringBuilder(n); // a resizable char buffer for (int i = 0; i < n; i++) sb.append(c); // amortized O(1) per append return sb.toString(); // one O(n) copy at the end } static String reverseWords(String sentence) { String[] words = sentence.trim().split("\\s+"); StringBuilder sb = new StringBuilder(); for (int i = words.length - 1; i >= 0; i--) { sb.append(words[i]); if (i > 0) sb.append(' '); } return sb.toString(); }}- One
a + b + cin a single expression is fine — the compiler builds it in one go. The trap is+=inside a loop. StringBuilderis not thread-safe and that's fine for interviews.StringBufferis the old synchronized version — you never need it there.- Compare strings with
.equals(), never==(which compares object identity, not content).
Characters are numbers
class CharMath { /** 'a' is 97, 'b' is 98, ... so c - 'a' maps 'a'..'z' to 0..25. */ static int[] letterCounts(String s) { int[] count = new int[26]; for (int i = 0; i < s.length(); i++) { count[s.charAt(i) - 'a']++; } return count; } /** Caesar shift inside 'a'..'z' for k >= 0. */ static char shift(char c, int k) { return (char) ('a' + (c - 'a' + k) % 26); } /** '7' -> 7. */ static int digitValue(char d) { return d - '0'; }}charis a 16-bit unsigned number (a UTF-16 code unit).'a' = 97,'A' = 65,'0' = 48.c - 'a'is anint. To go back, cast:(char) ('a' + i).- Use
int[26]for lowercase letters,int[128]for ASCII, and aHashMapfor full Unicode.
2D arrays
class Matrix { /** int[rows][cols] is an array of row arrays: grid[r][c] = row r, column c. */ static int[] rowSums(int[][] grid) { int[] sums = new int[grid.length]; for (int r = 0; r < grid.length; r++) for (int c = 0; c < grid[r].length; c++) // rows may differ in length (jagged) sums[r] += grid[r][c]; return sums; } static int[][] transpose(int[][] grid) { int rows = grid.length, cols = grid[0].length; int[][] t = new int[cols][rows]; for (int r = 0; r < rows; r++) for (int c = 0; c < cols; c++) t[c][r] = grid[r][c]; return t; }}int[][] grid = new int[rows][cols]is an array ofrowsseparateint[]objects.grid.length= rows,grid[0].length= cols.- Rows can have different lengths (a jagged array), so loop with
grid[r].lengthwhen that's possible. - Walking row by row (
router,cinner) is faster than column by column — each row is contiguous, which the CPU cache loves.
| call | does | cost |
|---|---|---|
new int[n] | Fixed-size array, filled with 0 | O(n) |
Arrays.fill(a, v) | Set every slot to v | O(n) |
Arrays.copyOf(a, len) | Copy (and truncate or pad with 0) into a new array | O(len) |
System.arraycopy(src, i, dst, j, len) | Fast native block copy, safe for overlapping ranges | O(len) |
Arrays.sort(int[]) | In-place sort of primitives (dual-pivot quicksort) | O(n log n) |
Arrays.equals(a, b) / Arrays.toString(a) | Compare / print contents (a == b only compares references) | O(n) |
list.add(x) / list.get(i) / list.set(i, x) | ArrayList append / read / overwrite | O(1) amortized / O(1) / O(1) |
list.add(i, x) / list.remove(i) | Insert / delete with shifting | O(n) |
s.charAt(i) / s.length() | Read one char / length | O(1) |
s.toCharArray() | Mutable copy of the characters | O(n) |
s.substring(a, b) | New String of chars a..b−1 | O(b − a) |
sb.append(x) / sb.toString() | Grow a StringBuilder / produce the final String | O(1) amortized / O(n) |
String.valueOf(char[]) / new String(char[]) | Turn a char array back into a String | O(n) |
Size known up front, primitives, hot loop
→ int[] / char[]
No boxing, no resizing, best cache behaviour.
Unknown size, append-heavy
→ ArrayList
Amortized O(1) appends, O(1) index.
Fast add/remove at both ends
→ ArrayDeque
Circular buffer: O(1) at the front too (ArrayList is O(n) there).
Build a string piece by piece
→ StringBuilder
O(n) total instead of O(n²) with +=.
Count lowercase letters
→ int[26]
Constant space and faster than a HashMap (no hashing, no boxing).
Count arbitrary characters / words
→ HashMap<Character or String, Integer> with merge
Works for any key, O(1) average per update.
07 · recognise
Spot the pattern
"Contiguous subarray" with the max/min sum
Kadane: extend or restart at each index
Same, but the array is circular
max(Kadane max, total − Kadane min), unless everything is negative
"Best pair (i < j)" where the later element is compared with something earlier
Keep a running min/max of the prefix (stock pattern)
"Without division" or "product/sum of everything except i"
Prefix and suffix accumulations
Anagrams, permutations of letters, "same characters"
Frequency array int[26] (or sorted string as a key)
"Appears more than n / 2 times"
Boyer–Moore vote: one candidate, one counter
"Next greater arrangement" or "next permutation"
Pivot from the right, swap with the next bigger value, reverse the suffix
Values in 1..n (or "smallest missing positive") with O(1) space
Index v − 1 is the home of value v: swap values home, or flip signs
"Rotate" or "shift" an array by k in O(1) space
Three reversals
Building a result string in a loop
StringBuilder, never +=
08 · traps & tricks
Mistakes to avoid, tricks to use
traps
- Off-by-one: valid indices are
0 .. n−1. Loops arei < n, noti <= n. - Comparing arrays or strings with
==— it compares references. UseArrays.equals/.equals. s += cinside a loop: silently O(n²). UseStringBuilder.- Shifting in the wrong direction while inserting — copy from the back or you overwrite everything with one value.
list.remove(i)on aList<Integer>removes by index, not by value.- Forgetting
k %= nin rotation problems — k can be larger than the array. intoverflow when summing or multiplying many values. Check constraints; uselongwhen in doubt.Arrays.asList(int[])gives aList<int[]>with one element, not a list of ints.- Starting a running best at 0 when at least one element must be chosen — all-negative inputs break (Kadane, circular max).
tricks
- Before coding, ask: "can I solve this with one pass and a few running variables?" That question finds Kadane, stock, prefix products and the majority vote.
- Say the complexity of library calls out loud —
substringandlist.add(0, x)are O(n),containscan be O(n·m) in the worst case — and interviewers notice. - Test edge cases every time: empty, one element, all equal, all negative, already sorted, k = 0, k > n.
- When the problem says O(1) extra space, the output array usually doesn't count — you're allowed to use it as scratch space.
- Stuck? Chalo, dry-run karte hain: take a 5-element example, write the running variables as table columns, and fill one row per index. The pattern usually shows itself by row 3.
09 · why & how
Questions you might be too shy to ask
Why is reading arr[i] O(1) but finding a value O(n)?
Reading by index is arithmetic: base address + i × element size. Finding a value has no formula — the value could be anywhere, so you check slots one by one. Sorting (binary search) or hashing is how you make value lookups fast.
When do I write i < n, i <= n or i < n - 1 in a loop?
Valid indices are 0 .. n − 1, so a plain scan is for (int i = 0; i < n; i++). i <= n reads nums[n] and crashes.
If the body reads nums[i + 1], stop one step earlier with i < n - 1, so the last pair is (n − 2, n − 1).
If the body reads nums[i - 1], start at i = 1 instead — that's how Stock II compares each day with yesterday.
Quick check: put the first and last value of i into every index in the body. Each must land in 0 .. n − 1.
If ArrayList sometimes copies everything, how can append be O(1)?
Because the copies get rarer as the list grows. Take doubling as the simple example: n appends cause copies of 1 + 2 + 4 + … < 2n elements in total. Divide by n appends and each costs a constant on average. That's amortized O(1): a promise about the total, not about every single call.
OpenJDK's ArrayList actually grows by about 1.5×. That is an implementation detail — the Javadoc only promises constant amortized time — and any fixed growth factor gives the same O(1).
Why are Java Strings immutable — isn't that wasteful?
Immutability makes strings safe to share between threads, safe to use as HashMap keys (the hash never changes), and lets Java cache them (the string pool). The cost is that every "change" makes a copy — which is exactly why StringBuilder exists.
When should I use int[] instead of ArrayList<Integer>?
When you know the size, or you're in a tight loop. int[] stores raw numbers side by side. ArrayList<Integer> stores references to Integer objects scattered around memory: more memory, more cache misses, and auto-boxing overhead.
What does "in place" actually mean?
You modify the input itself and use only O(1) extra memory (a few variables). Creating a second array of size n is not in place, even if you copy it back at the end.
Does the output array count as extra space?
By the usual interview convention, no — the output is required anyway. LeetCode 238 states this explicitly. Say the convention out loud so the interviewer knows you know it.
Is c - 'a' safe for uppercase letters or digits?
No. 'A' - 'a' is −32, which would crash an int[26]. Normalise first (Character.toLowerCase), or use int[128] indexed by the char itself for any ASCII, or a HashMap for full Unicode.
Subarray, substring, subsequence, subset — aren't they the same thing?
No, and the word changes the whole solution.
Subarray (substring for strings): one contiguous block, no gaps. In [1, 2, 3], [2, 3] is one; [1, 3] is not.
Subsequence: keep the order but skip anything you like, so [1, 3] is fine. Subset: any choice, order doesn't matter.
An array has n(n + 1)/2 non-empty subarrays but 2ⁿ − 1 non-empty subsequences. Kadane and running variables are tools for subarrays; subsequence questions usually need DP.
Kadane never tries every start. How can it be sure it didn't miss the best subarray?
Every subarray ends at some index. At each index i, Kadane keeps the best sum of a subarray ending exactly at i.
That best is either nums[i] alone or nums[i] added to the best ending at i − 1. There is no third option.
So when the scan reaches the index where the real answer ends, current already holds its sum, and best records it.
Example [-2, 5]: at 5, max(5, -2 + 5) = 5. Dropping a negative past never loses anything.
Why does the Boyer–Moore vote work? It feels like magic.
Think of it as pairing off. Every time a value different from the candidate arrives, one of each is thrown away. Each throw-away removes at most one copy of the majority but always one other value. The majority has more copies than everything else combined, so it is the only value that can be left standing.
Next Permutation: why swap the pivot with the rightmost bigger value, not any bigger value?
Everything after the pivot is falling, so reading it from the right gives values in rising order.
The first value from the right that beats the pivot is therefore the smallest value bigger than it: the smallest possible step up.
[1, 3, 5, 4, 2]: pivot 3. From the right, 2 is too small and 4 wins (not 5). Swap → [1, 4, 5, 3, 2].
The suffix [5, 3, 2] is still falling, which is why one reverse turns it into its smallest order [2, 3, 5].
First Missing Positive has a while loop inside a for loop. How is that O(n)?
Count swaps, not loops. Every swap puts one value into its home slot (index v − 1), and it never moves again. With n slots there can be at most n such swaps in the whole run — so the inner loop does O(n) work in total, not O(n) per i.
I understood Kadane when I read it, but I can't write it myself the next day. Am I just bad at this?
No — normal hai. Reading a solution and producing one are two different skills, and the second one needs practice. Close the solution and write it in a blank file, saying the one-line insight first ("extend or restart"). Stuck on a line? Peek once, then start again from blank — not from where you stopped. Repeat after one day and after three days. The recall cards at the end of the chapter are made for exactly this.
10 · practice
Interview problems
Every problem has brute → better → optimal solutions in Java, with complexity and a dry run.
- #121
- #122Best Time to Buy and Sell Stock IIMediumAppleAmazonBloombergGoogleMicrosoft
- #53
- #918Maximum Sum Circular SubarrayMediumAmazonGoogleMicrosoft
- #169
- #238
- #242
- #49
- #14Longest Common PrefixEasyBloombergAppleGoogleAmazonMicrosoft+1
- #189Rotate ArrayMediumAppleBloombergMicrosoftSamsungAmazon+1
- #31
- #41
Also practise this here
Each problem has one home page in the course; these use this chapter's idea too. The note says what to look for.
- #1Two SumEasyin Hashing
A one-pass array scan where the current element decides what you need to have seen earlier — a HashMap makes that lookup O(1).
- #48Rotate ImageMediumin Matrices
Reversal on a 2D array: transpose, then reverse every row, for a 90° turn in place.
- #54Spiral MatrixMediumin Matrices
Index bookkeeping on a 2D array: four shrinking walls walk an m × n grid in spiral order.
11 · revise
The whole chapter on one screen
10 cards, about a minute. Read them the night before an interview, or right after the chapter to lock it in.
- 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). - cost
Index O(1) · ArrayList append O(1) amortized · insert/delete in the middle O(n) · search unsorted O(n).
- use it when
Subarray max → Kadane. Except-self → prefix/suffix. Letters →
int[26]. More than n/2 → vote. Values 1..n → index v − 1. - template
Kadane:
cur = Math.max(x, cur + x); best = Math.max(best, cur);— start both atnums[0]. - template
Next permutation: pivot = first dip from the right → swap with the rightmost bigger value → reverse the suffix.
- trap
s += cin a loop is O(n²): every += copies the whole string. Build withStringBuilder, calltoString()once. - trap
list.remove(7)on aList<Integer>removes index 7, not the value 7. Writeremove(Integer.valueOf(7)). - trap
Rotate by k:
k %= nfirst. Circular max: all-negative input must return the Kadane max, not total − min. - pro tip
Before a nested loop, ask: one pass + a few running variables? Running min, best-ending-here, a vote counter.
- pro tip
O(1) space asked? Reverse in place, use the output array as scratch, or let index v − 1 remember value v.
12 · recall
Flip, remember, repeat
Why is arr[i] O(1) in Java?
Question 1: Why is arr[i] O(1) in Java?
13 · check yourself
Quick quiz
Why is `arr[i]` O(1) for a Java array?
An ArrayList has 1,000 elements. What does `list.add(0, x)` cost?
What does "amortized O(1)" append mean?
What is the time complexity of this loop? `String s = ""; for (int i = 0; i < n; i++) s += 'a';`
Kadane's algorithm on [-3, -1, -2] returns…
Which key works for grouping anagrams in a `HashMap`?
What is the next permutation of [1, 3, 5, 4, 2]?
How much extra memory does the Boyer–Moore majority vote use?
An array has 6 numbers. The first missing positive is at most…
14 · learn more
A second teacher, if you want one
- ▶ playlistArrays Playlist | Basics to Advanced | C++/Java/Python | DSA | Placements ↗Striver (take U forward) · EnglishClassic array problems (two sum, Kadane, majority element, rotation and more), each solved brute → better → optimal.
- ▶ videoDynamic and Static Arrays ↗William Fiset · EnglishA short, clear look at static vs dynamic arrays and how doubling keeps appends cheap. That's the idea inside ArrayList.
- ▶ video2. Data Structures and Dynamic Arrays ↗MIT OpenCourseWare · EnglishThe MIT 6.006 lecture on why arr[i] is O(1) and how a dynamic array gets amortized O(1) appends. It's the 'why' behind this chapter.