← Arrays & Strings · guided lesson
Arrays & Strings
the story
Array (contiguous memory)
Every tool here exists because something was too slow or broke without it. Here is what.
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 solved
Keeping many values of one kind under one name and reaching any of them by its number, without hand-written address arithmetic.
why it matters: 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.
sources: Backus et al. — The FORTRAN Automatic Coding System (Western Joint Computer Conference, 1957) ↗ · Full text at the Computer History Museum's Software Preservation Group ↗
also in this chapter: Dynamic array (ArrayList) · Immutable String & StringBuilder · Counting array (int[26]) · Kadane's algorithm · Prefix & suffix passes · Boyer–Moore majority vote · Next lexicographic permutation · Index as home (cyclic placement, sign markers)
the idea
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).
watch it
Why arr[i] is O(1) — memory addresses
Predict mode is on. Before each step, guess what happens, then watch. Wrong guesses are fine; that is how it sinks in.
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.
On this screen ← / → step the simulation. Use the buttons below to move through the lesson.
watch it
Insert in the middle — watch everything shift
Predict mode is on. Before each step, guess what happens, then watch. Wrong guesses are fine; that is how it sinks in.
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.
On this screen ← / → step the simulation. Use the buttons below to move through the lesson.
key idea 1 of 8
Read it once. Say it out loud once. Bas.
Contiguous memory: arr[i] lives at base + i × elementSize. One multiply and one add — that's why indexing is O(1).
key idea 2 of 8
Read it once. Say it out loud once. Bas.
Static vs dynamic: int[] has a fixed length. ArrayList wraps an array and copies it into a bigger one when full — appends are amortized O(1).
key idea 3 of 8
Read it once. Say it out loud once. Bas.
Shifting is the hidden cost: insert/delete at index i moves n − i elements. Front = O(n), end = O(1).
key idea 4 of 8
Read it once. Say it out loud once. Bas.
Strings are immutable in Java. s += x in a loop builds a new String each time → O(n²). Use StringBuilder → O(n).
key idea 5 of 8
Read it once. Say it out loud once. Bas.
Characters are numbers: c - 'a' maps 'a'..'z' to 0..25, so an int[26] is a tiny, fast hash map for letter counts.
key idea 6 of 8
Read it once. Say it out loud once. Bas.
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.
key idea 7 of 8
Read it once. Say it out loud once. Bas.
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).
key idea 8 of 8
Read it once. Say it out loud once. Bas.
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.
spot the pattern
When you see this, think this
"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
+6 more signals on the chapter page
watch out
A trap or two
Many wrong answers in interviews come from small slips like these, not from the hard part.
- 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.
quick check
One question. No pressure.
Why is arr[i] O(1) for a Java array?
now try
Your first real problem
You know enough to try this one. Stuck? Use the hints; that is what they are for.
Best Time to Buy and Sell Stock
open the problem →recall
Flip a few cards
Answer in your head first, then flip. Grade yourself honestly; the schedule brings back what you forget.
Why is arr[i] O(1) in Java?
Question 1: Why is arr[i] O(1) in Java?
done
Lesson complete
Chalo, that is the core. The full chapter has the rest: cost tables, Java details and more problems.