Text Justification
Text Justification: given an array of words and a width maxWidth, format the text so that each line has exactly maxWidth characters, fully justified (left and right). The last line is left-justified with no extra spacing.
- 1 <= words.length <= 300
- 1 <= words[i].length <= 20
- words[i] consists of only English letters and symbols.
- 1 <= maxWidth <= 100
- words[i].length <= maxWidth
Intuition
Text justification formats words into lines of exactly maxWidth characters, distributing spaces so both edges align. It is a Hard problem not for its algorithm but for the number of rules that must all hold at once.
The greedy line-packing is straightforward:
- Fit as many words on each line as possible, where k words need at least k − 1 spaces between them, so the line holds while wordLengths + wordCount − 1 <= maxWidth.
The difficulty is entirely in the space distribution, which has three distinct cases.
For a normal line, the spare spaces divide among the gaps. When they do not divide evenly, the leftmost gaps receive the extra — a line with 7 spaces across 3 gaps gets 3, 2, 2, not 2, 2, 3. Distributing extras to the right is the classic wrong answer.
A line holding one word has no gaps at all, so it is left-justified and padded entirely on the right. Dividing by a gap count of zero is the crash this case causes.
The last line is always left-justified with single spaces and right padding, regardless of how much room remains. This rule is stated plainly in the problem and is still the most frequently missed.
Every line must be exactly maxWidth characters — no more, no fewer — so the padding arithmetic has to be exact rather than approximate.
There is no clever insight to find here. The problem rewards careful case analysis, and the productive approach is to enumerate the three cases explicitly rather than trying to unify them.
Each word is placed once, giving O(total characters) time and space.
Text justification is a simulation problem with no algorithmic trick — the difficulty is in handling the space distribution and the special cases (last line, single-word line). When a problem asks you to format text into fixed-width lines with even spacing, greedy packing plus careful modular arithmetic on the gaps is the approach.
Approach
Before reading on: price up what the direct approach costs here, then ask what you are recomputing on every character that could be carried instead. Aim for O(n) time and O(n) space.
Pack lines greedily
Fit as many words as possible per line. k words need at least k − 1 spaces, so the line holds while lengths + count − 1 <= maxWidth.
Distribute extras to the left
When spare spaces do not divide evenly, the leftmost gaps take the extra — 7 spaces across 3 gaps gives 3, 2, 2. Padding rightward is the classic error.
Handle the single-word line
One word means zero gaps, so pad entirely on the right. Dividing by a gap count of zero is the crash this case causes.
Left-justify the last line
The final line uses single spaces with right padding, regardless of remaining room. Stated plainly in the problem and still the most-missed rule.
Verify exact width
Every line must be exactly maxWidth characters. The padding arithmetic has to be precise, not approximate.
Enumerate the cases explicitly
There is no unifying insight here — the problem rewards careful case analysis. Writing the three cases separately beats trying to merge them.
Cost of the approach
Each word is placed once and each output character written once, giving O(total characters) time and space.
Solution & live demo
Common pitfalls
Distributing extra spaces to the right gaps instead of the left
for i in range(extra):
gaps[k - 2 - i] += 1for i in range(extra):
gaps[i] += 1The problem specifies that when spaces cannot be evenly distributed, the left slots get more. Distributing right-to-left produces lines that are visually back-loaded, failing the expected output.
Forgetting to left-justify the last line
# apply full justification to every line
if is_last_line:
line = ' '.join(words_in_line)
line += ' ' * (maxWidth - len(line))The last line must be left-justified with single spaces, not fully justified. Full-justifying it spreads words unnaturally across the width.
Counting maxWidth characters including inter-word spaces during packing
if total_chars + len(word) <= maxWidth:
if total_chars + len(word) + num_words_on_line <= maxWidth:
When checking if a word fits, you must account for the spaces between words already on the line. Ignoring them overpacks the line, and the justified output exceeds maxWidth.
Edge cases
Left-justify the word and pad with spaces to reach maxWidth. No gap distribution needed.
Words are separated by single spaces, then the line is right-padded with spaces to maxWidth. No full justification.
maxWidth characters longThat word fills the entire line by itself. It becomes a single-word line, padded with zero extra spaces.