Text Justification

Problem

You are given a list of words (non-empty strings of visible characters) and an integer maxWidth. Lay the words out into lines of text so that every line is exactly maxWidth characters long, and return the lines as a list of strings.

Formatting rules:

• Fill lines greedily: put as many words on each line as will fit, keeping at least one space between adjacent words. Words must stay in their original order and may not be split.
• A finished line (except the last) must be fully justified: pad the gaps between words with extra spaces so the line is exactly maxWidth wide. Spread the spaces as evenly as possible; when they cannot be divided evenly, the leftmost gaps receive the extra spaces.
• A line containing only one word is left-justified: the word, then spaces to fill the width.
• The final line is left-justified: single spaces between words, then trailing spaces to fill the width.

You may assume every word’s length is at most maxWidth, so any word fits on a line by itself.

Examples

Example 1 Input: words = ["This", "is", "an", "example", "of", "text", "justification."], maxWidth = 16 Output: ["This is an", "example of text", "justification. "] Three words fit on each of the first two lines; extra spaces go to the left gaps first, and the last line is left-justified and padded on the right.

Example 2 Input: words = ["What","must","be","acknowledgment","shall","be"], maxWidth = 16 Output: ["What must be", "acknowledgment ", "shall be "] "acknowledgment" cannot share a line with anything, and a one-word line is left-justified, not centered.

Example 3 Input: words = ["Listen"], maxWidth = 10 Output: ["Listen "] A single word is also the last line, so it is left-justified and padded to width 10.

Constraints

• 1 <= words.length <= 300
• 1 <= words[i].length <= 20 and words[i].length <= maxWidth
• 1 <= maxWidth <= 100

The input is small, so this problem is not about asymptotic complexity. It tests a correct, bug-free greedy simulation.

Think about it first

TL;DR

Greedy line packing + even space distribution — O(C) time where C is the total number of characters in the output, O(1) extra space beyond the output.

Approach 1 — Brute force

There is no meaningful brute force here. The problem statement forces the greedy packing (“put as many words as fit on each line”), so there is nothing to search over. Every approach below uses the same greedy simulation and differs only in how it distributes the spaces.

Approach 2 — Greedy packing + round-robin space dealing

Split the work into two independent phases per line. Packing needs only one number: adding a word to a line that already holds k words costs len(word) + 1 more characters (the word plus one mandatory space), so the line is full when length + len(word) + k > maxWidth. Justifying can then ignore the distinction between mandatory and extra spaces: deal the whole space budget maxWidth - length one space at a time across the gaps, cycling from the left. The leftmost gaps end up with the extra spaces.

from typing import List


def fullJustify(words: List[str], maxWidth: int) -> List[str]:
    res: List[str] = []
    line: List[str] = []   # words of the line being built
    length = 0             # sum of word lengths in `line`

    for word in words:
        # adding `word` needs len(word) chars plus one space per existing word
        if length + len(word) + len(line) > maxWidth:
            spaces = maxWidth - length          # total spaces to place
            gaps = len(line) - 1
            if gaps == 0:                       # single word: left-justify
                only = line[0]
                res.append(only + " " * spaces)
            else:
                for i in range(spaces):         # deal spaces round-robin
                    line[i % gaps] += " "
                res.append("".join(line))
            line, length = [], 0
        line.append(word)
        length += len(word)

    # the final line is left-justified with single spaces
    last = " ".join(line)
    res.append(last + " " * (maxWidth - len(last)))
    return res

Walkthrough of Example 1 (maxWidth = 16):

1. This (4), is (2), an (2) accumulate: after them length = 8, len(line) = 3. Trying example (7): 8 + 7 + 3 = 18 > 16, so flush. Budget spaces = 16 - 8 = 8, gaps = 2; dealing 8 spaces round-robin gives 4 to each gap → "This is an".
2. example (7), of (2), text (4): length = 13. Trying justification. (14): 13 + 14 + 3 = 30 > 16, flush. spaces = 3, gaps = 2; dealing 3 spaces gives gap 0 two and gap 1 one → "example of text", with the extra space on the left as required.
3. justification. is the last line: "justification." + " " * 2 → "justification. ".

Complexity: every output character is appended O(1) times, so O(C) time with C = len(words) * maxWidth characters of output; O(1) auxiliary space beyond the result (the line buffer holds at most one line).

Approach 3 — Greedy packing + divmod arithmetic

Instead of dealing spaces one at a time, compute each gap’s width directly. With space budget B and g gaps, q, r = divmod(B, g) gives every gap q spaces and the leftmost r gaps q + 1. This is the same greedy packing driven by an explicit two-pointer scan (i = first word of the line, j = one past the last), which some find easier to reason about than the streaming buffer. It also merges the two left-justified special cases: the last line and a one-word line share one branch.

from typing import List


def fullJustify(words: List[str], maxWidth: int) -> List[str]:
    res: List[str] = []
    n = len(words)
    i = 0
    while i < n:
        # greedily extend j while the words i..j fit with single spaces
        j, length = i, 0
        while j < n and length + len(words[j]) + (j - i) <= maxWidth:
            length += len(words[j])
            j += 1

        gaps = j - i - 1
        if j == n or gaps == 0:
            # last line, or a single-word line: left-justify
            row = " ".join(words[i:j])
            row += " " * (maxWidth - len(row))
        else:
            q, r = divmod(maxWidth - length, gaps)
            parts: List[str] = []
            for k in range(i, j - 1):
                parts.append(words[k])
                parts.append(" " * (q + (1 if k - i < r else 0)))
            parts.append(words[j - 1])
            row = "".join(parts)

        res.append(row)
        i = j
    return res

Walkthrough of Example 2 (words = ["What","must","be","acknowledgment","shall","be"], maxWidth = 16):

1. i = 0: j advances past What, must, be (length = 10, check for acknowledgment: 10 + 14 + 3 = 27 > 16), stopping at j = 3. gaps = 2, divmod(16 - 10, 2) = (3, 0): both gaps get exactly 3 spaces → "What must be".
2. i = 3: only acknowledgment fits (14 + 5 + 1 = 20 > 16 with shall), so j = 4 and gaps = 0 → left-justify branch → "acknowledgment ".
3. i = 4: shall be fits (length = 7) and j = 6 = n, so the last-line branch runs → "shall be" + 8 spaces → "shall be ".

Complexity: identical to Approach 2 — O(C) time over the output characters, O(1) auxiliary space. The difference is purely stylistic: arithmetic per gap instead of a dealing loop, so the justify step does O(g) work per line rather than O(B).

Common pitfalls

• Forgetting the two left-justified cases. The last line AND any single-word line use single-space/left padding; centering a lone word or fully justifying the last line are the classic wrong answers.
• Off-by-one in the fit test. A line holding k words needs k mandatory spaces to accept word k + 1 — writing length + len(word) > maxWidth (no gap term) overpacks lines.
• Putting extra spaces in the wrong gaps. The remainder spaces belong to the leftmost gaps. A right-to-left dealing loop violates this and still passes on symmetric examples, so it is easy to miss.
• Lines of the wrong width. Every line must be exactly maxWidth — an easy self-check is asserting len(row) == maxWidth before appending while you debug.

Pattern takeaway

When a problem states the algorithm directly (greedy, deterministic rules), the work is decomposition rather than invention. Separate “which items form this group” from “how the group is rendered,” fix the arithmetic that drives each phase (here, k words means k - 1 mandatory gaps), and write the special cases (last group, singleton group) as explicit branches. This two-phase structure applies to most simulation-heavy array problems.