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.
Intuition
The problem is pure simulation — no clever algorithm, just careful bookkeeping. You greedily pack as many words as fit on each line, then distribute spaces. The tricky part is the space distribution: if a line has k gaps between words and needs s extra spaces, each gap gets s // k extra spaces, and the first s % k gaps get one more. The last line and lines with a single word are left-justified instead of fully justified. Getting the edge cases right — single-word lines, the last line, and integer division of spaces — is where most bugs hide.
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
Greedily pack words into each line
Walk through the words array. For each line, keep adding words as long as the total character count plus one space between each pair does not exceed maxWidth. Track the starting index and ending index of words on the current line.
Distribute spaces for full justification
For a line with k words (and k-1 gaps), the total space to distribute is maxWidth - total_chars. Each gap gets at least space_each = total_space // (k - 1) spaces, and the first extra = total_space % (k - 1) gaps get one additional space. Build the line by concatenating words with their computed spacing.
Handle single-word lines and the last line differently
If a line has only one word, left-justify it and pad the rest with spaces. The last line is also left-justified: words separated by single spaces, and the remainder padded with spaces. These are the two exceptions to the full-justification rule.
Solution
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.