Text Justification

Difficulty: Hard
Topics: Array, String, Simulation
Link: https://leetcode.com/problems/text-justification/

Problem Description

Given an array of strings words and a width maxWidth, format the text such that each line has exactly maxWidth characters and is fully (left and right) justified.

You should pack your words in a greedy approach; that is, pack as many words as you can in each line. Pad extra spaces ' ' when necessary so that each line has exactly maxWidth characters.

Extra spaces between words should be distributed as evenly as possible. If the number of spaces on a line does not divide evenly between words, the empty slots on the left will be assigned more spaces than the slots on the right.

For the last line of text, it should be left-justified, and no extra space is inserted between words.

Note:

A word is defined as a character sequence consisting of non-space characters only.
Each word’s length is guaranteed to be greater than 0 and not exceed maxWidth.
The input array words contains at least one word.

Example 1:


Input: words = ["This", "is", "an", "example", "of", "text", "justification."], maxWidth = 16
Output:
[
   "This    is    an",
   "example  of text",
   "justification.  "
]

Example 2:


Input: words = ["What","must","be","acknowledgment","shall","be"], maxWidth = 16
Output:
[
  "What   must   be",
  "acknowledgment  ",
  "shall be        "
]
Explanation: Note that the last line is "shall be    " instead of "shall     be", because the last line must be left-justified instead of fully-justified.
Note that the second line is also left-justified because it contains only one word.

Example 3:


Input: words = ["Science","is","what","we","understand","well","enough","to","explain","to","a","computer.","Art","is","everything","else","we","do"], maxWidth = 20
Output:
[
  "Science  is  what we",
  "understand      well",
  "enough to explain to",
  "a  computer.  Art is",
  "everything  else  we",
  "do                  "
]

Constraints:

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

Solution

1. Problem Deconstruction (500+ words)

Technical Restatement: Given a sequence of lexical tokens (words) and a target line width, implement a formatting algorithm that:

Applies greedy line breaking to maximize word density per line
Enforces exact width compliance through strategic whitespace insertion
Distributes inter-word spacing using left-biased remainder allocation
Handles terminal lines with special left-justification rules
Maintains word sequence integrity and avoids hyphenation

The core challenge involves calculating optimal space distributions between words while respecting both typographical conventions and computational constraints.

Beginner-Friendly Version: Imagine you’re typing text in a word processor with strict line length limits. You need to:

Fit as many words as possible on each line
Evenly stretch the spaces between words to make lines exactly the required length
When spaces don’t divide evenly, put extra spaces closer to the beginning
Make the last line look normal (left-aligned with regular single spaces)

Mathematical Formulation: Let $W = [w_1, w_2, ..., w_n]$ be the word sequence Let $L(w_i)$ be the length of word $w_i$ Let $M$ be the maximum line width

For each line containing words $w_a$ to $w_b$ :

Total characters occupied by words: $C = \sum_{i=a}^{b} L(w_i)$
Available spaces: $S = M - C$
Number of gaps between words: $G = (b - a)$

If $G > 0$ (multiple words):

Base spaces per gap: $B = \lfloor S / G \rfloor$
Leftover spaces: $R = S \mod G$
Space distribution: $[B+R, B, B, ..., B]$ for $R$ left gaps, then $B$ for remaining

If $G = 0$ (single word): Pad with $S$ spaces on right If last line: Distribute 1 space between words, pad with remaining $S - (b-a)$ spaces on right

Constraint Analysis:

1 <= words.length <= 300: Allows O(n³) solutions but suggests O(n²) is optimal
1 <= words[i].length <= 20: Individual word handling is trivial, focus on spacing logic
words[i] consists of only English letters and symbols: No special Unicode handling required
1 <= maxWidth <= 100: Output lines are manageable for string operations
words[i].length <= maxWidth: Guarantees single words always fit on a line

Hidden Edge Cases:

Single word lines requiring right-padding
Lines where spaces distribute with remainder 1 (minimal left bias)
Last line with exactly one word vs multiple words
Input with words that exactly fill maxWidth (no extra spaces needed)
Very short maxWidth forcing one word per line

2. Intuition Scaffolding

Real-World Metaphor: Imagine organizing books on a shelf where:

Books = words, shelf width = maxWidth
You want to fit as many books as possible on each shelf
Use bookends (spaces) to fill remaining space
Distribute fancy bookends unevenly (more decorative ones on left)
The last shelf uses simple, evenly spaced bookends

Gaming Analogy: Like inventory management in RPGs:

Items (words) have different sizes
Inventory slots (lines) have fixed capacity
Arrange items to fill slots optimally
Use filler items (spaces) to exactly fill slots
Special rules for the last inventory page

Math Analogy: Think of it as a constrained optimization problem:

Objective: Maximize words per line (greedy packing)
Constraint: Exact width compliance
Distribution: Optimal remainder allocation in modular arithmetic
Boundary: Special terminal condition handling

Common Pitfalls:

Global optimization trap: Trying to optimize line breaks globally rather than greedily
Space calculation errors: Forgetting that n words have (n-1) gaps
Remainder distribution: Applying remainder to right instead of left
Last line handling: Applying full justification to the final line
Single word lines: Not right-padding single words appropriately
Exact fit oversight: Not handling lines where words exactly fill width
Index boundary errors: Incorrectly handling word sequence slicing

3. Approach Encyclopedia

Brute Force Approach:

