68. Text Justification

Format words into lines of exactly maxWidth characters. Greedily pack as many words as fit per line, then spread the leftover spaces as evenly as possible — extra spaces favoring the leftmost gaps. The last line (and any single-word line) is left-justified and padded on the right. The algorithm is easy; the tricky part is the careful spacing simulation.

● HardGreedySimulationTypeScript

PROBLEM What we're solving

Given a list of words and a width, return each line padded to exactly maxWidth characters. Take words = ["This","is","an","example","of","text","justification."] with maxWidth = 16. The greedy packing gives lines This is an, example of text, and justification.. After spacing:

"This    is    an"
"example  of text"
"justification.  "

Line 1 has 3 words: 10 letters, 6 spaces over 2 gaps → 3 + 3. Line 2 has 3 words: 12 letters, 4 spaces over 2 gaps → 2 + 1 (the extra goes to the leftgap). Line 3 is the last line, so it's left-justified and padded on the right.

KEY IDEA Pack greedily, then spread

Two independent steps per line → first, greedily grab as many words as fit assuming a single space between them; then forget the words and just distribute the leftover spaces across the gaps, left to right.

The leftover space count is maxWidth − (sum of word lengths). Split it over gaps = numWords − 1: every gap gets ⌊total / gaps⌋, and the first total mod gaps gaps get one extra. That single floor/remainder pair is the whole trick.

RECIPE One line at a time

1 · Greedy fill. Starting at word i, keep adding the next word while lineLen + 1 + nextWord.length ≤ maxWidth (the +1 is the mandatory single space).
2 · Count the gaps. numWords words make numWords − 1 gaps and maxWidth − totalLetters spaces to place.
3 · Spread evenly. Each gap gets base = ⌊spaces / gaps⌋; the leftmost spaces mod gaps gaps get +1.
4 · Pad & advance. Push the line, set i to the next word, repeat until words run out.

Classic confusion → the last line and any single-word line are left-justified, not fully justified: one space between words, then pad the right with spaces. And for full lines, extra spaces go to the LEFT gaps, not the right — k ≤ extra, not k > gaps − extra.

COST Complexity & alternatives

Naive: even split only

wrong

Giving every gap ⌊s / g⌋ and dropping the remainder leaves lines too short; ignoring the last-line rule mis-pads the tail.

Greedy pack + even spread

O(n)

One pass over the words; total work is proportional to the total characters written.

This is mostly careful simulation, not a clever data structure. The greedy choice (pack as many words as fit) is provably optimal for this fixed format; the only real bugs are off-by-one space counting and forgetting the special-cased lines.

Pattern transfer →the "greedily fill a fixed-width line, then format" move recurs in word-wrap engines, terminal pagers, and CSV/column layout. The remainder-distribution trick (base + (k ≤ extra)) also shows up in round-robin scheduling, fair-share allocation, and dealing cards evenly.

RUN IT Pack greedily, then spread the spaces

words =maxWidth =

step 0 / 17

STARTStart. We'll greedily pack words into lines of exactly 16 chars. Padding spaces are shown as · so you can count them.

1function fullJustify(words: string[], maxWidth: number): string[] {
2▶  const lines: string[] = [];
3▶  let i = 0;
4 
5  while (i < words.length) {
6    // 1 ── Greedily pack words into the current line.
7    // lineLen tracks chars assuming exactly ONE space between words.
8    let j = i;
9    let lineLen = words[i].length;
10    while (j + 1 < words.length &&
11           lineLen + 1 + words[j + 1].length <= maxWidth) {
12      lineLen += 1 + words[j + 1].length;
13      j++;
14    }
15 
16    const numWords = j - i + 1;
17    const lastWord = j === words.length - 1;
18 
19    // 2 ── Build the line.
20    if (numWords === 1 || lastWord) {
21      // Left-justify: single space between words, pad the right.
22      let line = words.slice(i, j + 1).join(' ');
23      line += ' '.repeat(maxWidth - line.length);
24      lines.push(line);
25    } else {
26      // Full-justify: spread spaces across (numWords - 1) gaps.
27      const gaps = numWords - 1;
28      const totalSpaces = maxWidth - (lineLen - gaps); // chars w/o any spaces
29      const base = Math.floor(totalSpaces / gaps);     // each gap gets this
30      const extra = totalSpaces % gaps;                // leftmost gaps get +1
31      let line = words[i];
32      for (let k = 1; k < numWords; k++) {
33        const spaces = base + (k <= extra ? 1 : 0);
34        line += ' '.repeat(spaces) + words[i + k];
35      }
36      lines.push(line);
37    }
38 
39    i = j + 1; // advance to the next line's first word
40  }
41 
42  return lines;
43}

words ="This"0"is"1"an"2"example"3"of"4"text"5"justification."6

State

maxWidth

[]

lines

words on the current lineword / gap being processedextra (leftmost) space / paddingline emitted / done

slowfast

