LeetCode 68 – Text Justification

Text Justification is the problem that punishes people who start typing immediately. There is no algorithmic difficulty at all — pack words greedily, then pad — and it is still one of the highest failure rates on the list, because the spacing rules have four interacting special cases and each one is a silent off-by-one.

The problem

Given an array of words and a width maxWidth, format the text so every line is exactly maxWidth characters and fully justified: pack as many words per line as fit, and distribute spaces between them as evenly as possible. When the spaces do not divide evenly, the left gaps get the extra ones. The last line is left-justified with single spaces, padded on the right.

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

  "This    is    an"      3 words, 2 gaps, 6 spaces -> 3 and 3
  "example  of text"      3 words, 2 gaps, 3 spaces -> 2 and 1  (left gap gets more)
  "justification.  "      LAST line: left-justified

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

  "What   must   be"
  "acknowledgment  "      single word: left-justified, NOT stretched
  "shall be        "      last line

Split it in two before writing anything

The whole problem is two independent halves, and mixing them is what makes it hard:

1. Which words go on this line? Pure greedy — take words until the next one will not fit.
2. How is this line padded? Pure arithmetic on a fixed word list.

Say that out loud and write them as two loops, or a loop and a helper. Interviewers who have seen this problem a hundred times are largely watching whether you impose that structure.

The fitting test, which is where the first bug lives

Words on a line need at least one space between them, so a candidate line of k words occupies sum(lengths) + (k - 1) characters minimum. The cleanest way to write the test avoids the - 1 entirely: track lettersAndOneSpaceEach = sum(lengths + 1), and the line fits while that minus one is within the width.

line "abc" "de"      letters 5, gaps 1  -> minimum width 6
adding "fghi"        letters 9, gaps 2  -> minimum width 11

Greedy is provably right here because the words must stay in order and every word must be placed: deferring a word that fits can never let more words fit later, it only makes the current line sparser.

The four padding cases

This is the part to enumerate before coding, not discover while debugging:

The first two collapse into one branch — both are "join with single spaces, then pad right" — which is worth noticing, because it turns four cases into two.

And the last two collapse too. Giving the leftmost remainder gaps one extra space is exactly base + (gapIndex < remainder ? 1 : 0), so there is no separate even case at all. Two branches total.

Java

class Solution {
    public List<String> fullJustify(String[] words, int maxWidth) {
        List<String> lines = new ArrayList<>();
        int i = 0;

        while (i < words.length) {
            // 1. Which words fit? `width` counts each word plus one trailing space,
            //    so the real minimum is width - 1.
            int j = i, width = 0;
            while (j < words.length && width + words[j].length() <= maxWidth) {
                width += words[j].length() + 1;
                j++;
            }

            // 2. Pad them.
            lines.add(build(words, i, j, maxWidth, j == words.length));
            i = j;
        }

        return lines;
    }

    private String build(String[] words, int from, int to, int maxWidth, boolean lastLine) {
        int count = to - from;
        StringBuilder sb = new StringBuilder();

        if (lastLine || count == 1) {
            // Left-justified: single spaces, then pad the right.
            for (int k = from; k < to; k++) {
                if (k > from) sb.append(' ');
                sb.append(words[k]);
            }
            while (sb.length() < maxWidth) sb.append(' ');
            return sb.toString();
        }

        int letters = 0;
        for (int k = from; k < to; k++) letters += words[k].length();

        int gaps = count - 1;
        int base = (maxWidth - letters) / gaps;      // spaces in every gap
        int extra = (maxWidth - letters) % gaps;     // ...one more in the leftmost `extra` gaps

        for (int k = from; k < to; k++) {
            sb.append(words[k]);
            if (k < to - 1) {
                int spaces = base + (k - from < extra ? 1 : 0);
                for (int s = 0; s < spaces; s++) sb.append(' ');
            }
        }

        return sb.toString();
    }
}

The width + words[j].length() <= maxWidth test is the compact form of the fitting rule: width already includes a trailing space for every word taken so far, which is precisely the gap the new word needs. Getting this to read cleanly is worth the thirty seconds it takes to convince yourself, because the +1/-1 version of the same test is where the bug goes.

Python

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

        while i < len(words):
            j, width = i, 0
            while j < len(words) and width + len(words[j]) <= maxWidth:
                width += len(words[j]) + 1
                j += 1

            row = words[i:j]
            if j == len(words) or len(row) == 1:          # last line, or a single word
                lines.append(" ".join(row).ljust(maxWidth))
            else:
                letters = sum(len(w) for w in row)
                gaps = len(row) - 1
                base, extra = divmod(maxWidth - letters, gaps)

                line = ""
                for k, word in enumerate(row[:-1]):
                    line += word + " " * (base + (1 if k < extra else 0))
                lines.append(line + row[-1])

            i = j

        return lines

divmod gives the base width and the remainder in one call, which is exactly the shape of the rule. ljust handles the pad-right case, and " ".join the single spaces — the left-justified branch is genuinely one line in Python, which is worth using rather than transliterating the Java loop.

Complexity

Every word is examined a constant number of times and every output character is written once. There is nothing to improve, which is the tell that the grading is entirely on correctness.

Greedy is not optimal — and that is fine here

Worth one sentence if you have time. Greedy line-breaking can leave a very sparse line where looking ahead would have balanced two lines nicely. Knuth's algorithm — the one TeX uses — minimises a sum of squared raggedness with dynamic programming and produces visibly better paragraphs.

The problem specifies greedy, so implement greedy. Naming the alternative shows you know the difference between "the specified behaviour" and "the best behaviour", which is the useful distinction.

What the interviewer is checking

• That you separate word-packing from padding before writing code.
• The fitting test, including the mandatory single space between words.
• That the last line is left-justified, not stretched.
• That a single-word line is left-justified — the case people miss, since gaps would be zero and dividing by it throws.
• Extra spaces going to the left gaps.
• A word exactly as long as maxWidth.
• That every returned line is exactly maxWidth characters — worth asserting yourself before the interviewer checks.