LeetCode Problem 68

Difficulty: 🔴 Hard
Topics: Array, String, Simulation

Solution

LeetCode 68 - Text Justification

Problem Understanding

This problem asks us to simulate how text is formatted in a text editor when using full justification. We are given an array of words and a target line width called maxWidth. The goal is to arrange these words into multiple lines such that every line contains exactly maxWidth characters.

The key challenge is not simply fitting words into lines, but distributing spaces correctly. Each line, except the last one, must be fully justified. Full justification means both the left and right boundaries of the line align perfectly. To achieve this, spaces between words must be distributed as evenly as possible.

The problem specifies a greedy packing strategy. This means that for each line, we should place as many words as possible before moving to the next line. Once a line is formed, we determine how many spaces remain and distribute them among the gaps between words.

There are three important formatting rules:

1. Every line must have exactly maxWidth characters.
2. For normal lines, spaces should be distributed as evenly as possible. If the spaces cannot be divided evenly, the leftmost gaps receive extra spaces.
3. The last line must always be left-justified, meaning words are separated by a single space and any remaining spaces are appended to the end.

The input consists of:

• words: an array of strings, where each string is a non-empty word.
• maxWidth: an integer specifying the exact width of every line.

The output is a list of strings where each string represents one justified line.

The constraints are relatively small:

• At most 300 words
• Maximum word length of 20
• Maximum width of 100

These constraints suggest that an O(n²) solution might still pass, but the problem strongly hints toward a greedy linear simulation approach. Since the number of words is small and each word can only be processed a limited number of times, an O(n) or O(n * maxWidth) solution is ideal.

Several edge cases make this problem tricky. A line may contain only one word, in which case it must be left-justified because there are no gaps to distribute spaces across. The final line always behaves differently and must never be fully justified. Another subtle case occurs when spaces do not divide evenly among gaps, requiring extra spaces to be placed toward the left side.

Approaches

Brute Force Approach

A brute force approach would attempt to generate all possible ways to partition words into lines and then evaluate which partition satisfies the justification rules.

For every possible grouping of words, we would calculate whether the line widths fit within maxWidth, distribute spaces, and check validity. Since each word can either stay on the current line or start a new one, the number of partitions grows exponentially.

This approach is correct because it explores every possible arrangement and eventually finds the valid formatting. However, it is extremely inefficient because the number of line combinations becomes enormous as the number of words increases.

Even with only a few hundred words, exponential exploration is completely impractical.

Optimal Greedy Simulation

The key insight is that the problem explicitly instructs us to pack words greedily. Since we are always required to place as many words as possible into the current line, there is no ambiguity in how words should be grouped.

This observation removes the need for backtracking or dynamic programming.

The process becomes:

1. Greedily collect words for one line.
2. Compute the total spaces needed.
3. Distribute spaces according to the rules.
4. Move to the next line.

For non-final lines with multiple words, we evenly divide spaces between gaps. If there are leftover spaces, they are assigned from left to right.

For lines containing only one word or for the last line, we simply left-justify.

Because every word is processed once, this leads to an efficient linear solution.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^n)	O(n)	Explores many possible partitions of words into lines
Optimal Greedy Simulation	O(n)	O(n)	Greedily forms each line and distributes spaces directly

Algorithm Walkthrough

Step 1: Iterate Through Words Greedily

Maintain an index i representing the start of the current line.

From this position, greedily include as many words as possible while ensuring the line length does not exceed maxWidth.

We track:

• Total length of words in the current line
• Number of words included

We stop when adding another word would exceed maxWidth.

This greedy step is correct because the problem explicitly requires us to pack as many words as possible.

Step 2: Determine Whether This Is a Special Case

After collecting the words for a line, check if:

• This is the last line, or
• The line contains only one word

These cases are treated differently because they must be left-justified.

Instead of evenly distributing spaces, we place exactly one space between words and pad the remaining spaces at the end.

Step 3: Compute Space Distribution for Regular Lines

If this is not the last line and contains multiple words, compute:

• totalSpaces = maxWidth - totalWordLength
• gaps = numberOfWords - 1

We divide spaces evenly:

• spacesPerGap = totalSpaces // gaps
• extraSpaces = totalSpaces % gaps

The remainder represents spaces that cannot be distributed evenly. According to the problem statement, extra spaces go to the leftmost gaps.

Step 4: Build the Line

Construct the line string.

For each word:

• Append the word.
• Add spaces after it.

If the current gap index is less than extraSpaces, add one extra space.

This guarantees that leftmost gaps receive the additional spaces first.

Step 5: Move to the Next Line

