How do you solve Text Justification on LeetCode?

Text Justification (LeetCode #68) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(n) space complexity. Key insight: Distributing spaces evenly is crucial for proper justification.

What is the brute force solution for Text Justification?

The brute force approach for Text Justification is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach involves iterating through the words and adding them to a line until adding another word would exceed the maxWidth. Once a line is filled, we format it by adding spaces between the words. This method is straightforward but inefficient. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Text Justification?

Text Justification uses the following concepts: Array, String, Simulation. The recommended patterns to study are: Greedy, Simulation.

What are the interview tips for Text Justification?

Clarify the requirements before coding. Think about edge cases, like a single word or multiple words fitting exactly. Discuss your thought process while coding.

What are common mistakes when solving Text Justification?

Forgetting to handle the last line differently. Not distributing spaces correctly when the number of gaps is zero.

#68

Text Justification

Hard

ArrayStringSimulationGreedySimulation

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(n)

💡

Intuition

Time O(n)Space O(n)

The optimal approach uses a single pass to build lines and justify them efficiently. By keeping track of the current line's words and their lengths, we can calculate the necessary spaces in a more structured way, leading to better performance.

⚙️

Algorithm

4 steps

1Step 1: Initialize an empty list for the result and a temporary list for the current line.
2Step 2: Iterate through the words, adding them to the current line until adding another word would exceed maxWidth.
3Step 3: When a line is full, calculate the total spaces needed and distribute them evenly between the words.
4Step 4: For the last line, simply left-justify it and add it to the result.

solution.py17 lines

1def fullJustify(words, maxWidth):
2    result = []
3    current_line = []
4    current_length = 0
5
6    for word in words:
7        if current_length + len(word) + len(current_line) > maxWidth:
8            for i in range(maxWidth - current_length):
9                current_line[i % (len(current_line) - 1 or 1)] += ' '
10            result.append(''.join(current_line))
11            current_line = []
12            current_length = 0
13        current_line.append(word)
14        current_length += len(word)
15
16    result.append(' '.join(current_line).ljust(maxWidth))
17    return result

ℹ

Complexity note: The time complexity is O(n) because we iterate through the list of words once. The space complexity is O(n) as we store the result and the current line of words.

1Distributing spaces evenly is crucial for proper justification.
2The last line should always be left-justified.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.