LeetCode 68: Text Justification

Problem Restatement

We are given a list of words and an integer maxWidth.

We need to format the words into lines of exactly maxWidth characters.

The rules are:

1. Pack as many words as possible into each line.
2. Each line must have exactly maxWidth characters.
3. For normal lines, spaces should be distributed as evenly as possible between words.
4. If spaces cannot divide evenly, the left gaps get more spaces than the right gaps.
5. The last line is left-justified: one space between words, then trailing spaces.
6. A line with only one word is also left-justified.

Each word has length at least 1 and at most maxWidth, and the input contains at least one word. The official constraint allows up to 300 words.

Input and Output

Function shape:

def fullJustify(words: list[str], maxWidth: int) -> list[str]:
    ...

Examples

For:

words = ["This", "is", "an", "example", "of", "text", "justification."]
maxWidth = 16

The answer is:

[
    "This    is    an",
    "example  of text",
    "justification.  ",
]

The first line has words:

["This", "is", "an"]

Their total word length is:

4 + 2 + 2 = 8

The line width is 16, so it needs:

16 - 8 = 8

spaces.

There are two gaps:

This _ is _ an

So each gap gets four spaces:

"This    is    an"

The second line has:

["example", "of", "text"]

Total word length:

7 + 2 + 4 = 13

Spaces needed:

16 - 13 = 3

There are two gaps. The left gap gets two spaces, and the right gap gets one space:

"example  of text"

The last line is left-justified:

"justification.  "

First Thought: Add Words One by One

The main task has two parts:

1. Decide which words belong to the current line.
2. Build that line with the correct spaces.

The first part is greedy.

We keep adding words while the line can still fit inside maxWidth.

When we cannot add the next word, we justify the current line and start a new one.

Key Insight

To decide whether a word fits, we need to count both:

1. Word characters
2. Minimum spaces between words

Suppose the current line has words with total length line_len.

If we add another word, and the current line already has len(line_words) words, then we need at least one space before the new word.

So the condition is:

line_len + len(line_words) + len(word) <= maxWidth

Here, len(line_words) is the number of minimum spaces needed if we add the new word.

For example, if the current line has two words, adding a third word requires two minimum gaps total.

Space Distribution

Once a line is full, we know:

total_spaces = maxWidth - total_word_length

If the line has more than one word, the number of gaps is:

gaps = len(line_words) - 1

Each gap gets at least:

total_spaces // gaps

spaces.

The leftmost gaps get one extra space while the remainder lasts:

extra = total_spaces % gaps

So for gap index i:

spaces = base + (1 if i < extra else 0)

This exactly matches the rule that left gaps receive more spaces when the spaces do not divide evenly.

Last Line and Single-Word Lines

The last line is different.

It should have one space between words, then trailing spaces at the end.

For example:

["shall", "be"]

with maxWidth = 16 becomes:

"shall be        "

A single-word line follows the same left-justified rule:

"acknowledgment  "

So we can handle both cases with:

line = " ".join(line_words)
line += " " * (maxWidth - len(line))

Algorithm

Maintain:

ans = []
line_words = []
line_len = 0

For each word:

1. If the word fits in the current line, add it.
2. Otherwise, justify the current line and append it to ans.
3. Start a new line with the current word.

After processing all words, left-justify the last line and append it.

Return ans.

Correctness

The algorithm greedily adds a word to the current line exactly when the current words, the new word, and the minimum required spaces can fit inside maxWidth. Therefore each line contains as many words as possible before moving to the next line.

For every non-last line with multiple words, the algorithm computes the total number of spaces needed to make the line length exactly maxWidth. It divides those spaces across the gaps using quotient and remainder. Every gap receives either base or base + 1 spaces, so the distribution is as even as possible. Since the extra one-space gaps are assigned from left to right, left gaps receive more spaces when needed.

For a last line or a single-word line, the algorithm joins words with one space and pads the remaining width at the end. This matches the left-justification rule.

Every input word is added to exactly one line, and every output line is padded to exactly maxWidth. Therefore the returned list satisfies all problem requirements.

Complexity

Auxiliary working space, excluding the output, is O(maxWidth) for the current line.

Implementation

class Solution:
    def fullJustify(
        self,
        words: list[str],
        maxWidth: int,
    ) -> list[str]:

        ans = []
        line_words = []
        line_len = 0

        def justify(words_in_line: list[str], words_len: int) -> str:
            if len(words_in_line) == 1:
                line = words_in_line[0]
                return line + " " * (maxWidth - len(line))

            total_spaces = maxWidth - words_len
            gaps = len(words_in_line) - 1

            base = total_spaces // gaps
            extra = total_spaces % gaps

            parts = []

            for i in range(gaps):
                parts.append(words_in_line[i])

                spaces = base
                if i < extra:
                    spaces += 1

                parts.append(" " * spaces)

            parts.append(words_in_line[-1])

            return "".join(parts)

        for word in words:
            if line_len + len(line_words) + len(word) <= maxWidth:
                line_words.append(word)
                line_len += len(word)

            else:
                ans.append(justify(line_words, line_len))

                line_words = [word]
                line_len = len(word)

        last_line = " ".join(line_words)
        last_line += " " * (maxWidth - len(last_line))
        ans.append(last_line)

        return ans

Code Explanation

We keep the output and the current line state:

ans = []
line_words = []
line_len = 0

line_len stores only the total length of words, not spaces.

The helper function formats a completed non-last line:

def justify(words_in_line: list[str], words_len: int) -> str:

If there is only one word, pad spaces at the end:

if len(words_in_line) == 1:
    line = words_in_line[0]
    return line + " " * (maxWidth - len(line))

Otherwise, compute spaces:

total_spaces = maxWidth - words_len
gaps = len(words_in_line) - 1

Divide them evenly:

base = total_spaces // gaps
extra = total_spaces % gaps

Build the line from left to right:

for i in range(gaps):
    parts.append(words_in_line[i])

    spaces = base
    if i < extra:
        spaces += 1

    parts.append(" " * spaces)

Then append the final word:

parts.append(words_in_line[-1])

The main loop packs words greedily:

if line_len + len(line_words) + len(word) <= maxWidth:

If the word does not fit, justify the current line:

ans.append(justify(line_words, line_len))

Then start a new line:

line_words = [word]
line_len = len(word)

After all words are processed, the remaining line is the last line, so it is left-justified:

last_line = " ".join(line_words)
last_line += " " * (maxWidth - len(last_line))
ans.append(last_line)

Testing

def run_tests():
    s = Solution()

    assert s.fullJustify(
        ["This", "is", "an", "example", "of", "text", "justification."],
        16,
    ) == [
        "This    is    an",
        "example  of text",
        "justification.  ",
    ]

    assert s.fullJustify(
        ["What", "must", "be", "acknowledgment", "shall", "be"],
        16,
    ) == [
        "What   must   be",
        "acknowledgment  ",
        "shall be        ",
    ]

    assert s.fullJustify(
        ["Science", "is", "what", "we", "understand", "well",
         "enough", "to", "explain", "to", "a", "computer.",
         "Art", "is", "everything", "else", "we", "do"],
        20,
    ) == [
        "Science  is  what we",
        "understand      well",
        "enough to explain to",
        "a  computer.  Art is",
        "everything  else  we",
        "do                  ",
    ]

    assert s.fullJustify(["a"], 1) == ["a"]

    assert s.fullJustify(["a"], 3) == ["a  "]

    assert s.fullJustify(["a", "b", "c"], 3) == [
        "a b",
        "c  ",
    ]

    print("all tests passed")

run_tests()