Lesson 02 of 16 · 18:24
Arrays & strings
An array is a row of adjacent storage locations. Because every slot has the same size, the machine can calculate the address of index i directly. That physical layout explains both the superpower—constant-time indexing—and the cost: inserting near the front means moving everything that follows.
Strings are sequences too, but Python strings cannot be modified in place. Most array and string interview problems are therefore about controlling a scan: what information is remembered, which region has already been processed, and whether the answer can be built without repeatedly copying growing prefixes.
What you should be able to do after this lesson
- Derive operation costs from contiguous storage
- Separate logical length from allocated capacity
- Choose a scan invariant before writing the loop
The mental model
An index is an address calculation. Anything that changes the position of later elements must shift them; anything that grows past capacity must allocate and copy.
Recognize it when: Start here when order matters, random access is useful, or the problem is fundamentally about scanning, partitioning, prefix state, or contiguous ranges.
The invariant to say aloud: Know which portion of the array has already been classified and whether your operation mutates, copies, or preserves the input.
Learn the ideas one at a time
Concept 1 of 4
Static arrays
Watch from 0:10 ↗Contiguous fixed-size cells make arr[i] O(1). Searching an unsorted array is O(n), and insertion or deletion away from the end shifts a suffix.
A fixed array reserves one contiguous block. Indexing is fast because address = base + i × element_size. But the array has no hole for a new middle value: to insert at index 2, every existing value from index 2 onward must shift right. Searching is also linear unless some extra property, such as sorted order, lets you eliminate regions.
Walk through an example
Insert X into [A, B, C, D] at index 1: save the empty destination, move D to the right, then C, then B, and finally write X. Three moved values make the operation proportional to the suffix length.
In an interview
Say which portion of the array is already processed and which indices remain valid after each mutation. That is the invariant behind most in-place array solutions.
Concept 2 of 4
Dynamic arrays
Watch from 0:10 ↗A dynamic array tracks length and capacity. When full, it allocates a larger block and copies; many cheap appends pay for the rare O(n) resize, yielding amortized O(1).
A dynamic array stores both length and capacity. Appending within spare capacity is constant work. When capacity is exhausted, it allocates a larger block and copies the old values. That resize is expensive, but geometric growth means it happens rarely enough that a long sequence of appends averages to O(1) per append.
Walk through an example
With capacities 1, 2, 4, and 8, appending eight items copies roughly 1 + 2 + 4 old values across all resizes. The total copied work stays proportional to the eight appends rather than becoming 8².
In an interview
Use the word amortized: one append can be O(n), while a sequence of appends has O(1) average cost per operation.
Concept 3 of 4
Strings
Watch from 11:15 ↗A string is a sequence with array-like traversal, but Python strings are immutable. Repeated concatenation can copy growing prefixes; collect pieces and join when scale matters.
A string can be indexed and scanned like an array, but immutability changes how answers are built. Each apparent modification creates a new string. Repeatedly adding one character to an ever-growing result can copy the prefix again and again; collecting pieces in a list and joining once avoids that repeated work.
Walk through an example
Building 'abcd' with result = result + ch may copy lengths 0, 1, 2, and 3. A list append stores each character once, and ''.join(parts) performs one final linear construction.
In an interview
Clarify whether case, whitespace, punctuation, Unicode, and normalization matter before choosing a character representation.
Concept 4 of 4
Python operations
Watch from 13:30 ↗Indexing and end append are cheap; membership, slicing, inserting at the front, and deleting from the middle perform work proportional to the searched or moved region.
Python lists are dynamic arrays. list[i] and append are cheap; x in list scans; list.insert(0, x) and pop(0) shift a suffix; slicing creates a new list proportional to the slice. These details frequently turn an apparently linear solution into quadratic work.
Walk through an example
Calling pop(0) n times moves almost n items, then n-1, then n-2, producing quadratic total work. A deque removes from the front without shifting the remaining items.
In an interview
Audit every operation inside a loop. A concise built-in is not necessarily constant time just because it occupies one line.
Before you call this lesson done
- Identify the processed region
- Ask whether mutation shifts or copies data
- Choose list-plus-join for accumulated strings
- Test empty, one-element, and boundary-index cases
