68. Text Justification

HardRandomization, Math and Miscellaneous (FAANG add-on)Greedy grouping plus arithmetic space allocationGreedy line packing with space distribution

Text Justification

Given an array of words and a width maxWidth, format the text so each line has exactly maxWidth characters and is fully justified. Pack as many words per line as fit, distribute extra spaces as evenly as possible with larger gaps assigned to the left, and left-justify the final line and any line with a single word.

Open official problem prompt ↗

In plain English

Lay out a stream of words into fixed-width, fully justified lines matching a newspaper column, with the last line left-aligned.

Picture it like this

A typesetter fills each column line with words, then stretches the gaps between them like an accordion so both margins line up flush.

Example

Input: words = ["This","is","an","example","of","text","justification."], maxWidth = 16
Output: ["This is an","example of text","justification. "]
Why: Lines 1-2 spread spaces evenly (left gaps get the extra), and the last line is left-justified then padded to width 16.

Constraints

1 <= words.length <= 3001 <= words[i].length <= 20words[i] consists of only English letters and symbols1 <= maxWidth <= 100words[i].length <= maxWidth

Pattern lesson

See the pattern, then code

Greedy line packing with space distribution

↗

Randomization, Math and Miscellaneous (FAANG add-on)

Uniform random selection, sampling streams, number theory, or precision-heavy parsing.. Greedily fit the maximum words per line; once a line's words are chosen, the leftover spaces are fixed, so distribute them by integer division with the remainder going to the leftmost gaps.

New words, made simpleKnow these before the algorithm

Gap: A space region between two adjacent words on a line; a line with count words has count-1 gaps.
Full justification: Padding a line so text touches both the left and right margins exactly.
Base and extra spaces: Even share per gap (base) and the leftover remainder distributed to the leftmost gaps (extra).

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Fit line then re-flow

Redundant re-measuring; unnecessary given greedy packing works in one pass.

Try counts and re-measure repeatedly.

Time O(n^2)Space O(1)

Best choiceGreedy pack + arithmetic spacing

Single pass, exact width control, handles all rules cleanly.

Take max words that fit, compute space distribution with divmod, special-case last line.

Time O(total characters)Space O(maxWidth)

The rule we keep true

Invariant

When a line is closed, the words chosen are the maximum prefix that fits with at least one space between neighbors, so leftover space is minimized and fully determined.

Why this is correct

Reasoning

Greedy maximal packing is optimal for this layout because fewer words on a line can never reduce line count, and once words are fixed the width constraint forces the exact space count, which divmod distributes deterministically left-to-right.

The algorithm in three movesSay these aloud before coding

1Greedily collect words while current length + word + minimum single spaces fits maxWidth

line 1 words: This,is,an -> len 8, spaces 8 over 2 gaps -> 4 and 4

2If it is the last line or only one word, left-justify and pad the right with spaces

line 2 words: example,of,text -> spaces 3 over 2 gaps -> 2 and 1

3Otherwise split leftover spaces across gaps: base = spaces // gaps, extra = spaces % gaps

line 3 last: justification. + 2 pad

4Give the first 'extra' gaps one additional space and build the line

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

This0

is1

an2

example3

of4

text5

justification.6

1 · ReadThis,is,an

2 · AskDo 3 words fit?

3 · Update stateline_len=8, adding 'example' needs 8+7+3=18>16

4 · ResultClose line; spaces=8, gaps=2, base=4 extra=0 -> "This is an".

Key takeaway

First greedy line groups This/is/an, sharing 8 spaces evenly across two gaps.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 7-11Greedy fit
Add words while length plus (j-i) minimum separating spaces stays within maxWidth.
2
Lines 13-15Left-justify branch
Last line or single word: single spaces then right-pad to width.
3
Lines 16-25Full-justify branch
divmod splits leftover spaces; the first 'extra' gaps receive one bonus space each.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

A single word longer relationship where only one word fits a line (left-justify with right padding)
The last line always left-justified even if multiple words
A line whose spaces divide evenly (extra = 0)
Every word length <= maxWidth guaranteed so no word overflows

Common beginner mistakes

Fully justifying the last line instead of left-justifying it
Adding the extra space to the right gaps rather than the left
Forgetting the (j - i) minimum-spaces term in the fit test
Not right-padding single-word lines to reach maxWidth

Check your understanding

Why do the leftmost gaps receive the extra spaces?

PyPython 3 · solution.py

Optimal

1class Solution:2    def fullJustify(self, words: list[str], maxWidth: int) -> list[str]:3        res = []4        i, n = 0, len(words)5        while i < n:6            j = i7            line_len = 08            while j < n and line_len + len(words[j]) + (j - i) <= maxWidth:9                line_len += len(words[j])10                j += 111            count = j - i12            if j == n or count == 1:13                line = ' '.join(words[i:j])14                line += ' ' * (maxWidth - len(line))15            else:16                spaces = maxWidth - line_len17                gaps = count - 118                base, extra = divmod(spaces, gaps)19                parts = []20                for k in range(i, j - 1):21                    parts.append(words[k])22                    parts.append(' ' * (base + (1 if (k - i) < extra else 0)))23                parts.append(words[j - 1])24                line = ''.join(parts)25            res.append(line)26            i = j27        return res

Time complexityO(total characters)Optimized

Space complexityO(maxWidth) per line excluding outputExplained

Interview rehearsal

Explain before you code

25:00

Restate constraints and edge cases
Explain brute force and its bottleneck
State the invariant and complexity

Seen at

GoogleAirbnbLinkedInAmazon

Text Justification

Text Justification

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Randomization, Math and Miscellaneous (FAANG add-on)