Back to solutions

Text Justification

HardArrays

Format words into fully-justified lines of a fixed width.

Open problem
Constraints
  • 1 <= m <= 300
  • 1 <= word length <= maxWidth <= 100

Greedy line packing then spacing

Time O(total characters)Space O(total characters)

Greedily fit as many words on a line as possible (each gap needs at least one space). For a full line, distribute the leftover spaces across the gaps as evenly as possible, giving the leftmost gaps one extra each. The final line (or any single-word line) is left-justified and padded on the right.

Key terms
full justification:
Padding a line with spaces so both left and right edges align to the width.
gap:
The space between two adjacent words where padding is inserted.
// pack words while lineLen + words[j].size() + (j - i) <= maxWidth;
// last line or single word -> left justify + right pad;
// else base = spaces/gaps, extra = spaces%gaps, first 'extra' gaps get one more.
Step by step
  1. Pack words greedily: add words while their lengths plus minimal gaps fit in maxWidth.
  2. If it is the last line or has a single word, left-justify and pad the right.
  3. Otherwise compute leftover spaces = maxWidth - sum of word lengths; distribute base = spaces/gaps to each gap and one extra to the first (spaces%gaps) gaps.
  4. Assemble each line to exactly maxWidth and continue with the next batch of words.