Simulation and Layout

What is this?

Three problems where the specification is the algorithm. Text justification has three separate rules about where spaces go and every one of them is a distinct code path. The robot asks about infinite repetition and needs a single pass. Sparse multiplication is textbook matrix multiplication with the zeros skipped — which requires reordering the loops so that skipping is possible.

None of these rewards cleverness. They reward getting every case right the first time.

flowchart TD A["execute the rules exactly"] --> B["Text Justification"] A --> C["Robot Bounded In Circle"] A --> D["Sparse Matrix Multiplication"] B --> B1["last line: left-justified"] B --> B2["one word: pad right"] B --> B3["otherwise: extra spaces go LEFT"] C --> C1["one cycle only"] C1 --> C2["back at origin? bounded"] C1 --> C3["heading changed? bounded"] D --> D1["loop i, k, j — skip A[i][k] == 0"]

💡 Fun fact: Sparse Matrix Multiplication becomes efficient through a loop reorder, not a data structure. The textbook i, j, k order computes one output cell at a time and must touch every k regardless. Swapping to i, k, j puts A[i][k] in the outer position — so when it is zero, the entire inner loop over j is skipped, because a zero contributes nothing to any output cell in that row. Same arithmetic, same results, and the work drops to the number of non-zero entries. The i, k, j ordering is also the cache-friendlier one on dense matrices, which is why numerical libraries use it anyway.

🔓 The 3 problems in this chapter are free. Sign in with Google or Microsoft to start solving.

The one-line idea: enumerate the cases on paper first. In this chapter the specification is the algorithm, and every failure is a rule discovered halfway through an implementation.

1. Three rules about spaces

if width + len(line) + len(word) > maxWidth:      # len(line) = minimum 1 space per gap
    if len(line) == 1:
        out.append(line[0].ljust(maxWidth))       # rule 2: single word, pad right
    else:
        spaces, gaps = maxWidth - width, len(line) - 1
        q, r = divmod(spaces, gaps)               # q each, plus one extra for the first r
        out.append("".join(line[i] + " " * (q + (i < r)) for i in range(gaps)) + line[-1])
    line, width = [], 0
line.append(word); width += len(word)
...
out.append(" ".join(line).ljust(maxWidth))        # rule 1: last line, left-justified

divmod does the whole distribution: q spaces in every gap, and the remainder r handed one at a time to the leftmost gaps. That left-loading is the rule most often missed, and it is a single (i < r).

The overflow test uses len(line) as the count of minimum single spaces already committed — one per gap plus one for the word about to be added — which is why it reads as width + len(line) + len(word).

2. One pass settles infinity

x = y = 0; dx, dy = 0, 1                          # facing north
for c in instructions:
    if   c == 'G': x, y = x + dx, y + dy
    elif c == 'L': dx, dy = -dy, dx               # rotate left 90°
    else:          dx, dy = dy, -dx               # rotate right 90°
return (x, y) == (0, 0) or (dx, dy) != (0, 1)

Two acceptance conditions, and the second is the interesting one. If the heading changed, four repetitions of the cycle rotate the same displacement by 90° each time, and four vectors at right angles sum to zero — so the robot returns to the origin no matter what that displacement was. If the heading is unchanged and the position is not, every cycle adds the identical vector and the robot escapes.

Rotation without trigonometry is worth internalising: left is (dx, dy) → (−dy, dx), right is (dx, dy) → (dy, −dx).

3. Skip the zeros by reordering

for i in range(m):
    for k in range(n):
        if A[i][k] == 0: continue                 # ← the entire j loop is skipped
        for j in range(p):
            if B[k][j]: C[i][j] += A[i][k] * B[k][j]

The continue is only possible because k is in the middle rather than innermost. With the textbook i, j, k order the zero check would have to run inside the innermost loop and would save almost nothing.

For genuinely sparse inputs, converting each matrix to a list of (index, value) pairs per row is the further step — and worth mentioning even if you do not write it.

4. A 30-second worked example (justification)

words = ["This","is","an","example","of","text","justification."], maxWidth = 16

line 1: This is an        letters = 8, gaps = 2, spaces = 16 − 8 = 8
        divmod(8, 2) = (4, 0)  → 4 spaces in each gap, no remainder
        "This    is    an"                                             16 ✓

line 2: example of text   letters = 13, gaps = 2, spaces = 3
        divmod(3, 2) = (1, 1)  → 1 each, plus 1 extra to the LEFT gap
        "example  of text"                                             16 ✓

line 3: justification.    last line → left-justified, padded right
        "justification.  "                                             16 ✓

Line 2 is the whole chapter in one line of output. The extra space goes into the left gap, giving example two spaces after it and of one — and a solution that loads the remainder to the right produces "example of text", which is 16 characters, looks reasonable, and is wrong.

