</> MAANG.io

Advanced

Advanced problems where modelling is the hard part: implicit graphs, tricky DP states, intervals and design challenges.

0 of 95 solved 0%

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 each one 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 means storing only the nonzero entries of each row.

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

Simulation and Layout rule tree for justification, robot, and sparse matrix

Fun fact: In Sparse Matrix Multiplication, the efficient version does the same arithmetic as the textbook one, minus every product that has a zero factor. For A = [[1,0,0],[-1,0,3]] and B = [[7,0,0],[0,0,0],[0,0,1]] the dense loop does 2*3*3 = 18 multiplications and the compressed version does 3. The answer is the same [[7,0,0],[-7,0,3]].

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


Core 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 word already on the line, which covers the gap before the word about to be added. That is why it reads as width + len(line) + len(word).

The lesson walks this as two approaches. Approach 1 finds the line groups first and renders them second. It is O(total characters) time with O(n) extra space for the groups. Approach 2 fuses the two into one sweep and keeps O(maxWidth) working space. Both write the same O(total characters) output.

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, each cycle turns the displacement by the same nonzero rotation (90, 180 or 270 degrees). A nonzero rotation plus a translation is a rotation about a fixed point, so the robot orbits that point. Concretely, four cycles bring the heading back to north and the four displacement vectors sum to zero, so the robot is back at the origin within four cycles. If the heading is unchanged and the position is not, every cycle adds the identical vector and the robot escapes.

"GGLLGG" shows the first condition: it ends at (0, 0) facing south, so it is bounded on the position test alone. "GL" ends at (0, 1) facing west, so the heading test accepts it.

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

3. Skip the zeros by storing only the nonzeros

A_rows = [[(p, A[i][p]) for p in range(k) if A[i][p]] for i in range(m)]
B_rows = [[(j, B[p][j]) for j in range(n) if B[p][j]] for p in range(k)]

C = [[0] * n for _ in range(m)]
for i in range(m):
    for p, a in A_rows[i]:            # nonzero A[i][p] selects row p of B
        for j, b in B_rows[p]:
            C[i][j] += a * b

A nonzero A[i][p] pairs with exactly one row of B, row p. Scattering each product into C[i][j] with += replaces the per-cell dot product, and several values of p can land on the same cell. Only nonzero-times-nonzero pairs ever run, so the multiplication count follows the data instead of m*n*k.

Building the compressed rows costs O(m*k + k*n) because every cell is read once. On fully dense input the compressed version is slightly slower than the plain triple loop, since it pays for the list building as well. If the input already arrives as coordinates, that scan disappears.

Terms can cancel. [[1,1],[0,0]] x [[2,0],[-2,5]] is [[0,5],[0,0]]: cell (0,0) is touched twice and ends at 0.


4. A 30-second worked example (justification)

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

Worked text justification example at width 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. 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.
  • Repeating control sequences. A device replaying a fixed move sequence either drifts or stays in a region, and one cycle's net motion tells you which.
  • Graph analytics. Sparse matrix multiplication is the primitive behind BFS expressed as linear algebra.
  • Numerical libraries. Compressed sparse row storage, which keeps (index, value) pairs per row, is the same idea as the compressed rows above.

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 and any single-word line.
Pattern: greedy packing + explicit case rules. Target: O(total characters) time.

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. Store each row as (column, value) pairs and multiply only nonzero pairs.
Pattern: compressed rows to skip work. Target: O(m*k + k*n) to build the rows, plus one multiplication per nonzero pair.


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. It is left-justified like the last line.
  • Simulating the robot for many cycles. One cycle plus the origin-or-heading test is enough.
  • Getting the rotation formulas backwards. Left is (−dy, dx), right is (dy, −dx).
  • Testing for zero inside the dense i, j, k loops. The loops still run, so almost nothing is saved. Compress the rows first.
  • Not padding every line to exactly maxWidth. Trailing spaces are part of the required output.

8. Key takeaways

  1. The specification is the algorithm. Write the cases down before writing code.
  2. divmod distributes remainders, and which side receives them is a stated rule, not a preference.
  3. One pass can decide a question about infinity when the structure repeats.
  4. A nonzero net rotation closes the path. Four cycles bring the heading back and the displacements sum to zero.
  5. Store what you can skip. Keep only the nonzero entries so the loops never visit a zero.
  6. Every output line must be exactly the requested width, padding included.
  7. 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.

Text Justification

Core idea: You get a list of words and a fixed maxWidth, and must return lines that are each exactly maxWidth characters wide, fully justified. There are two phases. Pack: sweep left to right and greedily take as many words as fit on the current line, where a set fits if sum(word lengths) + (words - 1) <= maxWidth (one space per gap at minimum). Justify: a line with g gaps has maxWidth - sum(word lengths) spaces to spread. Give every gap spaces // g, and give the spaces % g leftover spaces one each to the leftmost gaps. Two kinds of line skip this rule and are left-justified (single spaces between words, then padding on the right): the last line, and any line with a single word (it has no gap to spread into). One pass over the words, O(total characters).


Sign in to continue reading

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

Sign in to read the full lesson

Sign in to MAANG.io

Use your Google or Microsoft account — no password to remember.

Continue with Google Continue with Microsoft

Please accept the terms above to continue.