TYPESCRIPT The solution, annotated

fullJustify.ts
function fullJustify(words: string[], maxWidth: number): string[] {
  const lines: string[] = [];
  let i = 0;

  while (i < words.length) {
    // 1 ── Greedily pack words into the current line.
    // lineLen tracks chars assuming exactly ONE space between words.
    let j = i;
    let lineLen = words[i].length;
    while (j + 1 < words.length &&
           lineLen + 1 + words[j + 1].length <= maxWidth) {
      lineLen += 1 + words[j + 1].length;
      j++;
    }

    const numWords = j - i + 1;
    const lastWord = j === words.length - 1;

    // 2 ── Build the line.
    if (numWords === 1 || lastWord) {
      // Left-justify: single space between words, pad the right.
      let line = words.slice(i, j + 1).join(' ');
      line += ' '.repeat(maxWidth - line.length);
      lines.push(line);
    } else {
      // Full-justify: spread spaces across (numWords - 1) gaps.
      const gaps = numWords - 1;
      const totalSpaces = maxWidth - (lineLen - gaps); // chars w/o any spaces
      const base = Math.floor(totalSpaces / gaps);     // each gap gets this
      const extra = totalSpaces % gaps;                // leftmost gaps get +1
      let line = words[i];
      for (let k = 1; k < numWords; k++) {
        const spaces = base + (k <= extra ? 1 : 0);
        line += ' '.repeat(spaces) + words[i + k];
      }
      lines.push(line);
    }

    i = j + 1; // advance to the next line's first word
  }

  return lines;
}

Reading it block by block

Lines 8–14 — greedy pack. Start a line at word i. Keep absorbing the next word as long as it fits with exactly one separating space (+1). The running lineLen assumes single spaces, which is exactly enough to test the fit.

Lines 16–17 — classify the line. numWords is how many we grabbed; lastWord is true when we consumed the final word. These two flags decide left-justify vs full-justify.

Lines 20–26 — left-justified case. A single-word line or the last line gets one space between words, then the right is padded so the total length hits maxWidth.

Lines 27–38 — full-justified case. Compute total spaces to place, divide by the number of gaps for base, and the remainder extra tells how many of the leftmost gaps get one bonus space (k <= extra).

Line 41 — advance. Set i = j + 1 so the next iteration starts at the first word of the next line. Loop until every word is placed.

Complexity → every word is examined a constant number of times and every output character is written once, so the work is O(total characters) — linear. Output uses O(total characters) space; aside from the result, only a handful of integer counters.

INTERVIEWFollow-ups they'll ask

"Why do extra spaces go to the LEFT gaps?"It's the problem's defined convention so output is deterministic; any consistent rule produces valid justification, but LeetCode checks for left-biased extras.
"What if a single word is longer than maxWidth?"The constraints guarantee every word fits; otherwise you'd need word-breaking / hyphenation, a different problem.
"How is the last line different?"It's left-justified: single spaces between words, all padding pushed to the right edge.
"Could you minimize raggedness instead?"That's the Knuth–Plass / DP word-wrap problem — it picks line breaks to minimize total squared slack, an O(n²) DP, not this greedy fixed-width version.

OPTIMAL Greedy

fullJustify.ts
function fullJustify(words: string[], maxWidth: number): string[] {
  const lines: string[] = [];
  let i = 0;

  while (i < words.length) {
    // 1 ── Greedily pack words into the current line.
    // lineLen tracks chars assuming exactly ONE space between words.
    let j = i;
    let lineLen = words[i].length;
    while (j + 1 < words.length &&
           lineLen + 1 + words[j + 1].length <= maxWidth) {
      lineLen += 1 + words[j + 1].length;
      j++;
    }

    const numWords = j - i + 1;
    const lastWord = j === words.length - 1;

    // 2 ── Build the line.
    if (numWords === 1 || lastWord) {
      // Left-justify: single space between words, pad the right.
      let line = words.slice(i, j + 1).join(' ');
      line += ' '.repeat(maxWidth - line.length);
      lines.push(line);
    } else {
      // Full-justify: spread spaces across (numWords - 1) gaps.
      const gaps = numWords - 1;
      const totalSpaces = maxWidth - (lineLen - gaps); // chars w/o any spaces
      const base = Math.floor(totalSpaces / gaps);     // each gap gets this
      const extra = totalSpaces % gaps;                // leftmost gaps get +1
      let line = words[i];
      for (let k = 1; k < numWords; k++) {
        const spaces = base + (k <= extra ? 1 : 0);
        line += ' '.repeat(spaces) + words[i + k];
      }
      lines.push(line);
    }

    i = j + 1; // advance to the next line's first word
  }

  return lines;
}

ALT 1 Round-robin space distribution

O(total characters) time · O(width) per line

Same greedy packing, but instead of a divmodformula it lays down a base space in every gap, then walks the gaps left-to-right handing out one leftover space at a time — making "extras go to the left gaps" literally visible in the loop.