Append the constructed line to the result list.

Set i to the beginning of the next unprocessed word and repeat.

Why it Works

The correctness comes from two properties.

First, the greedy packing rule guarantees that every line contains the maximum possible number of words, which the problem explicitly requires.

Second, the spacing formula ensures the exact number of remaining spaces are distributed evenly. Integer division guarantees a base number of spaces per gap, while the remainder ensures extra spaces are assigned to the leftmost positions. Special handling for single-word lines and the last line matches the problem specification exactly.

Thus, every produced line satisfies the required formatting rules.

Python Solution

from typing import List

class Solution:
    def fullJustify(self, words: List[str], maxWidth: int) -> List[str]:
        result = []
        n = len(words)
        index = 0

        while index < n:
            line_start = index
            line_length = 0

            # Greedily fit as many words as possible
            while (
                index < n
                and line_length + len(words[index]) + (index - line_start)
                <= maxWidth
            ):
                line_length += len(words[index])
                index += 1

            line_words = words[line_start:index]
            word_count = len(line_words)

            # Last line or single word -> left justified
            if index == n or word_count == 1:
                line = " ".join(line_words)
                remaining_spaces = maxWidth - len(line)
                line += " " * remaining_spaces
                result.append(line)
                continue

            # Fully justify
            total_spaces = maxWidth - line_length
            gaps = word_count - 1

            spaces_per_gap = total_spaces // gaps
            extra_spaces = total_spaces % gaps

            line = []

            for i in range(gaps):
                line.append(line_words[i])

                spaces = spaces_per_gap
                if i < extra_spaces:
                    spaces += 1

                line.append(" " * spaces)

            line.append(line_words[-1])

            result.append("".join(line))

        return result

The implementation closely follows the algorithm.

We begin by iterating through the words using an index pointer. For each line, we greedily determine how many words can fit. The expression:

line_length + len(words[index]) + (index - line_start)

calculates whether the next word fits. Here:

• line_length stores total character count of words
• len(words[index]) is the candidate word length
• (index - line_start) accounts for minimum required spaces between words

After determining line boundaries, we check whether the line is special.

If it is the last line or contains only one word, we left-justify using " ".join() and pad spaces to the right.

Otherwise, we compute how spaces should be distributed. Integer division determines the base number of spaces, while modulus determines leftover spaces for leftmost gaps.

Finally, we build the line efficiently using a list of strings and "".join() to avoid repeated string concatenation overhead.

Go Solution

func fullJustify(words []string, maxWidth int) []string {
	var result []string
	n := len(words)
	index := 0

	for index < n {
		lineStart := index
		lineLength := 0

		// Greedily fit words
		for index < n &&
			lineLength+len(words[index])+(index-lineStart) <= maxWidth {
			lineLength += len(words[index])
			index++
		}

		lineWords := words[lineStart:index]
		wordCount := len(lineWords)

		// Last line or single word
		if index == n || wordCount == 1 {
			line := ""

			for i, word := range lineWords {
				if i > 0 {
					line += " "
				}
				line += word
			}

			for len(line) < maxWidth {
				line += " "
			}

			result = append(result, line)
			continue
		}

		// Fully justify
		totalSpaces := maxWidth - lineLength
		gaps := wordCount - 1

		spacesPerGap := totalSpaces / gaps
		extraSpaces := totalSpaces % gaps

		line := ""

		for i := 0; i < gaps; i++ {
			line += lineWords[i]

			spaces := spacesPerGap
			if i < extraSpaces {
				spaces++
			}

			for j := 0; j < spaces; j++ {
				line += " "
			}
		}

		line += lineWords[wordCount-1]
		result = append(result, line)
	}

	return result
}

The Go implementation follows the same logic as the Python solution but adapts to Go's string handling.

Unlike Python, Go does not provide a built-in equivalent of " ".join() for slices in this exact formatting scenario, so we manually build strings.

Slices are used naturally for lineWords, and integer division behaves exactly as required for evenly distributing spaces.

There is no integer overflow concern because the maximum width is only 100.

Worked Examples

Example 1

Input

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

First Line Construction

Step	Words	Character Count
Add "This"	["This"]	4
Add "is"	["This", "is"]	6
Add "an"	["This", "is", "an"]	8
Cannot add "example"	stop	exceeds width

Current words:

["This", "is", "an"]

Word length:

4 + 2 + 2 = 8

Spaces needed:

16 - 8 = 8

Gaps:

2

Distribution:

8 // 2 = 4 spaces per gap
0 extra spaces

Result:

"This    is    an"

Second Line Construction

Words:

