02

Arrays & Strings in Java

The Java mechanics under every array and string solution — and the small traps that cost big marks.

beginner~55 min3 simulations7 problems

▶ guided lesson⚡ 1-minute summary↻ 14 recall cards

before this: Java Memory

01 · why it exists

Why this exists, and the weight it carries

since1995

Java arrays (int[], int[][])

James Gosling and the Sun Java team

In C, an array is just a pointer to memory, and nothing stops you writing past its end. Java's October 1995 white paper made arrays real objects and promised that every access is checked against the array's bounds. The Java Language Specification still says it: all array accesses are checked at run time, and a bad index throws ArrayIndexOutOfBoundsException. Fun fact: that 1995 white paper wrote myPoints.length() for arrays — the shipped language made it a plain field, length, the same mix-up learners make today.

the problem it solvedOut-of-bounds writes in C silently corrupt memory and crash much later (the white paper calls it the "delayed-crash" syndrome). Checked arrays turn that into an immediate, named exception.

its jobs today

  • The storage inside ArrayList, ArrayDeque, PriorityQueue and HashMap's bucket table — each keeps a plain array inside and moves to a bigger one to grow.
  • Fixed-size tables in DSA code: letter counts (int[26]), DP tables (int[n + 1]), visited flags (boolean[n]), grids (int[m][n]).

the weight it carries

Illustrative: 10 lakh (1,000,000) int scores. An int[] takes 4 B × 1,000,000 ≈ 4 MB in one block, and scores[750000] is one address calculation plus a bounds check — never a search.

without it

Every count, table and grid would need a map or a list of objects: several times the memory and a pointer hop on every read.

when · why · how

when
The size is known (or bounded) up front and you index by position: counts, DP tables, grids, flags.
why
O(1) read and write by index, no boxing, contiguous memory. The cost: the length is fixed, so growing means an O(n) copy.
how
int[] a = new int[n]; (zeros), int[] b = {1, 2, 3};, int[][] g = new int[rows][cols];, loop with i < a.length.

02 · plain english

The idea in 30 seconds

An int[] is a fixed row of numbered slots. A String is a sealed row of characters: you can read it, never change it.

Almost every DSA answer reads, copies or builds one of these. Their costs and traps (length vs length(), ==, += in a loop) decide whether your code is O(n) or O(n²), right or wrong.

Here you learn the tools. The array patterns (prefix sums, Kadane, two pointers) come in Stage 3.

picture this

A String is a PDF someone sent you: you can read any character instantly, but you can't edit it — every "change" exports a whole new PDF. A StringBuilder is the Word file you keep typing into, then export once at the end.

03 · remember

What you must know

  • new int[n] gives n slots already filled with defaults: 0, false, '\u0000', or null for objects. The length is fixed forever.
  • Three different sizes: arr.length (a field, for arrays), s.length() (a method, for strings), list.size() (a method, for collections).
  • == on arrays or strings asks "is this the same object?". For contents use Arrays.equals(a, b) and s.equals(t). To print, use Arrays.toString(a).
  • int[] stores raw numbers side by side. Integer[] and List<Integer> store references to boxed objects — more memory, slower, and null is possible.
  • A String never changes. s += c copies the whole string every time → O(n²) in a loop. StringBuilder.append is O(1) amortised → O(n) total.
  • A char is a 16-bit number. c - 'a' turns 'a'..'z' into 0..25 and (char) ('a' + i) turns it back — that's how an int[26] replaces a HashMap.
  • int[][] is an array of row arrays: grid.length rows, grid[r].length columns in row r. Rows may differ in length (jagged).
  • Library calls are not free: Arrays.copyOf, toCharArray, substring and split all copy — O(n) each.

04 · see it

Play with it in 3D

Press Space to play, ←/→ to step, drag to move, ? for all shortcuts. Try your own input.

sim

s += c vs StringBuilder — count the copies

Left bar: every `+=` builds a brand-new string. Right bar: the builder writes one char, and only copies when its array is full.

loading simulation…
sim

Char arithmetic — letters become array indexes

