Text Justification

Text Justification is a classic string-formatting problem. There is no clever data structure here — the whole challenge is being careful and greedy: fit as many words as the width allows on each line, then distribute the leftover spaces evenly.

The slow way first

You might try to decide line breaks by looking ahead — counting words to the end, balancing line lengths, minimizing raggedness. That is a much harder optimization problem and it is not what this question asks. The interview version uses a simple greedy rule, and overthinking it is the main way people get stuck.

The question to ask: while scanning words left to right, when does the current line become full? The line is full the moment adding one more word would push it past maxWidth.

The idea: greedy pack, then spread

Walk the words once, collecting them into a current line cur. Track length, the total letter count so far. Adding a word w also needs one space per existing word (that is len(cur) spaces). So if length + len(cur) + len(w) > maxWidth, the line is full: justify it, push it to the result, and start fresh.

To justify a full line: the leftover space is maxWidth - length. Split it across gaps = len(cur) - 1 gaps, handing them out one at a time from the left so earlier gaps get the extra when it does not divide evenly. The last line is special — single spaces, then pad the right.

Walk through it

Step through the animation. Words turn from gray to green as they are committed. We greedily add This, is, an (10 chars), then example would make 18 > 16, so the line is full. We spread 10 spaces over 2 gaps (5 each) and emit This is an. The rest — example, of, text — is the final line, so it is left-justified and right-padded.

Pseudocode

res, cur, length = [], [], 0
for each word w:
    if length + (len(cur) spaces) + len(w) > maxWidth:
        spaces = maxWidth - length            # leftover spaces to distribute
        gaps = max(1, len(cur) - 1)           # at least 1 to avoid div-by-zero
        hand them out one at a time, left to right (i % gaps)
        push the joined line to res
        reset cur and length
    add w to cur; length += len(w)
last line = single-spaced and padded on the right to maxWidth
return res + [last line]

The Python solution

def justify(words, maxWidth):
    res, cur, length = [], [], 0
    for w in words:
        if length + len(cur) + len(w) > maxWidth:
            spaces = maxWidth - length
            gaps = max(1, len(cur) - 1)
            for i in range(spaces):
                cur[i % gaps] += " "
            res.append("".join(cur))
            cur, length = [], 0
        cur.append(w); length += len(w)
    last = " ".join(cur).ljust(maxWidth)
    return res + [last]

• cur is the words on the current line; length is their combined letter count (no spaces yet).
• Line 4 is the overflow test: len(cur) is the number of single spaces already implied between the words on the line.
• spaces = maxWidth - length is exactly how many space characters must be inserted to fill the line.
• gaps = max(1, len(cur) - 1) — a one-word line has zero real gaps, so we force 1 to avoid dividing by zero (the space just goes after the word).
• i % gaps hands spaces out round-robin from the left, so the left gaps get the extra when it does not divide evenly.
• After the loop, cur holds the last line: join with single spaces and ljust to pad the right.

Complexity

We touch every word a constant number of times and write each output character once, so the work is linear in the size of the output text.

When this pattern shows up

Practice