5. Where you'll actually meet this

Typesetting engines. Justification is what word processors, browsers and PDF renderers implement.
Terminal and CLI output. Wrapping and aligning help text under a width limit is this code.
Robotics safety. Determining whether a repeated command sequence stays within a bounded region is a real pre-flight check.
Graph analytics. Sparse matrix multiplication is the core primitive behind PageRank and BFS-as-linear-algebra.
Machine learning pipelines. Sparse feature matrices are the normal case, not the exception.

6. Problems in this chapter

▶ Text Justification

Format words into fully justified lines of exact width. Pack greedily, distribute spaces with divmod loading the remainder left, and left-justify the last line.
Pattern: greedy packing + explicit case rules. Target: O(total characters).

▶ Robot Bounded In Circle

Decide whether a repeated instruction sequence keeps the robot bounded. Simulate one cycle; bounded if it returns to the origin or its heading changed.
Pattern: one-pass invariant. Target: O(n) time, O(1) space.

▶ Sparse Matrix Multiplication

Multiply two matrices that are mostly zeros. Loop i, k, j so a zero in A skips an entire inner loop.
Pattern: loop reordering to skip work. Target: proportional to the non-zero count.

7. Common pitfalls 🚫

Loading extra spaces to the right. They go to the leftmost gaps.
Justifying the last line. It is left-justified and padded on the right.
Forgetting the single-word line, which has no gaps and would divide by zero.
Simulating the robot for many cycles. One is provably enough.
Getting the rotation formulas backwards. Left is (−dy, dx), right is (dy, −dx).
Keeping the i, j, k loop order and then wondering why skipping zeros saved nothing.
Not padding every line to exactly maxWidth. Trailing spaces are part of the required output.

8. Key takeaways

The specification is the algorithm. Write the cases down before writing code.
divmod distributes remainders — and which side receives them is a stated rule, not a preference.
One pass can decide a question about infinity when the structure repeats.
Four right-angle rotations sum to zero, which is the whole boundedness proof.
Loop order determines what you can skip. Put the value you want to test outside the loop it controls.
Every output line must be exactly the requested width, padding included.
Why interviewers like it: there is nothing to be clever about, so completeness and care are the only things visible.

Order: Text Justification → Robot Bounded In Circle → Sparse Matrix Multiplication.

Sparse Matrix Multiplication

Core idea: You're multiplying two matrices A (m×k) and B (k×n), but almost every entry is 0. The textbook triple loop computes every C[i][j] as a full dot product over k terms — yet a term A[i][p] * B[p][j] is 0 (and contributes nothing) the instant either factor is 0. So the only products that matter are nonzero × nonzero. The trick: walk the nonzero entries of A directly. For each nonzero A[i][p], the matching column p of A lines up with row p of B; scatter A[i][p] * B[p][j] into C[i][j] for each nonzero B[p][j]. Precompute a compressed form — for each row, a list of (col, value) pairs of just its nonzeros — and you never touch a single zero. Work drops from O(m·n·k) (dense) to O(nonzeros).

The problem, rephrased

You run a co-purchase recommender. A is a users × items matrix where A[u][i] is how much user u likes item i — but each user has rated only a handful of items, so the matrix is mostly zeros. B is an items × tags matrix linking items to genre tags, also overwhelmingly empty. You want C = A · B: a users × tags table scoring each user against each tag. The naive way scores every (user, tag) pair against every item in between — billions of multiplications, nearly all by zero. You'd rather do work only where real signal exists.

Formally: given matrix A of shape m × k and matrix B of shape k × n, return their product C of shape m × n, where C[i][j] = Σ_p A[i][p] * B[p][j]. Both matrices are sparse (most entries are 0); compute C without wasting work on zeros.

This is LeetCode 311 — Sparse Matrix Multiplication.

Input	Means	Output
`A = [[1,0,0],[-1,0,3]]`, `B = [[7,0,0],[0,0,0],[0,0,1]]`	2×3 times 3×3	`[[7,0,0],[-7,0,3]]`
`A = [[0]]`, `B = [[0]]`	1×1 times 1×1, both empty	`[[0]]`
`A = [[1,0],[0,1]]`, `B = [[2,3],[4,5]]`	identity-ish times dense 2×2	`[[2,3],[4,5]]`

The word sparse is the whole story. If the matrices were dense, the triple loop is unavoidable — you genuinely need all m·n·k products. Because they're sparse, the overwhelming majority of those products are 0 × something or something × 0, and a 0 term adds nothing to the sum. Identifying and skipping those zero terms — ideally without even visiting them — is what turns a wasteful O(m·n·k) into work proportional to how much real data there is.

Sign in to continue reading

The rest of this lesson is available with a free account. Signing in with Google or Microsoft is free.

Advanced