Generated by Codex with GPT-5

Quick facts

What the problem is really asking

The input is a list of words and a fixed line width. The task is to break the words into lines and return the exact text layout that a formatter would produce.

The important part is that the problem does not ask for the “nicest-looking” paragraph in a vague sense. It gives exact rules:

  • each non-final line should contain as many words as possible
  • spaces on those lines should be spread as evenly as possible
  • if the spaces do not divide evenly, the leftmost gaps get the extra spaces
  • the last line is left-justified

Once those rules are read carefully, the problem stops being about global optimization and becomes a line-building simulation problem.

Why the greedy strategy is correct

The first decision is where a line should end.

That part is greedy: keep adding the next word while the line still fits, and stop exactly when one more word would overflow.

This is not just a good heuristic. It is forced by the problem statement.

If a non-final line can still fit another word and that word is skipped anyway, then the line does not contain as many words as possible, so the output is invalid. That means every line break is determined by the longest prefix of remaining words that still fits.

After the words for a line are fixed, the spacing is also deterministic:

  • if it is the last line, join words with single spaces and pad the end
  • if the line has only one word, put that word first and pad the rest with spaces
  • otherwise distribute maxWidth - total_letters spaces across the gaps

So the whole solution is:

  1. greedily choose the words for the current line
  2. format that line according to whether it is the last line or a normal line
  3. move to the next line

Because each word is assigned to exactly one line and each output character is written once, this is already asymptotically optimal for the required output size.

The key spacing math

Suppose a non-final line contains k words with total_letters letters combined.

Then the number of spaces that must be inserted is:

total_spaces = maxWidth - total_letters

Those spaces need to be spread across k - 1 gaps.

If the line has more than one gap:

  • base_spaces, extra_spaces = divmod(total_spaces, k - 1)
  • every gap gets base_spaces
  • the first extra_spaces gaps get one additional space

That exactly matches the “left side gets the extra spaces” rule.

How to derive this in an interview

A clean interview path is:

  1. Start from the line-break rule. Ask: “How do I know which words belong to the current line?” The answer is to keep adding words until the next one would overflow.
  2. Observe that once the line’s words are known, the remaining work is pure formatting. There is no ambiguity left.
  3. Split the implementation into two helpers: one helper chooses the maximal word range for a line, and another helper turns that range into the final string.

That separation makes the code easy to reason about and keeps the correctness argument simple:

  • the greedy helper guarantees each non-final line packs as many words as possible
  • the formatting helper guarantees spaces are distributed exactly as required

Best approach

The intended solution is greedy simulation.

It runs in O(total output characters) time and uses O(maxWidth) temporary space per line, or O(total output characters) overall if the returned list is counted. There is no meaningful asymptotic improvement beyond that because the algorithm must produce the full text anyway.

There are different implementation styles:

  • two pointers plus a running letter count
  • a current-line list that is flushed when the next word no longer fits

They are the same core algorithm. The version below uses explicit helpers because it keeps the line-selection logic separate from the spacing logic.

Python solution

The implementation below uses three small helpers:

  • find_line_end chooses the largest range of words that fits on the current line
  • build_left_justified_line handles the last line and the single-word case
  • build_fully_justified_line handles normal lines with even space distribution

That keeps the main function short while still making the spacing rules explicit.

from typing import List, Tuple


def validate_input(words: List[str], max_width: int) -> None:
    """Validate the basic assumptions used by the formatter."""
    if max_width <= 0:
        raise ValueError("max_width must be positive.")

    for word in words:
        if len(word) > max_width:
            raise ValueError("Each word must fit within max_width.")


def find_line_end(words: List[str], start_index: int, max_width: int) -> Tuple[int, int]:
    """
    Return the inclusive end index for the current line and the total
    number of letters in the chosen words.
    """
    end_index = start_index
    total_letters = len(words[start_index])

    while end_index + 1 < len(words):
        next_word_length = len(words[end_index + 1])
        current_gap_count = end_index - start_index + 1

        # Adding another word requires at least one new separating space.
        projected_width = total_letters + next_word_length + current_gap_count
        if projected_width > max_width:
            break

        end_index += 1
        total_letters += next_word_length

    return end_index, total_letters


