LeetCode Solutions Blog

Text Justification

Number: 68

Difficulty: Hard

Paid? No

Problem Description

Given an array of strings (words) and a maximum width (maxWidth), format the text such that each line has exactly maxWidth characters and is fully (left and right) justified. Words must be packed using a greedy approach, and extra spaces should be distributed as evenly as possible, with any remainder spaces placed on the left slots. The last line should be left-justified and not fully-justified.

Key Insights

Use a greedy approach to fill each line with as many words as possible without exceeding maxWidth.
Calculate total space to distribute by subtracting the combined words length from maxWidth.
If the line has more than one word, distribute extra spaces evenly; if not, pad the line with spaces at the end.
Handle the last line separately by left-justifying the text (i.e., adding a single space between words and padding the end).

Space and Time Complexity

Time Complexity: O(n) where n is the number of words, since each word is processed once.
Space Complexity: O(n) for storing the result and temporary buffers.

Solution

The solution iterates over the list of words and groups them into lines such that the combined length of the words and minimum required spaces does not exceed maxWidth. For each completed group (line):

If it’s not the last line, calculate extra spaces required.
If the line has multiple words, distribute the spaces evenly, adding any extra spaces from left to right.
If the line contains a single word, append spaces to the right.
For the last line, join words with a single space and pad the remaining width with spaces.

Data structures used include lists (or arrays) for current words accumulation and the final result. The logic is implemented using a simulation approach to mimic text formatting.

Code Solutions

def fullJustify(words, maxWidth):
    result = []         # Final list of justified text lines.
    current_words = []  # Current line's words.
    current_len = 0     # Total length of current line's words (excluding spaces).

    # Process all words.
    for word in words:
        # Check if adding the next word would exceed the maxWidth when including minimum one space between words.
        if current_words and (current_len + len(word) + len(current_words)) > maxWidth:
            total_spaces = maxWidth - current_len           # Total spaces to distribute.
            gaps = len(current_words) - 1                     # Number of gaps between words.
            
            # If there is only one word, left justify.
            if gaps == 0:                                   
                line = current_words[0] + ' ' * total_spaces
            else:
                # Calculate even spaces and extras to add from the left.
                space_per_gap, extra = divmod(total_spaces, gaps)
                line = ''
                for i in range(gaps):
                    # Distribute an extra space to the leftmost gaps.
                    spaces = space_per_gap + (1 if i < extra else 0)
                    line += current_words[i] + ' ' * spaces
                line += current_words[-1]                     # Append the last word.
            result.append(line)
            # Reset the current line to start with the current word.
            current_words = []
            current_len = 0
        
        # Add the word to the current line.
        current_words.append(word)
        current_len += len(word)
    
    # Process the last line, which is left-justified.
    line = ' '.join(current_words)
    line += ' ' * (maxWidth - len(line))
    result.append(line)
    return result

# Example usage:
words = ["This", "is", "an", "example", "of", "text", "justification."]
maxWidth = 16
print(fullJustify(words, maxWidth))