approach-2.ts
function fullJustify(words: string[], maxWidth: number): string[] {
  const lines: string[] = [];
  let i = 0;

  while (i < words.length) {
    // 1 ── Greedily pack words into the current line (single-space fit test).
    let j = i;
    let lineLen = words[i].length;
    while (j + 1 < words.length &&
           lineLen + 1 + words[j + 1].length <= maxWidth) {
      lineLen += 1 + words[j + 1].length;
      j++;
    }

    const lineWords = words.slice(i, j + 1);
    const numWords = lineWords.length;
    const gaps = numWords - 1;
    const lastLine = j === words.length - 1;

    if (gaps === 0 || lastLine) {
      // 2a ── Left-justify: one space between words, pad the right.
      let line = lineWords.join(' ');
      line += ' '.repeat(maxWidth - line.length);
      lines.push(line);
    } else {
      // 2b ── Full-justify via round robin.
      // Total spaces to place across the gaps.
      const letters = lineLen - gaps;            // chars w/o any spaces
      const totalSpaces = maxWidth - letters;
      const base = Math.floor(totalSpaces / gaps);

      // Give every gap the base count, then hand out the leftovers
      // one at a time, left to right, until none remain.
      const gapSizes: number[] = new Array(gaps).fill(base);
      let leftover = totalSpaces - base * gaps;
      let g = 0;
      while (leftover > 0) {
        gapSizes[g]++;
        g++;
        leftover--;
      }

      // 3 ── Stitch words and gaps together.
      let line = lineWords[0];
      for (let k = 0; k < gaps; k++) {
        line += ' '.repeat(gapSizes[k]) + lineWords[k + 1];
      }
      lines.push(line);
    }

    i = j + 1; // advance to the next line's first word
  }

  return lines;
}

Note → Because leftover < gaps always, the round-robin pass touches each leftmost gap exactly once — identical output to the base + (k ≤ extra) formula, just spelled out as an explicit loop. The only extra cost is an O(gaps) array per line, bounded by maxWidth, so the asymptotics are unchanged.

MNEMONIC The one-liner

"Pack till it spills, split the leftovers left — but the tail leans left and pads right."

TRIGGERS When you see _ → reach for _

"lines of exactly maxWidth chars"	greedy fixed-width packing
"distribute spaces evenly"	floor + remainder (base + extra)
"extra spaces to the left"	k <= extra gets +1
"last line / single word"	left-justify + right pad

SKELETON The reusable shape

skeleton.ts
let i = 0;
while (i < words.length) {
  let j = i, lineLen = words[i].length;
  while (j + 1 < n && lineLen + 1 + words[j+1].length <= maxWidth)
    lineLen += 1 + words[++j].length;
  const last = j === n - 1, gaps = j - i;
  if (gaps === 0 || last) {
    let line = words.slice(i, j+1).join(' ');
    lines.push(line + ' '.repeat(maxWidth - line.length));
  } else {
    const slots = maxWidth - (lineLen - gaps);
    const base = Math.floor(slots / gaps), extra = slots % gaps;
    let line = words[i];
    for (let k = 1; k <= gaps; k++)
      line += ' '.repeat(base + (k <= extra ? 1 : 0)) + words[i+k];
    lines.push(line);
  }
  i = j + 1;
}

FLASHCARDS Tap to flip

How do you decide which words go on a line?

Greedily add words while lineLen + 1 + next.length <= maxWidth (the +1is one separating space). Stop at the first word that doesn't fit.

tap to flip

1 / 7

Answer to reveal explanations. No penalty for retries.Score: 0 / 9

QUESTION 01

For a fully-justified line, the number of spaces to distribute is:

QUESTION 02

When spaces = 5 must be spread over gaps = 2, the gaps get:

QUESTION 03

How is the LAST line formatted?

QUESTION 04

A line holds a single word. How is it justified?

QUESTION 05

In the greedy fit test, why the “+1” in lineLen + 1 + next.length?

QUESTION 06

What is the overall time complexity?

QUESTION 07

When extra spaces don't divide evenly, which gaps receive the bonus space?

QUESTION 08

#68 · Text JustificationFormat words into lines of exactly maxWidth characters: greedily pack words per line, distribute leftover spaces as evenly as possible with extras going to the leftmost gaps, and left-justify the last line.Which algorithmic approach does this primarily use?

QUESTION 09

PROBLEM What we're solving

KEY IDEA Pack greedily, then spread

RECIPE One line at a time

COST Complexity & alternatives

RUN IT Pack greedily, then spread the spaces

TYPESCRIPT The solution, annotated

Reading it block by block

INTERVIEWFollow-ups they'll ask

OPTIMAL Greedy

ALT 1 Round-robin space distribution

MNEMONIC The one-liner

TRIGGERS When you see ___ → reach for ___

SKELETON The reusable shape

FLASHCARDS Tap to flip

TRIGGERS When you see _ → reach for _