Text Justification

How it works

Text justification requires packing words into lines of fixed width, distributing extra spaces as evenly as possible between words. The challenge is handling three distinct cases: regular lines with multiple words (distribute spaces evenly, with extra spaces going to the left gaps), single-word lines (pad with trailing spaces), and the last line (left-justified with trailing spaces).

The key is to greedily fit as many words as possible on each line, then calculate how to distribute the remaining space among the gaps between words.

Steps

1. Initialize an empty result list and track the current line's words and total character length.
2. For each word, check if it fits on the current line (considering at least one space between words):
   • If it fits, add it to the current line.
   • If not, justify the current line:
     • Calculate total extra spaces needed (maxWidth - length).
     • Divide spaces evenly among gaps. Distribute remaining spaces one extra each to leftmost gaps.
     • For single-word lines, add all spaces after the word.
     • Join words and add to result. Start a new line.
3. Handle the last line separately: left-justify (single space between words) and pad with trailing spaces.
4. Return the result.

Complexity

• Time complexity: O(n * m)
• Space complexity: O(n * m)

Where n is the number of words and m is the average length of the words.

Things to watch for

Forgetting to Account for Spaces When Checking Line Capacity

When determining if a word fits on the current line, you must include the mandatory spaces between words. The check should be length + word.length + numberOfWordsOnLine <= maxWidth, not just length + word.length <= maxWidth. Forgetting the space count causes lines to exceed the maximum width.

Division by Zero with Single-Word Lines

When a line contains only one word, there are zero gaps between words, leading to division by zero when calculating space distribution. Always use max(1, gaps) when dividing to handle single-word lines, where all extra spaces go after the word.

Incorrect Handling of the Last Line

The last line follows different rules: it should be left-justified with single spaces between words and trailing spaces to reach maxWidth. A common mistake is applying the same full-justification logic to the last line, resulting in incorrectly distributed spaces.

Uneven Space Distribution Going to Wrong Gaps

Extra spaces that cannot be evenly distributed must go to the leftmost gaps first. A mistake is distributing remainder spaces to the rightmost gaps or distributing them randomly. The remainder should decrement as you add one extra space to each gap from left to right.

Not Padding Lines to Exact Width

Every line must be exactly maxWidth characters. For single-word lines or the last line, forgetting to append trailing spaces results in lines shorter than required. Always calculate and append maxWidth - currentLineLength spaces at the end.

from typing import List

class Solution:
    def fullJustify(self, words: List[str], maxWidth: int) -> List[str]:
        res = []
        line, length = [], 0
        i = 0

        while i < len(words):
            if length + len(words[i]) + len(line) <= maxWidth:
                line.append(words[i])
                length += len(words[i])
                i += 1
            else:
                # Line complete
                extra_space = maxWidth - length
                remainder = extra_space % max(1, (len(line) - 1))
                space = extra_space // max(1, (len(line) - 1))
                for j in range(max(1, len(line) - 1)):
                    line[j] += " " * space
                    if remainder:
                        line[j] += " "
                        remainder -= 1
                res.append("".join(line))
                line, length = [], 0

        # Handling last line
        last_line = " ".join(line)
        trail_space = maxWidth - len(last_line)
        res.append(last_line + " " * trail_space)
        return res

class Solution {
public:
    vector<string> fullJustify(vector<string>& words, int maxWidth) {
        vector<string> res;
        vector<string> line;
        int length = 0, i = 0;

        while (i < words.size()) {
            if (length + words[i].size() + line.size() <= maxWidth) {
                line.push_back(words[i]);
                length += words[i].size();
                i++;
            } else {
                // Line complete
                int extra_space = maxWidth - length;
                int remainder = extra_space % max(1, (int)(line.size() - 1));
                int space = extra_space / max(1, (int)(line.size() - 1));

                for (int j = 0; j < max(1, (int)line.size() - 1); j++) {
                    line[j] += string(space, ' ');
                    if (remainder > 0) {
                        line[j] += " ";
                        remainder--;
                    }
                }

                string justified_line = accumulate(line.begin(), line.end(), string());
                res.push_back(justified_line);
                line.clear();
                length = 0;
            }
        }

        // Handling last line
        string last_line = accumulate(line.begin(), line.end(), string(),
                                      [](string a, string b) {
                                            return a.empty() ? b : a + " " + b;
                                        });
        int trail_space = maxWidth - last_line.size();
        last_line += string(trail_space, ' ');
        res.push_back(last_line);

        return res;
    }
};