Foundations
Lists, strings, and slicing
The sequence operations that show up in almost every solution, and the three that quietly cost you a factor of n.
Lists
A Python list is a growable array. Indexing and appending are cheap. Inserting or deleting anywhere other than the end is not, because everything after the hole has to shift.
Gotcha
pop(0) in a loop
Using a list as a queue by calling pop(0) turns an O(n) loop into an O(n squared) one. Each pop shifts every remaining element down by one.
When you need a queue, use collections.deque, which has popleft() at O(1). You will need this constantly once you reach breadth-first search.
Slicing
A slice copies. It does not give you a view onto the original, and that single fact is behind a whole class of accidental quadratic solutions: taking s[i:] inside a loop over i copies the tail of the string on every pass.
Key idea
Half-open ranges
Python slices and range() both include the low end and exclude the high end. s[i:j] holds j - i characters. range(a, b) yields b - a numbers.
Half-open ranges are why so much of this code avoids off-by-one errors. The size of a half-open window from left to right is just right - left, with no correction term. Write the window as inclusive on both ends and the size becomes right - left + 1, and that stray + 1 is where the mistakes live. Pick one convention and hold it for the whole problem.
Strings are immutable
You cannot assign into a string. Every operation that looks like it edits one actually builds a new one, which is why building a string by repeated concatenation in a loop is a trap.
Gotcha
Why += on strings is a trap
CPython has an optimization that sometimes mutates a string in place when nothing else refers to it, which makes the loop above look linear in casual testing. PEP 8 explicitly tells you not to depend on it: it is fragile even in CPython and absent in implementations that do not use reference counting.
Build a list and join it once with "".join(pieces). It is the same number of lines and it is linear everywhere.
Iterating properly
Reaching for range(len(x)) out of habit is a Java reflex. Usually you want the element, sometimes you want the index and the element, and occasionally you want two sequences at once.
Sorting
sorted() returns a new list. list.sort() sorts in place and returns None, which is a classic way to accidentally assign None to your variable. Both take a key function, and both are stable: elements that compare equal keep their original relative order.
Tip
Look at where pear and kiwi land
Both have length 4. In the first result pear comes before kiwi, because that is the order they were in originally and Python's sort is stable: equal keys keep their existing relative order. In the third result kiwi comes first, because the key (len(w), w) breaks the tie alphabetically.
Stability is the mechanism behind sorting by two criteria without writing a combined key. Sort by the secondary key first, then by the primary one, and the secondary ordering survives inside each group.
Tip
Sorting costs O(n log n)
That is often the right trade. If sorting turns an O(n squared) scan into an O(n log n) sort plus an O(n) pass, take it. A large fraction of interval and greedy problems are exactly that trade.
Lists of lists
A grid is a list whose elements are lists. grid[r] is the row at index r, and grid[r][c] is one cell. Row first, then column, always in that order.
len(grid) is the number of rows and len(grid[0]) is the number of columns. Walking every cell is two nested loops, the outer over rows and the inner over columns.
Gotcha
Building a grid of zeros
The obvious way to make an empty grid is wrong in a way that is genuinely hard to spot. [[0] * 3] * 2 builds one row and then stores the same row object twice, so writing to one row writes to both.
Use a comprehension, which builds a fresh row each time round.
Building strings with f-strings
Putting an f before a string lets you drop expressions into it inside braces. It is the readable way to assemble output, and it appears in a few later lessons.
Tip
Characters as numbers
ord(ch) gives a character's numeric code and chr(n) converts back. Subtracting ord("a") turns a lowercase letter into 0 through 25, which is how you index a 26-slot array by letter or measure the gap between two letters.
Unpacking and swapping
Multiple assignment reads better than temporary variables and is used constantly in two-pointer and linked-list code.
Predict the output: aliasing
Two names, one list. Type exactly what this prints, including the brackets and spaces.
Predict the output: sort versus sorted
This is the mistake everyone makes exactly once. Type what it prints.
Predict the output: integer division
Python's // is floor division, not truncation. Type the two values separated by a single space.
Which one is the quadratic version?
One loop empties a list by calling nums.pop(0) n times. The other empties a deque by calling popleft() n times. Both remove the same n items in the same order. Which statement is right?
Sequence warm-up
Three small functions, no imports needed. second_largest returns the second largest distinct value. reverse_words reverses the order of the words in a sentence but not the letters inside them. running_totals returns a list where position i holds the sum of everything up to and including i.
Tests
print(second_largest([3, 1, 4, 4, 5, 5]))
print(reverse_words("the quick brown fox"))
print(running_totals([1, 2, 3, 4]))
print(running_totals([]))Output
Run the tests when you are ready.