`c - 'a'` maps each letter to a counter. Pass 1 counts, pass 2 finds the first letter with count 1.

loading simulation…
sim

2D and jagged arrays — rows of rows

`accounts[r]` is a whole row array. Each row can have its own length, so the inner loop asks that row.

loading simulation…

05 · cost

Time & space, explained

Array operations in Java
TimeExtra spacewhy
new int[n]O(n)O(n)Java fills every slot with the default value before you see it.
a[i] read / write, a.lengthO(1)O(1)Address arithmetic plus a bounds check; the length is a stored field.
Arrays.fill / equals / toStringO(n)O(1) / O(1) / O(n)One pass over the elements; toString builds a string of all of them.
Arrays.copyOf / copyOfRange / cloneO(length copied)O(length copied)A new array is allocated and filled — never a free view.
Arrays.sort(int[])O(n log n)sorts in placeDual-Pivot Quicksort; the javadoc promises O(n log n) on all data sets.
Arrays.sort(Integer[], comparator)O(n log n)up to n/2 referencesA stable merge sort (TimSort) on objects; the temp buffer is what the extra space pays for.
Arrays.asList(T[])O(1)O(1)A fixed-size List view over the same array — nothing is copied.
String and StringBuilder operations
TimeNoteswhy
s.charAt(i), s.length()O(1)read onlyThe characters sit in an internal array with a known length.
s + t (one expression)O(|s| + |t|)a new StringBoth strings are copied into a fresh one.
s += c, n times in a loopO(n²)n new StringsStep k copies k chars: 1 + 2 + … + n = n(n + 1)/2.
sb.append(c), n times, then toString()O(n)O(1) amortised per appendThe array grows to 2 × old + 2 when full, so growth copying stays under about 2n.
s.toCharArray(), s.substring(a, b)O(n), O(b − a)both copyBoth allocate new storage. substring stopped sharing the original's array in Java 7u6.
s.split(regex), s.trim()O(n)new stringsOne scan, plus a new String for every piece.
s.equals(t), s.compareTo(t)O(n)no copyChar by char until the first difference (or the end).
Integer.parseInt(s), String.valueOf(x)O(digits)parse / formatOne pass over the digits.
int[] vs Integer[] vs ArrayList<Integer>
int[]Integer[]ArrayList<Integer>why
New slots start as0null— (starts empty)Primitives default to 0; references default to null.
Memory per value (typical 64-bit JVM)4 B4 B ref + 16 B object4 B ref + 16 B object + spare capacityEach boxed value is its own object (values −128..127 are cached and shared).
Can it grow?nonoyes — add is O(1) amortisedArrays are fixed; ArrayList copies into a bigger array when full.
Sort with a Comparator?noyesyes (list.sort)Comparators work on objects only.
Main dangeroverflowNPE when unboxing nullNPE; remove(int) vs remove(Object)Boxed types bring null and reference-equality problems.

06 · java

Raw vs Collections Framework

Creating arrays: sizes and default values