def build_left_justified_line(
    words: List[str],
    start_index: int,
    end_index: int,
    max_width: int,
) -> str:
    """Join words with single spaces and pad the right side."""
    line = " ".join(words[start_index : end_index + 1])
    return line + (" " * (max_width - len(line)))


def build_fully_justified_line(
    words: List[str],
    start_index: int,
    end_index: int,
    total_letters: int,
    max_width: int,
) -> str:
    """Distribute spaces as evenly as possible, favoring leftmost gaps."""
    gap_count = end_index - start_index
    if gap_count == 0:
        return build_left_justified_line(words, start_index, end_index, max_width)

    total_spaces = max_width - total_letters
    base_spaces, extra_spaces = divmod(total_spaces, gap_count)

    parts: List[str] = []
    for gap_index in range(gap_count):
        parts.append(words[start_index + gap_index])

        spaces_for_this_gap = base_spaces
        if gap_index < extra_spaces:
            spaces_for_this_gap += 1

        parts.append(" " * spaces_for_this_gap)

    parts.append(words[end_index])
    return "".join(parts)


def full_justify_text(words: List[str], max_width: int) -> List[str]:
    """Format words into fully justified lines."""
    validate_input(words, max_width)

    justified_lines: List[str] = []
    start_index = 0

    while start_index < len(words):
        end_index, total_letters = find_line_end(words, start_index, max_width)
        is_last_line = end_index == len(words) - 1

        if is_last_line:
            line = build_left_justified_line(words, start_index, end_index, max_width)
        else:
            line = build_fully_justified_line(
                words,
                start_index,
                end_index,
                total_letters,
                max_width,
            )

        justified_lines.append(line)
        start_index = end_index + 1

    return justified_lines


class Solution:
    def fullJustify(self, words: List[str], maxWidth: int) -> List[str]:
        """LeetCode entry point."""
        return full_justify_text(words, maxWidth)

Interview follow-ups

What changes if the problem becomes “word wrap” and asks for the most visually pleasing paragraph instead of this exact formatting rule?

That becomes a different problem. Once the goal is to minimize raggedness or some penalty function, greedy no longer works because leaving a little extra room on the current line might make several later lines much better. The standard approach is dynamic programming over line breaks: for each starting word, try every possible ending word that fits, compute the line penalty, and combine it with the best answer for the suffix. This works because the problem now has a real global objective, so line decisions interact with each other. The tradeoff is complexity: the usual DP solution is around O(n^2) time and O(n) or O(n^2) space depending on how it is implemented, which is slower than the original greedy formatter.

How would you adapt this if the caller wanted to stream lines one at a time instead of returning a full list?

The same greedy line-selection logic still works. The only change is the output interface: instead of appending each formatted line to a list, the function can yield each line immediately or write it to a file-like object. That works because each line is finalized before the next line is processed, so future words never change an already emitted line. The complexity stays essentially the same, but the memory profile improves because the algorithm only needs to keep the current line’s bookkeeping instead of the whole result in memory at once.

What if words are allowed to be longer than maxWidth and the interviewer asks for hyphenation or splitting?

Then the first step is to define a splitting policy, because the original problem avoids that complication entirely. A practical solution is to preprocess each oversized word into chunks that fit, optionally adding hyphens according to the chosen rule, and then run the same justification algorithm on the expanded token stream. This works because once every emitted token fits inside maxWidth, the line-building and spacing logic becomes identical to the original problem. The tradeoff is that correctness now depends on the splitting rule, and the implementation becomes more domain-specific because real hyphenation is a language problem, not just a spacing problem.

Practical takeaway

This is a good interview problem because the implementation looks fussy, but the core idea is simple:

  • greedily decide which words belong on the line
  • compute the exact number of spaces that must appear
  • distribute those spaces according to the rule for that kind of line

Once those three pieces are separated, the solution becomes straightforward and easy to defend.