Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
Greedily pack as many words as fit in `maxWidth` (each word plus one minimum space between). For a full line with multiple words, distribute the leftover spaces as evenly as possible across the gaps, giving the LEFTMOST gaps the extra spaces. Two special cases are LEFT-justified (padded on the right): the very last line, and any line containing a single word.
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you can decompose a fiddly spec into clean cases and implement exact spacing without off-by-one bugs — composure on a problem with many small rules rather than a clever insight.
Where candidates slip
Distributing extra spaces evenly instead of left-heavy, forgetting that single-word lines and the last line are left-justified, or producing lines that aren't exactly maxWidth wide.
How to stand out
Enumerate the three cases up front (full multi-word line, single-word line, last line), use divmod to distribute remainder spaces to the leftmost gaps, and verify each output line is exactly maxWidth long. Mention Knuth–Plass as the optimal-breaking generalization.
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachFirst decision previewGreedily pack words into a lineIs it the last line OR a single word?YesNoExplore the full treeCollapse the tree
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 2 · Optimal
Greedy Pack with Pointer Scan + Even Distribution (Optimal)
1Hint 1Explore hintHide hint
First decide which words go on each line. A word fits on the current line only if the current word-length sum, plus one space per existing word, plus the new word's length, stays within maxWidth.
2Hint 2Explore hintHide hint
Once a line's words are chosen, count leftover spaces = maxWidth − (sum of word lengths). Distribute them across the gaps as evenly as possible, giving leftmost gaps the remainder.
3Hint 3Explore hintHide hint
Handle two left-justified cases separately: the last line, and any line with a single word — join with single spaces and pad the right to maxWidth.
A · Core idea
Text Justification is a simulation problem: there's no clever trick, just a specification you must execute exactly. The algorithm has two clean phases — decide line membership (greedy packing), then format the line (space distribution) — and getting the second phase's edge cases right is the whole challenge.
Phase 1 — greedy packing with the correct fit test. Starting at word i, extend a window [i, j) adding words while they still fit. The subtle part is the fit test. If the line already holds numWords words with total character length lineLen, then adding the next word requires at least numWords separating spaces (one before each existing word's successor) plus the new word's length. So the word fits iff lineLen + numWords + len(word) ≤ maxWidth. The numWords term is the count of minimum single spaces — getting this term wrong (off by one) is the most common packing bug.
Phase 2 — distribute the leftover spaces, left-heavy. Once a line's words are fixed (and it's not the last line and has more than one word), the total space to insert is spaces = maxWidth − lineLen, spread over gaps = numWords − 1 slots. We compute each = spaces / gaps and extra = spaces % gaps. Every gap gets each spaces, and the first `extra` gaps get one additional space. That left-heavy rule is mandated by the prompt — for 7 spaces over 3 gaps you produce 3, 2, 2, not 2, 2, 3. Using divmod (or / and %) and a condition like (k − i) < extra keeps the extras on the left cleanly.
The two left-justified special cases. Two situations skip even distribution entirely. First, the last line: the spec says it must be left-justified with single spaces between words and the remainder as trailing padding. Second, a single-word line: there are zero gaps to distribute into, so dividing by gaps = 0 would crash — instead we place the word at the left and pad the right. Both reduce to 'join with single spaces, then append spaces until the line is maxWidth long'. Forgetting either case is the difference between accepted and wrong answer, and the single-word case can also be a literal divide-by-zero.
The final invariant to check. Every emitted line must be exactly maxWidth characters — never shorter, never longer. After building each line it's worth mentally asserting its length equals maxWidth; that single check catches most spacing mistakes.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
words = ["This","is","an","example","of","text","justification."], maxWidth = 16Interactive diagram
Distributing 8 spaces over 2 gaps vs 3 over 2 gaps
line 1 packEven case splits 4/4; uneven case is left-heavy (2/1), driven by spaces % gaps.
["This is an","example of text","justification. "]C · Code with teaching comments
D · Why it works and complexityO(total characters in output) timeO(maxWidth) spaceOpen the invariant and proofExplore the proofHide the proof
Separate 'which words' (greedy packing) from 'how to space them' (distribution). With that split, the only real intellectual content is the left-heavy divmod distribution and remembering the two left-justified cases — everything else is mechanical.
ComplexityO(total characters in output) time, O(maxWidth) space — Each word is examined a constant number of times to decide its line, and building the output writes each character once → O(total output characters), which is O(n · maxWidth) in the worst case. The per-line buffer is O(maxWidth) extra space.
E · Edge cases and pitfalls9single word longer alone fills < maxWidth — numWords == 1 branch → word left, rest padded right (no divide-by-zero on gaps).Explore edge casesHide edge cases
Edge cases handled
single word longer alone fills < maxWidthnumWords == 1 branch → word left, rest padded right (no divide-by-zero on gaps).last line with multiple wordsj == n branch → single spaces between words, trailing pad to maxWidth.a line that exactly fills maxWidth with min spacesspaces % gaps may be 0 → all gaps equal; still padded to exact width.every word equals maxWidthEach word is alone on its line → all left-justified single-word lines.
Pitfalls
- Off-by-one in the fit test — forgetting the (j - i) minimum-space term overpacks or underpacks the line.
- Distributing extra spaces right-heavy instead of left-heavy.
- Dividing by gaps = 0 on a single-word line — must be special-cased.
- Not treating the last line as left-justified.
- Producing a line that isn't exactly maxWidth characters.
Approach 2 of 2
Greedy Accumulator with Flush-on-Overflow (Alternative Organization)
1Hint 1Explore hintHide hint
Instead of a window pointer, accumulate words into a current-line list. Before adding a word, check whether it would overflow; if so, flush (format) the current line first.
2Hint 2Explore hintHide hint
The overflow test mirrors the fit test: current word-length sum + number of words so far + next word length > maxWidth means flush.
3Hint 3Explore hintHide hint
After the loop, flush the leftover words as the last line (left-justified). The flush routine handles single-word and full-line spacing.
A · Core idea
This is the same greedy algorithm organized as an accumulator rather than a window scan — useful to show you can structure the simulation either way and to make the 'flush a completed line' step explicit.
How accumulation works. We keep a list line of the words currently destined for the line and a running lineLen (sum of their lengths). For each incoming word, we first ask whether adding it would overflow: lineLen + len(line) + len(word) > maxWidth. Here len(line) is the number of words already accumulated, which equals the minimum number of single spaces needed once we add another word — exactly the same fit logic as the pointer version, just phrased as an overflow test. If it overflows, we flush: format the accumulated line (which is necessarily a full, non-last line) and reset. Then we add the current word to the now-empty line.
The flush routine. Flushing a full line distributes maxWidth − lineLen spaces over len(line) − 1 gaps, left-heavy, identical to phase 2 above. The one branch inside flush is the single-word line, which has no gaps and is therefore left-justified and right-padded.
Why the last line is handled outside the loop. During the loop we only ever flush completed (overflowing) lines, all of which are interior and fully justified. The final group of words never triggers an overflow flush, so after the loop we format it once as the last line: join with single spaces and pad right. Pulling the last line out of the loop is what cleanly separates 'fully justified interior lines' from 'left-justified last line' — a common source of confusion when people try to detect the last line inside the loop.
Trade-off versus the pointer version. The accumulator reads naturally as 'add words until one doesn't fit, then emit' and makes the last-line handling visually distinct. The pointer version avoids mutating a list and is slightly more compact. They are equivalent in behavior and complexity; pick whichever you can write bug-free under pressure. I'd present the pointer version first and offer this as 'here's the same thing structured around an explicit flush'.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
words = ["What","must","be","acknowledgment","shall","be"], maxWidth = 16add What,must,be
lineLen=4+4+2=10, 3 words; acknowledgment would need 10+3+14=27>16 → flush
flush [What,must,be]: spaces=16-10=6 over 2 gaps → 3,3 → "What must be"["What must be","acknowledgment ","shall be "]C · Code with teaching comments
Reference implementation previewpublic List<String> fullJustify(String[] words, int maxWidth) { List<String> result = new ArrayList<>(); List<String> line = new ArrayList<>(); int lineLen = 0; for (String word : words) {Explore the full codeHide the full code
D · Why it works and complexityO(total characters in output) timeO(maxWidth) spaceOpen the invariant and proofExplore the proofHide the proof
Framing the fit test as an overflow-then-flush makes the last-line rule fall out for free: only overflowing lines are flushed inside the loop (always fully justified), and the leftover group after the loop is the one and only left-justified last line.
ComplexityO(total characters in output) time, O(maxWidth) space — Same asymptotics as the pointer version: each word is added and emitted once, and each output character is written once → O(total output characters) time, O(maxWidth) per-line buffer space.
E · Edge cases and pitfalls7all words on one line (fit within maxWidth) — No overflow flush ever fires; the whole input becomes the last line → left-justified.Explore edge casesHide edge cases
Edge cases handled
all words on one line (fit within maxWidth)No overflow flush ever fires; the whole input becomes the last line → left-justified.single word equal to maxWidthNo spaces to pad; emitted as-is on its own line.words exactly filling lines with minimum spacesextra = 0 each flush → uniform single-or-equal spacing, padded to width.
Pitfalls
- Trying to detect the last line inside the loop — cleaner to flush only overflows and handle leftovers after.
- Forgetting to reset both line and lineLen after a flush.
- Single-word flush dividing by gaps = 0.
- Right-heavy extra-space distribution instead of left-heavy.
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewpublic List<String> fullJustify(String[] words, int maxWidth) { List<String> result = new ArrayList<>(); int i = 0, n = words.length; while (i < n) { int j = i, lineLen = 0;Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Right-heavy space distribution
The spec mandates leftmost gaps get the extra spaces. Putting the remainder on the right produces visibly wrong output (e.g. 1,2 instead of 2,1).
Explore the code comparisonHide the code comparison
Right-heavy space distribution
The spec mandates leftmost gaps get the extra spaces. Putting the remainder on the right produces visibly wrong output (e.g. 1,2 instead of 2,1).
Don't write this
each, extra = divmod(spaces, gaps)
for k in range(gaps):
add = each + (1 if k >= gaps - extra else 0) # right-heavy: wrong
...Write this instead
each, extra = divmod(spaces, gaps)
for k in range(gaps):
add = each + (1 if k < extra else 0) # left-heavy: correct
...2Single-word line divides by zero
A line with one word has gaps = numWords − 1 = 0. Computing spaces / gaps crashes; you must left-justify single-word lines instead.
Explore the code comparisonHide the code comparison
Single-word line divides by zero
A line with one word has gaps = numWords − 1 = 0. Computing spaces / gaps crashes; you must left-justify single-word lines instead.
Don't write this
int gaps = numWords - 1;
int each = spaces / gaps; // ArithmeticException when numWords == 1Write this instead
if (numWords == 1) {
sb.append(words[i]);
while (sb.length() < maxWidth) sb.append(' ');
} else {
int gaps = numWords - 1;
int each = spaces / gaps;
// ...
}3Last line fully justified instead of left-justified
Applying even distribution to the last line spreads big gaps through it; the spec requires single spaces and trailing padding.
Explore the code comparisonHide the code comparison
Last line fully justified instead of left-justified
Applying even distribution to the last line spreads big gaps through it; the spec requires single spaces and trailing padding.
Don't write this
# treating the final group like any other full line
line = distribute_evenly(words[i:j], maxWidth)Write this instead
if j == n: # last line
line = ' '.join(words[i:j])
line += ' ' * (maxWidth - len(line))Revise
Carry the pattern into the interview
Pattern to remember
Greedy line packing + even space distribution
Code pattern to memorize
fit test: lineLen + (#wordsSoFar) + len(word) <= maxWidth
full line: spaces=maxWidth-lineLen; gaps=words-1
each = spaces//gaps; extra = spaces%gaps
first `extra` gaps get (each+1), rest get each
last line OR single word: join with one space, left-justify, pad rightRules to remember
- 1Greedy fit test counts the minimum one space per gap: a word fits only if
lineLen + numWordsSoFar + len(word) ≤ maxWidth. - 2Extra spaces go to the LEFTMOST gaps. With 7 leftover spaces over 3 gaps you give 3,2,2 — the front gaps absorb the remainder via
divmod. - 3The last line is left-justified: single spaces between words, then pad the right to
maxWidth. - 4A line with a single word is also left-justified — there are no gaps to distribute into, so pad the right.
- 5Every output line is exactly `maxWidth` characters — pad with trailing spaces, never leave a line short.
Use this pattern when
- You must lay out tokens under fixed-width formatting rules (newspaper/console text wrapping)
- Greedy line-filling (first-fit) is acceptable rather than optimal line breaking
- There are distinct 'normal' vs 'edge' line rules (last line, single word)
- Exact, deterministic spacing matters and must be reconstructed character by character
Choose another pattern when
- You need MINIMUM total raggedness (Knuth–Plass optimal breaking) → DP, not greedy
- Proportional fonts / variable glyph widths → not a fixed-width character problem
- Word wrapping where words may be split with hyphens → different rules
- You only need the number of lines, not the formatted text → simpler counting
Interview takeaway
Text Justification is pure simulation: the hard part is not the algorithm but executing three spacing rules without off-by-one errors. Pack greedily, distribute leftover spaces left-heavy with `divmod`, and remember the two left-justified special cases (last line, single-word line).
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternGreedy line-packing simulation with even (left-heavy) space distribution. The challenge is exact formatting across three cases (full line, single-word line, last line), not algorithmic cleverness. For optimal minimum-raggedness line breaking, the generalization is the Knuth–Plass dynamic program.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Zigzag ConversionAnother layout-by-rules simulation: place characters positionally, then read them back.
- Rearrange Spaces Between WordsComing soonDistribute a fixed total of spaces evenly between words — the same divmod distribution idea, simplified.
- Sentence Screen FittingComing soonGreedy word packing into fixed-width rows, but counting fits instead of formatting them.