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 tiny — this problem is not about asymptotic complexity but about a 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 itself forces the greedy packing (“put as many words as fit on each line”), so there is nothing to search over — the ladder starts at the naive greedy simulation and the approaches below differ only in how they distribute the spaces.

Approach 2 — Greedy packing + round-robin space dealing

The insight: split the work into two independent phases per line. Phase 1 (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. Phase 2 (justifying) can then forget about “mandatory” vs “extra” spaces entirely: deal the whole space budget maxWidth - length one space at a time across the gaps, cycling from the left — the leftmost gaps automatically end up with the extra spaces.

from typing import List


class Solution:
    def fullJustify(self, 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" — the extra space landed 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

The insight: instead of dealing spaces one at a time, compute each gap’s width in closed form. With space budget B and g gaps, q, r = divmod(B, g) means every gap gets q spaces and the leftmost r gaps get 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 many people find easier to reason about than the streaming buffer. It also naturally merges the two left-justified special cases: “last line” and “one-word line” share one branch.

from typing import List


class Solution:
    def fullJustify(self, 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; divmod remainders or a right-to-left dealing loop silently violate this and pass the eye test on symmetric examples.
• 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 hands you the algorithm in its statement (greedy, deterministic rules), the challenge is decomposition, not cleverness: isolate “which items form this group” from “how the group is rendered,” pin down the one arithmetic fact that drives each phase (here, k words ⇒ k - 1 mandatory gaps), and enumerate the special cases (last group, singleton group) as explicit branches. That two-phase, invariant-first structure is the reusable template for every simulation-heavy array problem.