Text Justification
Format text into fully justified lines by greedily packing words and distributing spaces
Problem Statement
Given an array of words and a width maxWidth, format the text so that each line is exactly maxWidth characters and fully justified (flush on both sides).
Pack as many words per line as possible, separated by at least one space. Distribute extra spaces as evenly as possible; if they do not divide evenly, the left gaps get more than the right ones.
The last line is left-justified: single spaces between words, padded on the right.
Input: words = ["This", "is", "an", "example", "of", "text", "justification."]
maxWidth = 16
Output: [
"This is an",
"example of text",
"justification. "
]Intuition
This problem is not algorithmically deep — it is a specification problem. The difficulty is holding three separate rules straight without letting them interfere.
The three rules
1. Greedy packing. Fit as many words on a line as possible. Greedy is correct here because the problem defines it that way — you are not minimising anything, just filling.
2. Space distribution. With k words there are k - 1 gaps. Extra spaces go to the leftmost gaps first.
3. Two exceptions. The last line, and any line holding a single word, are left-justified with single spaces and right padding.
The packing arithmetic
A line holding words w₁ … wₖ needs at least sum(lengths) + (k - 1) characters — the words plus one space per gap. Add a word only while that total stays within maxWidth.
The space arithmetic
Once the words are chosen, let slots = k - 1 and spaces = maxWidth - sum(lengths).
base = spaces // slots ← every gap gets at least this many
extra = spaces % slots ← the first `extra` gaps get one moreFor ["example", "of", "text"] with maxWidth = 16:
sum(lengths) = 7 + 2 + 4 = 13, slots = 2, spaces = 16 - 13 = 3
base = 3 // 2 = 1, extra = 3 % 2 = 1
gap 1 gets 1 + 1 = 2 spaces (it is within the first `extra` gaps)
gap 2 gets 1 = 1 space
"example" + " " + "of" + " " + "text" → "example of text" ✓ 16 charactersWatch it run
Approach
Greedily collect words for one line
Keep adding while current_length + len(word) + number_of_words <= maxWidth. The number_of_words term accounts for the minimum single space before each added word.
Detect the two special cases
If this is the last line, or the line has exactly one word → join with single spaces and pad on the right.
Otherwise distribute spaces
Compute base and extra, then build the line gap by gap, giving the first extra gaps one additional space.
Solution
def full_justify(words: list[str], max_width: int) -> list[str]:
"""Format words into fully justified lines of exactly max_width."""
lines: list[str] = []
line: list[str] = [] # words on the current line
letters = 0 # total characters of those words, no spaces
for word in words:
# +len(line) accounts for one space before each existing word.
if letters + len(word) + len(line) > max_width:
lines.append(_justify(line, letters, max_width))
line, letters = [], 0
line.append(word)
letters += len(word)
# The last line is left-justified, not fully justified.
lines.append(" ".join(line).ljust(max_width))
return lines
def _justify(line: list[str], letters: int, max_width: int) -> str:
"""Fully justify one line of words."""
if len(line) == 1:
return line[0].ljust(max_width) # a single word is left-justified
slots = len(line) - 1
spaces = max_width - letters
base, extra = divmod(spaces, slots)
parts: list[str] = []
for i, word in enumerate(line[:-1]):
# The first `extra` gaps get one additional space.
parts.append(word + " " * (base + (1 if i < extra else 0)))
parts.append(line[-1])
return "".join(parts)The three mistakes this problem is built around
1. Fully justifying the last line. It must be left-justified. Handle it after the loop, never inside.
2. Dividing by zero on a single-word line. slots = k - 1 is 0, so the division must be guarded by the single-word special case.
3. Distributing extra spaces to the right. The rule is explicitly left-biased. i < extra gives the leftmost gaps the surplus.
Why `letters + len(word) + len(line)` is the right test
letters is the words' characters with no spaces. len(line) is the number of words currently on the line, which equals the number of gaps that would exist after adding one more word. So the expression is exactly the minimum width of the line with the new word included.
Complexity Analysis
Time Complexity
O(n × maxWidth)
Space Complexity
O(n)
- Time — each word is examined once during packing, and building each line costs work proportional to
maxWidth. - Space — the output lines, plus the small buffer holding the current line's words.
Edge Cases
Related Problems
- Zigzag Conversion — another layout-simulation problem
- Reverse Words in a String — whitespace normalisation
- Candy — a greedy rule applied carefully in stages