The Text Justification problem involves formatting an array of words into lines that match a given width. The challenge is to distribute spaces evenly between words, prioritizing left alignment for the last line. This requires a greedy approach to pack words into lines, while ensuring no line exceeds the maximum width.
Problem Statement
Given an array of words and a maximum width (maxWidth), the task is to justify the text. Each line must contain as many words as possible, and the total length of the words plus spaces must exactly match the given maxWidth. If extra spaces are needed, distribute them as evenly as possible between words. If the spaces cannot be evenly distributed, the leftmost spaces should be placed first.
The last line should be left-justified, meaning it is filled with words but without extra space between them. If the line contains only one word, it should be left-justified with any remaining space filled at the end of the line. Handle the edge cases where lines may have one or no words.
Examples
Example 1
Input: words = ["This", "is", "an", "example", "of", "text", "justification."], maxWidth = 16
Output: [ "This is an", "example of text", "justification. " ]
Example details omitted.
Example 2
Input: words = ["What","must","be","acknowledgment","shall","be"], maxWidth = 16
Output: [ "What must be", "acknowledgment ", "shall be " ]
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 " ]
Example details omitted.
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 Approach
Greedy Approach
The problem follows a greedy approach where you try to fit as many words as possible in each line. The greedy method ensures that each line gets as many words as it can without exceeding maxWidth.
Space Distribution
After packing the words, spaces must be distributed evenly between the words. If the remaining spaces are not divisible by the number of spaces between words, place the extra spaces from left to right.
Left Justification for the Last Line
The last line of text should always be left-justified. No extra spaces between words, and any remaining space should be added at the end.
Complexity Analysis
| Metric | Value |
|---|---|
| Time | Depends on the final approach |
| Space | Depends on the final approach |
The time complexity depends on the final approach. Typically, it involves iterating over the words and distributing spaces, leading to an O(n) time complexity where n is the number of words. The space complexity depends on the storage of the formatted output, which is O(n) as well.
What Interviewers Usually Probe
- Able to explain space distribution in detail.
- Can implement a greedy approach effectively.
- Demonstrates understanding of left justification and its edge cases.
Common Pitfalls or Variants
Common pitfalls
- Incorrectly distributing spaces when the number of spaces doesn't divide evenly.
- Forgetting that the last line should be left-justified.
- Overcomplicating the space distribution by adding extra checks.
Follow-up variants
- Handling very large maxWidth values.
- Handling words with different lengths efficiently.
- Implementing an alternative approach that minimizes space usage while keeping time complexity optimal.
How GhostInterview Helps
- GhostInterview can guide you through the greedy approach and ensure space distribution is handled correctly.
- It helps you stay focused on the edge cases like the last line being left-justified.
- GhostInterview provides hints on optimizing both time and space complexity for large inputs.
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
FAQ
How do I approach the Text Justification problem?
Start by packing words into lines using a greedy approach, ensuring the total line width does not exceed maxWidth. Then, distribute spaces evenly between the words, with extra spaces placed on the left. Finally, make sure the last line is left-justified.
What happens if the spaces can't be evenly distributed?
If the spaces cannot be evenly distributed, the extra spaces are added from left to right, meaning the leftmost spaces will get more space than the rightmost.
Why is the last line always left-justified?
The last line is left-justified to ensure that no extra space is added between words, and the remaining space is filled at the end of the line.
How do I handle edge cases like a single word on a line?
If there's only one word on the line, the line will be left-justified, and the remaining spaces will be added at the end of the line.
What is the time complexity of solving Text Justification?
The time complexity is typically O(n), where n is the number of words. This involves iterating over the words and distributing spaces in each line.
Need direct help with Text Justification instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Text Justification from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
Add Binary involves summing two binary strings and returning the result as a binary string using math and string manipulation.
Open problem page#59 Spiral Matrix IIGenerate a spiral matrix of size n x n, filled with elements from 1 to n² in spiral order, for interview-focused solving.
Open problem page#79 Word SearchSolve Word Search with backtracking by exploring adjacent cells to match a target word in a grid.
Open problem page