A line can contain the correct words and still be wrong: one space in the wrong gap, one missing trailing space, or full justification applied to the final line is enough to fail.

The reliable Text Justification solution is a deterministic simulation:

1. Scan left to right and collect the maximum contiguous group of words that fits.
2. Render that group using one of three cases:
   • ordinary multi-word line,
   • one-word line,
   • final line.

The packing rule is greedy because the contract explicitly requires each line to contain as many words as possible. The difficult part is not choosing line breaks. It is preserving the exact width while applying the correct spacing rule.

Read the contract before writing code

The formatter must satisfy several obligations simultaneously:

• Preserve the input order.
• Pack the maximum number of words into each line.
• Make every output line exactly maxWidth characters long.
• For ordinary multi-word lines, distribute spaces across internal gaps.
• If the spaces do not divide evenly, assign the extra spaces to the leftmost gaps.
• Left-justify one-word lines with trailing spaces.
• Left-justify the final line with single spaces between words and trailing padding.

That gives the solution its shape immediately:

collect a maximal line
if it is a one-word line or the final line:
    use left justification
else:
    distribute spaces across internal gaps

The output must be checked by character count, not by appearance. Trailing spaces are invisible in most terminals and easy to miss during an interview.

Recognize the pattern: stateful simulation

This problem does not need dynamic programming or a search over possible line breaks. The specification already determines the line breaks.

The evolving state is small:

• line: the words currently being collected,
• word_chars: the total number of characters in those words,
• i: the index of the next unprocessed word.

When the next word fits, extend the state. When it does not, finalize the current state and begin a new line.

This is a useful recognition pattern:

Fixed input order + a local fit test + deterministic rendering rules usually indicates stateful simulation.

A more general typography engine could optimize global costs across lines, such as minimizing unevenness over an entire paragraph. That would be a different problem. Here, the contract says greedy maximal packing, so searching for alternative breaks is unnecessary overhead and creates more ways to violate the specification.

The algorithm has two distinct responsibilities:

1. Collection: decide which words belong to the line.
2. Rendering: decide where the spaces go.

Keep those responsibilities separate in your reasoning, even if the final implementation uses one outer loop. Packing bugs and spacing bugs are different bugs.

Collect each maximal line

Suppose the current line contains k words and their total character count is word_chars.

Adding a candidate word requires:

• the candidate's characters,
• one separator between the candidate and each existing word.

So the candidate fits exactly when:

[ \text{word_chars} + k + \text{len(candidate)} \leq \text{maxWidth} ]

The value k is the number of separators that will exist after adding the candidate.

Do not build a partially formatted string just to test this. The formatted string contains spacing decisions that are irrelevant during collection. Track the word-character total directly.

For maxWidth = 16, the beginning of the canonical example behaves like this:

Candidate line	Word characters	Minimum separators	Occupied width
What	4	0	4
What must	8	1	9
What must be	10	2	12
What must be acknowledgment	24	3	27

acknowledgment does not fit, so the first line is finalized as the maximal block:

["What", "must", "be"]

The next line starts with acknowledgment. It cannot accept shall, so it becomes a one-word line. The final two words form the last line:

["shall", "be"]

The scan never reorders words and never skips a candidate. When a candidate fails, it remains the first word considered for the next line.

Derive the spacing arithmetic

For an ordinary line containing at least two words, define:

• word_chars: total characters used by the words,
• gaps = len(line) - 1,
• spaces = maxWidth - word_chars.

The spaces value is the total number of space characters available for all internal gaps. It does not include a separate “minimum separator” amount. Every internal gap receives its final allocation from this total.

Divide the total spaces into a quotient and remainder:

[ \text{base}, \text{remainder} = \operatorname{divmod}(\text{spaces}, \text{gaps}) ]

Then:

• the first remainder gaps receive base + 1 spaces,
• every remaining gap receives base spaces.

For example, if a line has three words, word_chars = 10, and maxWidth = 16:

[ \text{gaps} = 2 ]

[ \text{spaces} = 16 - 10 = 6 ]

[ \text{base}, \text{remainder} = \operatorname{divmod}(6, 2) = (3, 0) ]

Both gaps receive three spaces.

If the total were seven instead:

[ \operatorname{divmod}(7, 2) = (3, 1) ]

The left gap receives four spaces and the right gap receives three.

This is the full justification spaces rule in its most useful form: quotient for the baseline, remainder for the left-to-right extras.

Line type	Internal separators	Trailing padding
Ordinary multi-word line	Divide all remaining spaces across gaps; left gaps receive remainders	None
One-word line	No internal gaps	All unused width goes after the word
Final line	Exactly one space between adjacent words	All unused width goes at the end

The arithmetic proves the width by conservation:

[ \text{word characters} + \text{allocated gap spaces} = \text{maxWidth} ]

A one-word line has zero internal gaps, so division across gaps is undefined and conceptually wrong. All padding belongs on the right.

The final line uses single separators even if more space remains. Its unused width also belongs on the right.

Prove the invariant and the three branches

A correct implementation needs more than a successful sample. It needs a statement that remains true while the scan moves.

Line-collection invariant: Before each collection step, line contains a contiguous sequence of unprocessed words in input order, and those words fit within maxWidth using the minimum required separators.

When the next word fits, adding it preserves the invariant. When it does not fit, the current line is maximal: adding the next word would exceed the width. Finalizing it therefore obeys the greedy packing rule.

After finalization, the rejected word becomes the first word of the next line. Every word is processed exactly once.

Now consider rendering.

Ordinary multi-word line

The renderer selects the words in their original order. There are gaps internal gaps, and their allocations sum to spaces:

[ \underbrace{(\text{base}+1) + \cdots + (\text{base}+1)}{\text{remainder gaps}} + \underbrace{\text{base} + \cdots + \text{base}}{\text{remaining gaps}}

\text{spaces} ]

Therefore, the words plus all gap spaces occupy exactly maxWidth. Since the extra one-space allocations are applied to the first gaps, the leftmost-remainder rule is also satisfied.

One-word line

There are no internal gaps. The word consumes len(word) characters, and appending:

[ \text{maxWidth} - \text{len(word)} ]

spaces produces a line of exactly maxWidth characters.

Final line

Joining the words with one space between each adjacent pair preserves left justification. Appending the remaining width as trailing spaces produces the required fixed-width output without inserting extra spaces between words.

Together, these cases establish the main rendering invariant:

Rendering invariant: Every finalized line contains exactly the selected words in input order and has exactly maxWidth characters.

The collection invariant proves the line boundaries. The rendering invariant proves the contents of each line. That is the complete correctness argument.

Dry-run the cases that expose bugs

Use:

words = ["What", "must", "be", "acknowledgment", "shall", "be"]
maxWidth = 16

First line

The selected words are:

What must be

Their word characters total:

[ 4 + 4 + 2 = 10 ]

There are two gaps and six spaces to distribute:

[ 16 - 10 = 6 ]

[ \operatorname{divmod}(6, 2) = (3, 0) ]

So the rendered line is:

"What   must   be"

It contains 4 + 3 + 4 + 3 + 2 = 16 characters.

One-word line

The next selected line is:

["acknowledgment"]

The word has length 14, so it receives two trailing spaces:

"acknowledgment  "

No internal gap exists. Trying to apply the ordinary multi-word formula here would divide by zero or introduce a meaningless spacing decision.

Final line

The final line is:

["shall", "be"]

Its left-justified form is:

"shall be"

The text uses eight characters, so eight spaces are appended:

"shall be        "

It must not become:

"shall         be"

That would fully justify the final line and violate the contract.

When debugging, inspect output with repr() or print each line alongside len(line):

for line in result:
    print(repr(line), len(line))