["example", "of", "text"]

Word length:

7 + 2 + 4 = 13

Spaces needed:

3

Gaps:

2

Distribution:

1 space each + 1 extra left space

Result:

"example  of text"

Final Line

Words:

["justification."]

Left justified:

"justification.  "

Example 2

Input

words = ["What","must","be","acknowledgment","shall","be"]
maxWidth = 16

First Line

Words:

["What", "must", "be"]

Word length:

10

Spaces:

6

Gaps:

2

Each gap gets:

3 spaces

Result:

"What   must   be"

Second Line

Single word:

["acknowledgment"]

Must be left justified:

"acknowledgment  "

Third Line

Last line:

["shall", "be"]

Left justified:

"shall be       "

Example 3

Line	Words	Result
1	["Science","is","what","we"]	"Science is what we"
2	["understand","well"]	"understand well"
3	["enough","to","explain","to"]	"enough to explain to"
4	["a","computer.","Art","is"]	"a computer. Art is"
5	["everything","else","we"]	"everything else we"
6	["do"]	"do "

The same greedy process repeats for every line. Words are packed maximally, spacing is computed, and the final line is left justified.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each word is processed once while constructing lines
Space	O(n)	Output storage plus temporary line construction

The time complexity is linear because every word enters and leaves processing exactly once. Although strings are built for each line, the total amount of text produced is proportional to the input size and output width.

The space complexity is O(n) due to the result list containing justified lines. Aside from output storage, only a few temporary variables are used.

Test Cases

solution = Solution()

# Example 1
assert solution.fullJustify(
    ["This", "is", "an", "example", "of", "text", "justification."],
    16
) == [
    "This    is    an",
    "example  of text",
    "justification.  "
]  # standard example

# Example 2
assert solution.fullJustify(
    ["What","must","be","acknowledgment","shall","be"],
    16
) == [
    "What   must   be",
    "acknowledgment  ",
    "shall be       "
]  # single-word middle line

# Example 3
assert solution.fullJustify(
    ["Science","is","what","we","understand","well",
     "enough","to","explain","to","a","computer.",
     "Art","is","everything","else","we","do"],
    20
) == [
    "Science  is  what we",
    "understand      well",
    "enough to explain to",
    "a  computer.  Art is",
    "everything  else  we",
    "do                  "
]  # large multi-line case

# Single word
assert solution.fullJustify(
    ["hello"],
    10
) == [
    "hello     "
]  # smallest valid input

# Exact fit
assert solution.fullJustify(
    ["abc", "def"],
    7
) == [
    "abc def"
]  # no extra padding needed

# Uneven spacing
assert solution.fullJustify(
    ["a", "b", "c"],
    6
) == [
    "a  b c"
]  # extra space goes left

# Multiple single-word lines
assert solution.fullJustify(
    ["longword", "anotherlongword"],
    15
) == [
    "longword       ",
    "anotherlongword"
]  # each line contains one word

# Last line left justification
assert solution.fullJustify(
    ["a", "b", "c", "d"],
    3
) == [
    "a b",
    "c d"
]  # final line remains left-justified

Test	Why
Example 1	Validates standard justification behavior
Example 2	Verifies single-word non-final line
Example 3	Tests complex multi-line formatting
Single word	Smallest valid input
Exact fit	Ensures no unnecessary padding
Uneven spacing	Confirms extra spaces go left
Multiple single-word lines	Tests repeated left justification
Last line left justification	Verifies special final-line rule

Edge Cases

Single Word in a Line

A line containing only one word can be a source of bugs because there are no gaps between words for space distribution. A naive implementation might divide by zero while computing spaces per gap.

The implementation explicitly checks:

word_count == 1

In this case, the word is left-justified and padded with trailing spaces.

Last Line Formatting

The final line behaves differently from all previous lines. Instead of evenly distributing spaces, words must be separated by exactly one space.

A common mistake is accidentally applying full justification to the final line, producing incorrect spacing.

The implementation detects:

index == n

and switches to left justification.

Uneven Space Distribution

When spaces do not divide evenly among gaps, the extra spaces must go to the leftmost gaps.

For example:

["a", "b", "c"], width = 6

requires:

"a  b c"

instead of:

"a b  c"

The implementation handles this correctly using:

if i < extra_spaces:
    spaces += 1

which guarantees left-biased distribution.

Words That Exactly Fill the Width

Sometimes a set of words plus minimum required spaces perfectly fills maxWidth.

For example:

["abc", "def"], width = 7

The implementation correctly recognizes that no extra spaces are needed and produces:

"abc def"

without unnecessary trailing padding.