Text Justification
Asked at Atlassian, Databricks
Problem
Given an array of words and a maximum width, format the text such that each line has exactly maxWidth characters. Justify text by inserting spaces between words and distributing extra spaces as evenly as possible. The last line is left-justified. This is a greedy simulation problem.
Asked At
| Company | Difficulty | |
|---|---|---|
| Atlassian | Hard | View all Atlassian questions → |
| Databricks | Hard | View all Databricks questions → |
How to Think About It
The core logic: greedily pack as many words as possible into each line. Count total characters (including single spaces between words). If adding the next word would exceed maxWidth, finalize the current line.
For each line, calculate: total word characters, number of gaps (words - 1), extra spaces to distribute. Extra = maxWidth - total_chars. Each gap gets extra // gaps spaces. The first extra % gaps gaps get one extra space.
Visual walkthrough for words=["This","is","an","example","of","text","justification."], maxWidth=16:
Line 1: "This" (4) + "is" (2) + "an" (2) = 8 chars. Gaps=2. Remaining: 16-8=8. Each gap gets 8/2=4 spaces. Result: "This is an"
Line 2: "example" (7) + "of" (2) + "text" (4) = 13 chars. Gaps=2. Extra=3. First gap gets 2, second gets 1. Result: "example of text"
Line 3: "justification." (14). Last line: left-justify. "justification. "
Special case: last line is always left-justified. Words separated by single space, remaining spaces padded at the end.
Edge case: line with exactly one word is left-justified (same as last line logic for non-last lines too). All spaces go at the end.
Optimal Approach
Step 1: Greedily pack words into lines. For each line:
- Count words that fit (total_chars + spaces <= maxWidth)
- Calculate extra spaces = maxWidth - total_chars_in_line
- If one word or last line: left-justify (single spaces, pad right)
- Otherwise: distribute extra spaces evenly across gaps
- First extra % gaps gaps get one extra space
Step 2: Build each line string by joining words with the calculated spacing.
Key insight: the greedy packing ensures each line is as full as possible. The even distribution of spaces is the standard justified text algorithm.
Time: O(n * maxWidth) where n = number of words. Space: O(maxWidth) per line.
What Trips People Up in Real Interviews
Miscounting spaces. The total line length must be exactly maxWidth. Count word lengths AND the single spaces between words first, then distribute the remaining spaces.
Forgetting that the last line is left-justified. The last line uses single spaces and pads the right end. Don't apply the same distribution logic.
Not handling single-word lines. A line with one word is left-justified (like the last line). All extra spaces go at the end, not between non-existent gaps.
Off-by-one in space distribution. The first extra % gaps gaps get one more space than the rest. If extra=5 and gaps=3, spaces are [2,2,1] or [2,1,2] depending on implementation.
Adding trailing spaces at the end of non-last lines. Justified text in standard practice does NOT have trailing spaces. The total line length should equal maxWidth without trailing spaces.
Solution Code
def fullJustify(words, maxWidth):
lines = []
line = []
line_len = 0
for word in words:
if line_len + len(line) + len(word) > maxWidth:
gaps = len(line) - 1
if gaps == 0:
lines.append(line[0] + ' ' * (maxWidth - len(line[0])))
else:
total_spaces = maxWidth - line_len
base = total_spaces // gaps
extra = total_spaces % gaps
justified = ''
for i, w in enumerate(line):
justified += w
if i < gaps:
spaces = base + (1 if i < extra else 0)
justified += ' ' * spaces
lines.append(justified)
line = []
line_len = 0
line.append(word)
line_len += len(word)
last_line = ' '.join(line)
last_line += ' ' * (maxWidth - len(last_line))
lines.append(last_line)
return linesFrequently Asked Questions
What is the Text Justification problem?
Given an array of words and a maximum width, format the text such that each line has exactly maxWidth characters. Justify text by inserting spaces between words and distributing extra spaces as evenly as possible. The last line is left-justified. This is a greedy simulation problem.
How do you solve Text Justification?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Text Justification?
Text Justification is asked at Atlassian, Databricks. It is a hard difficulty problem.
What are common mistakes on Text Justification?
- Miscounting spaces. The total line length must be exactly maxWidth. Count word lengths AND the single spaces between words first, then distribute the remaining spaces.
- Forgetting that the last line is left-justified. The last line uses single spaces and pads the right end. Don't apply the same distribution logic.
- Not handling single-word lines. A line with one word is left-justified (like the last line). All extra spaces go at the end, not between non-existent gaps.
- Off-by-one in space distribution. The first `extra % gaps` gaps get one more space than the rest. If extra=5 and gaps=3, spaces are [2,2,1] or [2,1,2] depending on implementation.
- Adding trailing spaces at the end of non-last lines. Justified text in standard practice does NOT have trailing spaces. The total line length should equal maxWidth without trailing spaces.