Visible output hides trailing spaces. A length check does not.

Implement the Python solution

The implementation should mirror the derivation. The outer loop collects one maximal line at a time. The rendering branch makes the three cases explicit.

from typing import List


def full_justify(words: List[str], max_width: int) -> List[str]:
    result: List[str] = []
    i = 0

    while i < len(words):
        # Collect the largest line that fits using minimum separators.
        line = [words[i]]
        word_chars = len(words[i])
        i += 1

        while i < len(words):
            candidate = words[i]

            # len(line) is the number of separators needed after
            # adding this candidate.
            required = word_chars + len(line) + len(candidate)

            if required > max_width:
                break

            line.append(candidate)
            word_chars += len(candidate)
            i += 1

        is_last_line = i == len(words)

        # One-word lines and the final line are left-justified.
        if len(line) == 1 or is_last_line:
            text = " ".join(line)
            result.append(text + " " * (max_width - len(text)))
            continue

        # Ordinary multi-word line:
        # distribute all remaining spaces across internal gaps.
        gaps = len(line) - 1
        spaces = max_width - word_chars
        base, remainder = divmod(spaces, gaps)

        pieces: List[str] = []

        for gap_index in range(gaps):
            pieces.append(line[gap_index])

            gap_width = base + (1 if gap_index < remainder else 0)
            pieces.append(" " * gap_width)

        pieces.append(line[-1])
        result.append("".join(pieces))

    return result

The variable meanings are deliberately direct:

• line is the current contiguous block of words.
• word_chars excludes spaces, which makes the remaining space budget explicit.
• required is the exact minimum width after adding a candidate.
• gaps and spaces express the quotient-and-remainder derivation without reconstructing it from a partially formatted string.
• remainder is consumed from left to right through gap_index < remainder.

The final-line test occurs after collection. That matters because the final line is identified by the scan reaching the end of the input, not by its number of words. A final line may contain one word or several.

Complexity, edge cases, and interview checks

Let:

• C be the total number of input word characters,
• O be the total number of characters in the returned lines, including spaces.

The scan examines each input word once. Rendering writes each returned character once, so the total work is:

[ O(C + O) ]

This is the honest complexity for a formatter. Describing the algorithm only as O(n) hides the cost of constructing the output strings. If n means the number of words, the character-level work still depends on word lengths and emitted padding.

The returned result itself requires O(O) space. The temporary current line stores references to the words in one collected line, and the fragment list used during rendering is proportional to that line's output. The output space is unavoidable because the function must return every formatted line.

Targeted tests should check the contract directly:

• A word whose length is exactly maxWidth.
• A shorter line containing only one word.
• A line where the next word fails to fit.
• Uneven space distribution, such as seven spaces over two gaps.
• Several complete ordinary lines.
• A final line containing multiple words.
• A final line containing one word.
• A single-word input.

For every test, verify:

all(len(line) == max_width for line in result)

Also verify:

• input order is preserved,
• no line begins with a space,
• ordinary-line remainders go to the left,
• one-word lines have only trailing padding,
• the final line has single internal separators,
• trailing spaces are present when required.

Common failures are mechanical:

1. Forgetting separator cost during collection.
   Adding a candidate requires one separator per existing word in the line.

2. Using word_chars as if it already included spaces.
   Keep word characters and gap characters separate until rendering.

3. Giving remainder spaces to the right.
   The condition is gap_index < remainder, not a reverse loop.

4. Applying full justification to the final line.
   The final line always uses single spaces between words.

5. Treating a one-word line as an ordinary line.
   It has no internal gaps. Pad on the right.

6. Trusting visual output.
   Use repr() and explicit length checks. Invisible characters still count.

The transferable rule is simple: when a specification gives you a deterministic scan, a compact evolving summary, and exact output obligations, separate collection from rendering. Name the invariant. Branch only where the contract changes. Then make the final check mechanical: every emitted line preserves order and has length maxWidth.