javadefaults and the three sizesjava.util.*
class Create {    static String defaults() {        int[] counts = new int[3];             // [0, 0, 0]        boolean[] seen = new boolean[2];       // [false, false]        char[] letters = new char[2];          // two '\u0000' chars (code 0), not spaces        String[] names = new String[2];        // [null, null]: no String objects exist yet        int[] primes = {2, 3, 5, 7};           // literal: the length comes from the values        return Arrays.toString(counts) + " " + Arrays.toString(seen) + " " + (int) letters[0]                + " " + Arrays.toString(names) + " " + primes.length;    }     static String threeSizes(int[] arr, String s, List<Integer> list) {        return arr.length + " " + s.length() + " " + list.size(); // field, method, method    }     static int lastIndex(int[] arr) {        return arr.length - 1;                 // valid indices are 0 .. length - 1    }}
  • Arrays are always filled: numbers with 0, booleans with false, chars with '\u0000' (code 0, not a space), objects with null.
  • Valid indexes are 0 .. a.length - 1. a[a.length] throws ArrayIndexOutOfBoundsException — Java checks every access.
  • new int[0] is legal and useful (an empty answer). new int[-1] throws NegativeArraySizeException.

Copying and comparing arrays

javathe loops you'd write yourselfjava.util.*
class ByHand {    static int[] copyOf(int[] a, int newLength) {        int[] copy = new int[newLength];                          // new slots start at 0        for (int i = 0; i < Math.min(a.length, newLength); i++) copy[i] = a[i];        return copy;    }     static boolean sameContents(int[] a, int[] b) {        if (a.length != b.length) return false;        for (int i = 0; i < a.length; i++) if (a[i] != b[i]) return false;        return true;    }}
  • int[] b = a; copies nothing — it's a second name for the same array. Copy with a.clone() or Arrays.copyOf(a, a.length).
  • Arrays.copyOfRange(a, from, to): from is inclusive, to is exclusive — the same rule as substring.
  • Arrays.equals compares contents; for 2D arrays use Arrays.deepEquals and Arrays.deepToString.
  • Arrays.sort(a) sorts in place and returns nothing (void) — don't write a = Arrays.sort(a).

The Arrays.asList trap

javaasList on int[] vs Integer[]java.util.*
class AsListTrap {    static String demo() {        int[] primitives = {3, 1, 2};        List<int[]> wrong = Arrays.asList(primitives);    // ONE element: the whole int[]        Integer[] boxed = {3, 1, 2};        List<Integer> view = Arrays.asList(boxed);        // 3 elements, backed by the array        view.set(0, 9);                                   // writes through: boxed[0] is now 9        boolean addFails;        try {            view.add(4);                                  // fixed size: no add, no remove            addFails = false;        } catch (UnsupportedOperationException e) {            addFails = true;        }        List<Integer> real = new ArrayList<>(Arrays.asList(boxed)); // a real, growable copy        real.add(4);        return wrong.size() + " " + view.size() + " " + boxed[0] + " " + addFails + " " + real;    }}
  • Generics only hold objects, so Arrays.asList(int[]) sees ONE object: the array itself → List<int[]> of size 1.
  • Arrays.asList(Integer[]) is a fixed-size view: set writes through to the array, add/remove throw UnsupportedOperationException.
  • List.of(...) is stricter still: fully immutable, and it rejects null. Need a growable list? new ArrayList<>(Arrays.asList(...)).

2D and jagged arrays

javarows of rowsjava.util.*
class TwoD {    static String rectangle() {        int[][] grid = new int[2][3];                 // 2 rows × 3 columns, all 0        grid[1][2] = 7;                               // row 1, column 2        int rows = grid.length, cols = grid[0].length;        return rows + "x" + cols + " " + Arrays.deepToString(grid);    }     static int[][] jagged(int rows) {        int[][] tri = new int[rows][];                // rows exist, but each row is still null        for (int r = 0; r < rows; r++) tri[r] = new int[r + 1];   // row r gets r + 1 slots        return tri;    }     static int countCells(int[][] grid) {        int cells = 0;        for (int[] row : grid) cells += row.length;   // use THIS row's length, never grid[0].length        return cells;    }     static int[][] deepCopy(int[][] g) {        int[][] copy = new int[g.length][];        for (int r = 0; r < g.length; r++) copy[r] = g[r].clone();  // copy every row        return copy;                                  // g.clone() alone would share the rows    }}
  • new int[2][3] makes an array of 2 references, each pointing to its own int[3] row. grid[r][c] = row first, then column.
  • new int[rows][] leaves every row null until you assign grid[r] = new int[len] — that's how jagged arrays (like a triangle) are built.
  • grid.clone() copies only the row references: both grids share rows. Clone each row for a real copy.
  • Walk row by row (r outer, c inner). Each row is contiguous memory, so this order is also the cache-friendly one.

int[] vs Integer[] vs List<Integer>

javaboxing, nulls and conversionsjava.util.*
class Boxing {    static String defaults() {        int[] primitives = new int[3];                // [0, 0, 0]: raw numbers side by side        Integer[] boxed = new Integer[3];             // [null, null, null]: references, no objects yet        List<Integer> list = new ArrayList<>();       // empty; grows as you add        for (int i = 0; i < 3; i++) list.add(i * 10); // autoboxing: int -> Integer        boolean unboxingNullThrows = false;        try {            int first = boxed[0];                     // auto-unboxing null -> NullPointerException            list.add(first);        } catch (NullPointerException e) {            unboxingNullThrows = true;        }        return Arrays.toString(primitives) + " " + Arrays.toString(boxed) + " " + list + " " + unboxingNullThrows;    }     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); // unboxes each element        return out;                                   // or: list.stream().mapToInt(Integer::intValue).toArray()    }     static Integer[] sortDescending(int[] nums) {        Integer[] boxed = new Integer[nums.length];        for (int i = 0; i < nums.length; i++) boxed[i] = nums[i];        Arrays.sort(boxed, Collections.reverseOrder()); // a Comparator needs objects, not int        return boxed;    }}
  • list.add(x) silently boxes int → Integer; int y = list.get(i) silently unboxes — and throws NullPointerException on null.
  • Converting between int[] and List<Integer> is always an O(n) loop (or a stream doing the same loop).
  • Arrays.sort(int[]) takes no Comparator. For descending order, sort ascending and read backwards, or box into Integer[].

Strings never change (and the string pool)

java== vs equals, and the ignored-result bugjava.util.*
class Immutable {    static String demo() {        String a = "upi";                      // a literal lives in the string pool        String b = "upi";                      // same literal -> the SAME pooled object        String c = new String("upi");          // forces a separate object on the heap        String d = c.intern();                 // asks the pool for its copy        String upper = a.toUpperCase();        // a is untouched; a NEW string comes back        return (a == b) + " " + (a == c) + " " + a.equals(c) + " " + (a == d) + " " + a + " " + upper;    }     static String trimBug(String s) {        s.trim();                              // BUG: the trimmed copy is thrown away        return s;    }     static String trimFixed(String s) {        return s.trim();                       // keep the new string the method returns    }}
  • Equal string literals share one pooled object, so == sometimes works by accident. Strings from new, input or substring are separate objects. Always use equals.
  • Every "modifying" method — trim, toUpperCase, replace, concat — returns a NEW string. Keep it: s = s.trim();.
  • Immutability is what makes strings safe as HashMap keys: a key can't change after it's stored.

Building strings: += vs StringBuilder

javathe same result, O(n²) vs O(n)java.util.*
class Building {    static String slow(int n) {        String s = "";        for (int i = 0; i < n; i++) {            s += (char) ('a' + i % 26); // a NEW string: copies all of s, then 1 more char        }        return s;    }     static String fast(int n) {        StringBuilder sb = new StringBuilder();          // room for 16 chars to start        for (int i = 0; i < n; i++) {            sb.append((char) ('a' + i % 26)); // writes 1 char; when full, grows to 2 × old + 2        }        return sb.toString();                            // one final copy    }}
  • One a + b + c in a single expression is fine. The trap is += repeated inside a loop: javac does not turn your loop into one builder.
  • new StringBuilder() holds 16 chars; when full it grows to 2 × old + 2. Doubling keeps the total copying under about 2n.
  • Useful builder calls: append, reverse(), setCharAt(i, c), deleteCharAt(sb.length() - 1), insert(0, x) (O(n) — it shifts).
  • StringBuffer is the older, synchronized twin. In interview code, always StringBuilder.

Characters are numbers

javachar arithmetic and Character helpersjava.util.*
class Chars {    static int[] letterIndexes(String s) {        int[] idx = new int[s.length()];        for (int i = 0; i < s.length(); i++) idx[i] = s.charAt(i) - 'a'; // 'a'->0 ... 'z'->25        return idx;    }     static char letterAt(int i) {        return (char) ('a' + i);               // int -> char needs a cast    }     static int digitValue(char c) {        return c - '0';                        // '7' -> 7 (its code is 55)    }     static String sortedLetters(String s) {        char[] cs = s.toCharArray();           // a mutable COPY of the characters        Arrays.sort(cs);        return new String(cs);                 // or String.valueOf(cs); never cs.toString()    }     static String helpers() {        return Character.isLetter('Q') + " " + Character.isDigit('7') + " "                + Character.isLetterOrDigit('_') + " " + Character.toLowerCase('Q') + " "                + Character.isUpperCase('Q') + " " + (int) 'a' + " " + ('a' + 1) + " " + (char) ('a' + 1);    }}
  • 'a' is 97, 'A' is 65, '0' is 48. Letters a–z are consecutive, so c - 'a' is an index 0..25.
  • char + int gives an int: 'a' + 1 prints 98. Cast back with (char) ('a' + 1).
  • toCharArray() makes a mutable copy — sort it, swap in it, then new String(cs). cs.toString() prints junk like [C@….
  • Uppercase or mixed input? Character.toLowerCase(c) first, or use int[128] indexed by the char itself.

Converting and parsing

javanumber ↔ textjava.util.*
class Convert {    static String toText(int n, char c, char[] cs) {        return String.valueOf(n) + "|" + String.valueOf(c) + "|" + String.valueOf(cs)                + "|" + Integer.toString(n, 2) + "|" + n;      // the last one: "" + n works too    }     static int parse(String s) {        return Integer.parseInt(s.trim());     // trim first: " 42" alone would throw    }     static boolean parseThrows(String s) {        try {            Integer.parseInt(s);            return false;        } catch (NumberFormatException e) {            return true;                       // "", " 42", "4.2", "2147483648" (too big) all throw        }    }     static long parseBig(String s) {        return Long.parseLong(s);              // values beyond int's 2,147,483,647    }}
  • String.valueOf(x) works for every type (and String.valueOf(char[]) joins the chars). Integer.toString(n, 2) gives binary.
  • Integer.parseInt throws NumberFormatException on spaces, empty strings, decimals and values above 2,147,483,647. Trim input first.
  • Need bigger numbers? Long.parseLong handles up to about 9.2 × 10¹⁸.

split and trim traps

javawhat split really returnsjava.util.*
class SplitTrim {    static String[] words(String line) {        String t = line.trim();                // drop spaces at both ends first        return t.isEmpty() ? new String[0] : t.split("\\s+"); // one or more whitespace chars    }     static String traps() {        return "a  b".split(" ").length               // 3: ["a", "", "b"], an empty token between spaces                + " " + " a b".split(" ").length      // 3: a leading separator gives "" first                + " " + "a,b,,".split(",").length     // 2: trailing empty strings are dropped                + " " + "a,b,,".split(",", -1).length // 4: limit -1 keeps them                + " " + "1.2.3".split(".").length     // 0: "." is regex for ANY char!                + " " + "1.2.3".split("\\.").length   // 3: escape it                + " " + "x|y".split("\\|").length;    // 2: | is regex too    }}
  • split takes a regex. ., |, +, *, ? and $ mean something there: escape them as "\\.", "\\|".
  • Splitting on one space keeps empty tokens between double spaces and before a leading space. trim() + split("\\s+") is the safe default for words.
  • Trailing empty strings are dropped ("a,b,," → 2 pieces) unless you pass a limit of -1.
  • trim() removes ASCII spaces and control chars at both ends; strip() (Java 11+) also removes Unicode spaces.

compareTo and substring

javadictionary order and copyingjava.util.*
class CompareSub {    static String compare() {        return "apple".compareTo("banana")            // -1: 'a' - 'b' at the first difference                + " " + "rahul".compareTo("rahul")    // 0: equal                + " " + "Zomato".compareTo("swiggy")  // -25: 'Z' (90) < 's' (115), capitals sort first                + " " + "abc".compareTo("ab")         // 1: same prefix, so the length decides                + " " + "Priya".equalsIgnoreCase("PRIYA")                + " " + "priya".compareToIgnoreCase("Rahul"); // -2: 'p' - 'r'    }     static String lastWord(String s) {        int start = s.lastIndexOf(' ') + 1;           // -1 + 1 = 0 when there is no space        return s.substring(start);                    // copies s.length() - start chars    }}
  • a.compareTo(b) subtracts the first differing chars (or the lengths). Only the sign matters: negative = a first.
  • Uppercase sorts before lowercase ('Z' = 90 < 'a' = 97). Use compareToIgnoreCase when case shouldn't matter.
  • substring(a, b) copies b − a chars (since Java 7u6). Inside a loop, pass indexes around instead of cutting new strings.
Java API you will actually use
calldoescost
new int[n] / new int[r][c]Zero-filled array / gridO(n) / O(r·c)
arr.length · s.length() · list.size()Size of an array / a String / a collectionO(1)
Arrays.fill(a, v)Set every slot to vO(n)
Arrays.copyOf(a, len) / copyOfRange(a, from, to)New array; pads with 0 or null; to is exclusiveO(len)
Arrays.equals(a, b) / Arrays.deepEquals(g, h)Compare contents of 1D / nested arraysO(n)
Arrays.toString(a) / Arrays.deepToString(g)Readable text for debuggingO(n)
Arrays.sort(a) / Arrays.sort(boxed, cmp)Sort primitives / sort objects with a ComparatorO(n log n)
Arrays.asList(T...)Fixed-size List view over an object arrayO(1)
System.arraycopy(src, i, dst, j, len)Fast block copy between arraysO(len)
s.charAt(i) / s.toCharArray()One char / a mutable copy of all charsO(1) / O(n)
sb.append(x) / sb.reverse() / sb.toString()Build, reverse and finish a stringO(1) amortised / O(n) / O(n)
String.valueOf(x) / Integer.parseInt(s) / Long.parseLong(s)Number ↔ textO(digits)
s.split(regex) / s.trim() / s.strip()Cut into pieces / drop spaces at both endsO(n)
s.equals(t) / s.compareTo(t) / s.equalsIgnoreCase(t)Same text? / which comes first?O(n)
Character.isDigit / isLetter / toLowerCaseClassify or normalise one charO(1)

A fixed number of numeric slots (counts, DP, flags)

→ int[] / boolean[]

Compact, zero-filled, O(1) by index, no boxing.

Size unknown, or the method returns a List

→ ArrayList<Integer>

Grows by itself; pass n as the capacity when you know it.

Sort numbers in a custom order

→ Integer[] + Comparator (or sort ascending, read backwards)

Arrays.sort(int[]) takes no Comparator.

Build text in a loop

→ StringBuilder

O(n) total instead of O(n²).

Edit characters in place

→ char[] cs = s.toCharArray() … new String(cs)

A String can't change; a char array can.

Count lowercase letters

→ int[26] with c - 'a'

O(1) per char and 26 counters — lighter than a HashMap.

07 · recognise

Spot the pattern

"Only lowercase English letters"

int[26] with c - 'a' — no HashMap needed

Values in a small range, like 1 ≤ nums[i] ≤ 100

A counting array indexed by the value: new int[101]

Return a string you build piece by piece

StringBuilder, then one toString()

"Words separated by one or more spaces"

trim() + split("\\s+"), or scan with an index

m × n grid, matrix, int[][]

grid.length rows, grid[r].length columns; r outer, c inner

Return type List<Integer> / List<Boolean>

new ArrayList<>(n) when n is known; values get boxed

Output size known up front (2n, n + 1, m·n)

Allocate new int[size] once and fill it by index arithmetic

08 · traps & tricks

Mistakes to avoid, tricks to use

traps

  • arr.length(), s.length, list.length — three wrong spellings. The compiler catches them, but under pressure they cost minutes.
  • == on arrays or strings compares references. Arrays.equals(a, b) and a.equals(b) compare contents.
  • System.out.println(arr) prints [I@…. Use Arrays.toString(arr); for 2D, Arrays.deepToString(grid).
  • Arrays.asList(intArray) is a List<int[]> with one element. And Arrays.asList/List.of can't grow — wrap them in new ArrayList<>(…).
  • s.trim(); or s.toUpperCase(); on its own line does nothing — keep the returned string.
  • split(".") and split("|") are regexes: escape them. And "a b".split(" ") contains an empty token.
  • 'a' + 1 is the int 98, and "" + 'a' + 1 is "a1". Cast when you want a char: (char) ('a' + 1).
  • Unboxing null throws: int x = map.get(missingKey) or reading an unfilled Integer[].
  • grid.clone() on a 2D array shares the rows. Clone each row.
  • Integer.parseInt(" 42") throws — trim first. Values above 2,147,483,647 need Long.parseLong.

tricks

  • Before coding, write the sizes down: n = nums.length, m = grid.length, k = s.length(). Fewer typos, clearer loops.
  • Debug arrays with one line: System.out.println(Arrays.toString(a));.
  • When the output size is known, allocate once (new int[2 * n]) instead of growing a list.
  • Mixed case? Character.toLowerCase(c) first, then c - 'a'.
  • Say library costs out loud in interviews: "substring copies, so this line is O(n)." Interviewers notice.
  • Chalo, one habit for life: the moment you write += on a String inside a loop, switch to StringBuilder.

09 · why & how

Questions you might be too shy to ask

Why is it length for arrays but length() for strings?

An array's length is a final field fixed when the array is created, so there's nothing to compute. String is a class and length() is one of its methods; collections use size(). Everyone mixes these up at first, and the compiler tells you at once. Learn the three and move on.

Why does my loop crash with i <= arr.length?

Indexes start at 0, so an array of length 3 has slots 0, 1, 2. The last valid index is arr.length - 1. With <=, the last round reads arr[3] and throws ArrayIndexOutOfBoundsException. Default habit: for (int i = 0; i < n; i++).

Should I use a for-each loop or an index loop?

For-each (for (int x : nums)) is perfect when you only read the values. Use an index loop when you need the position, a neighbour like nums[i + 1], a backward walk, or a write into the array. Dhyan do: x = 0 inside a for-each changes only the copy x, never the array.

int[], Integer[] or List<Integer> — which one?

Default to int[] when the size is known (counts, DP tables, prefix sums). Use List<Integer> when the size grows or the method must return a List. Integer[] is mainly for sorting with a Comparator. Converting costs O(n), so choose early.

I called list.remove(1) on a List<Integer> and the wrong thing disappeared. Why?

remove has two versions. remove(int index) removes by position; remove(Object o) removes by value. A plain 1 is an int, so Java picks the index version. For [10, 20, 1], list.remove(1) gives [10, 1], while list.remove(Integer.valueOf(1)) gives [10, 20].

The method must return int[], but I collected my answer in a List<Integer>. How do I convert?

Allocate and copy: int[] ans = new int[list.size()]; then ans[i] = list.get(i) in a loop. The one-liner list.stream().mapToInt(Integer::intValue).toArray() does the same O(n) work. If you knew the size up front, skip the list and fill an int[] directly.

Why doesn't Java make s += c fast for me?

Because String is immutable: s += c must leave the old string untouched, so it builds a new one and copies everything. javac compiles each += on its own; it doesn't turn your whole loop into one builder. A single a + b + c is fine — the trap is repeating += n times.

My answer is built from the back. Should I call sb.insert(0, c) every time?

No. insert(0, c) shifts every char already in the builder one place right, so n inserts cost O(n²) — the same trap as +=. Instead append in the order you get the chars, then call sb.reverse() once at the end: O(n) total.

Is substring O(1)?

Not since Java 7 update 6 (2012). Before that, a substring shared the original's character array; OpenJDK removed that sharing (bug JDK-6924259), so today substring(a, b) copies b − a chars. Treat it as O(length).

Why does "1.2.3".split(".") return an empty array?

split takes a regular expression, and . matches any character. Every char becomes a separator, every piece is empty, and trailing empty pieces are dropped — nothing is left. Write split("\\.").

Everyone says never use ==. Is s.charAt(i) == 'a' wrong too?

No, that one is correct. A char is a primitive (just a number), so == compares the values directly. The == trap is only for objects: String, Integer, arrays. Simple hai: char → ==, String → equals.

s.charAt(i) or s.toCharArray() — which should I use?

To only read characters, charAt(i) is enough: O(1) each and no copy, so O(1) extra space. toCharArray() copies the whole string once (O(n) time and space). Take that copy when you must change chars: sort them, swap them, or overwrite them.

Why is an int[26] counter called O(1) space? It is still an array.

Space complexity asks how memory grows with the input size n. The 26 counters stay 26 whether s has 5 chars or 10⁵ chars, so the growth is zero: O(1). Some interviewers write O(k) for an alphabet of size k. Say both, and you are safe.

Is this the arrays chapter? Where are Kadane and prefix sums?

This chapter is only the Java mechanics. Why indexing is O(1), shifting, dynamic arrays, Kadane and prefix tricks live in Arrays & Strings (Stage 3), after you have Big-O. Bas itna yaad rakho: here you learn the tools, there you learn the patterns.

10 · practice

Interview problems

Every problem has brute → better → optimal solutions in Java, with complexity and a dry run.

  1. #58
    Length of Last Word
    EasyBloombergGoogleAmazonMicrosoft
  2. #1929
    Concatenation of Array
    EasyGoogleBloombergAmazonInfosys
  3. #1672
    Richest Customer Wealth
    EasyGoogleMicrosoftMeta
  4. #1431
    Kids With the Greatest Number of Candies
    EasyAmazonMetaMicrosoft
  5. #1470
    Shuffle the Array
    EasyMicrosoftGoogleAmazon
  6. #387
    First Unique Character in a Stringmust-do
    EasyGoldman SachsBloombergWalmartAmazonApple
  7. #1512
    Number of Good Pairs
    EasyBloombergGoogleMicrosoft

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.

  1. #242
    Valid Anagram
    Easyin Arrays & Strings

    The same int[26] + c - 'a' mechanics, used to compare two strings.

  2. #125
    Valid Palindrome
    Easyin Two Pointers

    charAt, Character.isLetterOrDigit and toLowerCase inside a two-pointer scan.

  3. #1480
    Running Sum of 1d Array
    Easyin Mindset

    Writing into an array by index — a gentle first array problem.

11 · revise

The whole chapter on one screen

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

  1. what it is

    int[] = fixed row of slots, pre-filled with 0/false/null. String = text you read but never change. StringBuilder = text you build.

  2. use it when

    Size known → int[]. Size unknown or a List is returned → ArrayList<Integer>. Text in a loop → StringBuilder. Only a–z → int[26].

  3. template

    int[] count = new int[26]; for (char c : s.toCharArray()) count[c - 'a']++;

  4. cost

    s += c n times copies 1 + 2 + … + n chars: O(n²). sb.append(c) is O(1) amortised: O(n). substring, split, toCharArray copy: O(n).

  5. trap

    arr.length · s.length() · list.size(). And == on arrays or strings compares references — use Arrays.equals / equals.

  6. trap

    Arrays.asList(int[]) is a List<int[]> of ONE element. split(".") splits on every char — escape it: split("\\.").

  7. pro tip

    Print with Arrays.toString(a) (2D: deepToString). Plain println(a) shows junk like [I@1b6d3586.

  8. pro tip

    'a' + 1 is the int 98; (char) ('a' + 1) is 'b'. Digit chars: c - '0'.

12 · recall

Flip, remember, repeat

card 1 / 14
recall

Array, String, List: how do you get the size of each?

tap or Space to flip ↻

Question 1: Array, String, List: how do you get the size of each?

13 · check yourself

Quick quiz

  1. For `int[] a` and `String s`, which line compiles?

  2. What does `new String[3]` contain?

  3. You build a 10⁵-char string one char at a time. Which way is O(n)?

  4. `List<Integer> list = Arrays.asList(1, 2, 3); list.add(4);` — what happens?

  5. `char c = 'd';` What is `c - 'a'`?

  6. `"a,b,,".split(",").length` is…

  7. `String a = "upi"; String b = new String("upi");` Which is true?

0/0 correct · 7 left

14 · learn more

A second teacher, if you want one