def fullJustify(words, maxWidth):
    result = []
    i = 0
    
    while i < len(words):
        # Start new line with current word
        line_words = [words[i]]
        line_length = len(words[i])
        i += 1
        
        # Greedily add words until overflow
        while i < len(words) and line_length + 1 + len(words[i]) <= maxWidth:
            line_words.append(words[i])
            line_length += 1 + len(words[i])  # +1 for space
            i += 1
        
        # Handle last line or single word line
        if i == len(words) or len(line_words) == 1:
            # Left justify
            line = ' '.join(line_words)
            line += ' ' * (maxWidth - len(line))
            result.append(line)
        else:
            # Full justify
            total_spaces = maxWidth - sum(len(word) for word in line_words)
            gaps = len(line_words) - 1
            
            # Distribute spaces
            base_spaces = total_spaces // gaps
            extra_spaces = total_spaces % gaps
            
            line = line_words[0]
            for j in range(1, len(line_words)):
                # Add base spaces + 1 extra for first 'extra_spaces' gaps
                spaces_to_add = base_spaces + (1 if j <= extra_spaces else 0)
                line += ' ' * spaces_to_add + line_words[j]
            
            result.append(line)
    
    return result

Complexity Analysis:

Time: O(n × maxWidth) - Each word processed once, string operations scale with line width
Space: O(n × maxWidth) - Output storage dominates, proportional to total characters

Visualization:

Words: ["This", "is", "an", "example"]
maxWidth: 16

Line 1: "This is an" 
Words length: 3 + 2 + 2 = 7
Spaces needed: 16 - 7 = 9
Gaps: 2
Base: 9 // 2 = 4
Extra: 9 % 2 = 1

Distribution: [4+1, 4] = [5, 4]
Result: "This_____is____an"  (_ = space)

4. Code Deep Dive

Optimized Implementation:

class Solution:
    def fullJustify(self, words: List[str], maxWidth: int) -> List[str]:
        result = []  # Stores final justified lines
        current_line = []  # Words in current line
        current_length = 0  # Current line character count (without spaces)
        
        for word in words:
            # Calculate if adding this word would exceed maxWidth
            # current_length (words) + len(word) + spaces between words
            if current_line:
                # If line has words, we need at least one space before new word
                potential_length = current_length + len(word) + 1
            else:
                # First word in line, no space needed
                potential_length = current_length + len(word)
            
            if potential_length <= maxWidth:
                # Word fits in current line
                current_line.append(word)
                current_length += len(word) if not current_line else len(word) + 1
            else:
                # Word doesn't fit, justify current line
                result.append(self.justify_line(current_line, maxWidth, False))
                
                # Start new line with current word
                current_line = [word]
                current_length = len(word)
        
        # Handle last line (left-justified)
        result.append(self.justify_line(current_line, maxWidth, True))
        return result
    
    def justify_line(self, words: List[str], maxWidth: int, is_last_line: bool) -> str:
        if is_last_line or len(words) == 1:
            # Left justification for last line or single word
            line = ' '.join(words)
            return line + ' ' * (maxWidth - len(line))
        
        # Full justification for multiple words
        total_chars = sum(len(word) for word in words)
        total_spaces = maxWidth - total_chars
        gaps = len(words) - 1
        
        base_spaces = total_spaces // gaps
        extra_spaces = total_spaces % gaps
        
        line = words[0]
        for i in range(1, len(words)):
            # Distribute extra spaces to left gaps
            spaces_to_add = base_spaces + (1 if i <= extra_spaces else 0)
            line += ' ' * spaces_to_add + words[i]
        
        return line

Edge Case Handling:

Example 1, Line 2: ["example", "of", "text"] → 7+2+4=13 chars, 3 spaces needed, 2 gaps → [2,1] distribution
Example 2, Line 2: Single word "acknowledgment" → right-padded with 2 spaces
Example 3, Line 2: ["understand", "well"] → 10+4=14 chars, 6 spaces, 1 gap → all 6 spaces go to single gap

5. Complexity War Room

Hardware-Aware Analysis:

At maximum input (300 words × 20 chars = 6000 chars raw), output stores ~300 × 100 = 30KB
Fits comfortably in L1/L2 cache for modern processors
String operations are O(maxWidth) = O(100) per line, very efficient
Memory access patterns are sequential with good locality

Industry Comparison Table:

Approach	Time Complexity	Space Complexity	Readability	Interview Viability
Dynamic Line Breaking	O(n³)	O(n²)	6/10	❌ Overkill
Greedy + Space Distribution	O(n × maxWidth)	O(n × maxWidth)	8/10	✅ Optimal
Pre-calculated Line Breaks	O(n²)	O(n)	7/10	⚠️ More Complex

Algorithm Selection Rationale: The greedy approach achieves optimal O(n) time for typical cases while being intuitive to implement. The space distribution logic, while detailed, follows straightforward arithmetic rules that can be clearly explained during interviews.

6. Pro Mode Extras

Advanced Variants:

Hyphenation Support: Break long words with hyphenation dictionaries
Dynamic Programming Line Breaking: Minimize “badness” (cubed leftover spaces)
Multi-column Layout: Distribute text across multiple columns
Ragged-right Justification: Traditional publishing style with flexible right margin
Kerning-aware Justification: Adjust inter-character spacing in addition to word spacing

Interview Cheat Sheet:

First Mention: Always state time/space complexity upfront
Key Insight: Greedy word packing + left-biased space distribution
Critical Cases: Single-word lines, last line, exact-width lines
Testing Strategy:
- Single word input
- Words that exactly fill lines
- Maximum constraint boundaries
- Mixed short/long word sequences
Common Follow-ups:
- “How would you handle hyphenation?”
- “What if we wanted to minimize total number of lines?”
- “How would this work with proportional fonts?”

#68 - Text Justification