Text Justification
Text Justification is a hard arrays & hashing problem solved with the simulation pattern.
The best approach, optimal (greedy packing + arithmetic spacing), runs in O(n · maxWidth) time and O(maxWidth) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (hand out spaces one at a time) up.
Problem
You are given an array of words words and a line width maxWidth. Lay the words out as text where every line is exactly maxWidth characters long and the text is fully justified.
Fill lines greedily: put as many words on a line as fit, with at least one space between neighbouring words. Then pad each line with extra spaces between the words so that it reaches maxWidth. The spaces should be spread as evenly as possible; when they cannot be split evenly, the gaps on the left get more spaces than the gaps on the right.
The last line is left-justified instead: its words are separated by single spaces and the rest of the line is filled with spaces at the end. A line that holds only one word is also left-justified. Return the lines as a list of strings.
Examples
Example 1
- Input
words = ["plan", "the", "trip", "to", "the", "hills", "early"], maxWidth = 14- Output
["plan the trip", "to the hills", "early "]- Why
- "plan the trip" needs 13 characters, so the 1 extra space goes to the leftmost gap; the last line is left-aligned and padded.
Example 2
- Input
words = ["go", "fetch", "a", "stick", "now"], maxWidth = 9- Output
["go fetch", "a stick", "now "]- Why
- Each full line spreads its spare spaces across its single gap; "now" alone on the last line is padded on the right.
Example 3
- Input
words = ["extraordinary", "is", "ok"], maxWidth = 13- Output
["extraordinary", "is ok "]- Why
- The first word fills a whole line by itself; the final line keeps single spaces between words.
Constraints
1 <= words.length <= 3001 <= words[i].length <= 20words[i]contains only English letters, digits and punctuation, never spaces.words[i].length <= maxWidth <= 100
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 13 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (hand out spaces one at a time) | O(n · maxWidth) | O(maxWidth) |
| Optimal (greedy packing + arithmetic spacing) | O(n · maxWidth) | O(maxWidth) |
1Brute force (hand out spaces one at a time)
O(n · maxWidth)Each line hands out at most maxWidth spaces one by one, and there are at most n lines.O(maxWidth)The gap sizes and the line being built, apart from the output.Pack words greedily into a line. Then hand out the spare spaces one by one, going round the gaps from left to right, which naturally gives the left gaps more when the count does not divide evenly. The last line and single-word lines just get single spaces and right padding.
- Starting at word i, keep taking words while the letters so far plus one space per gap still fit in maxWidth; the line ends before word j.
- If j is the end of the input or the line has one word, join with single spaces and pad the right with spaces.
- Otherwise give every gap 0 spaces, then hand out maxWidth - letters spaces one at a time, cycling over the gaps from the left.
- Build the line from the words and gap sizes, add it to the answer, and continue from j.
class Solution {
public List<String> fullJustify(String[] words, int maxWidth) {
List<String> res = new ArrayList<>();
int n = words.length, i = 0;
while (i < n) {
int j = i, letters = 0;
while (j < n && letters + words[j].length() + (j - i) <= maxWidth) {
letters += words[j].length();
j++;
}
int gaps = j - i - 1;
int[] spaces = new int[Math.max(gaps, 0)];
if (j == n || gaps == 0) {
Arrays.fill(spaces, 1);
} else {
int left = maxWidth - letters, g = 0;
while (left > 0) {
spaces[g]++;
left--;
g = (g + 1) % gaps;
}
}
StringBuilder sb = new StringBuilder();
for (int k = i; k < j; k++) {
sb.append(words[k]);
if (k < j - 1) {
for (int s = 0; s < spaces[k - i]; s++) sb.append(' ');
}
}
while (sb.length() < maxWidth) sb.append(' ');
res.add(sb.toString());
i = j;
}
return res;
}
}class Solution:
def fullJustify(self, words: List[str], maxWidth: int) -> List[str]:
res = []
n, i = len(words), 0
while i < n:
j, letters = i, 0
while j < n and letters + len(words[j]) + (j - i) <= maxWidth:
letters += len(words[j])
j += 1
gaps = j - i - 1
spaces = [0] * max(gaps, 0)
if j == n or gaps == 0:
spaces = [1] * max(gaps, 0)
else:
left, g = maxWidth - letters, 0
while left > 0:
spaces[g] += 1
left -= 1
g = (g + 1) % gaps
parts = []
for k in range(i, j):
parts.append(words[k])
if k < j - 1:
parts.append(" " * spaces[k - i])
line = "".join(parts)
res.append(line + " " * (maxWidth - len(line)))
i = j
return resclass Solution {
public:
vector<string> fullJustify(vector<string>& words, int maxWidth) {
vector<string> res;
int n = words.size(), i = 0;
while (i < n) {
int j = i, letters = 0;
while (j < n && letters + (int)words[j].size() + (j - i) <= maxWidth) {
letters += words[j].size();
j++;
}
int gaps = j - i - 1;
vector<int> spaces(max(gaps, 0), 0);
if (j == n || gaps == 0) {
fill(spaces.begin(), spaces.end(), 1);
} else {
int left = maxWidth - letters, g = 0;
while (left > 0) {
spaces[g]++;
left--;
g = (g + 1) % gaps;
}
}
string line;
for (int k = i; k < j; k++) {
line += words[k];
if (k < j - 1) line += string(spaces[k - i], ' ');
}
line += string(maxWidth - line.size(), ' ');
res.push_back(line);
i = j;
}
return res;
}
};function fullJustify(words, maxWidth) {
const res = [];
const n = words.length;
let i = 0;
while (i < n) {
let j = i, letters = 0;
while (j < n && letters + words[j].length + (j - i) <= maxWidth) {
letters += words[j].length;
j++;
}
const gaps = j - i - 1;
const spaces = new Array(Math.max(gaps, 0)).fill(0);
if (j === n || gaps === 0) {
spaces.fill(1);
} else {
let left = maxWidth - letters, g = 0;
while (left > 0) {
spaces[g]++;
left--;
g = (g + 1) % gaps;
}
}
let line = "";
for (let k = i; k < j; k++) {
line += words[k];
if (k < j - 1) line += " ".repeat(spaces[k - i]);
}
line += " ".repeat(maxWidth - line.length);
res.push(line);
i = j;
}
return res;
}2Optimal (greedy packing + arithmetic spacing)
O(n · maxWidth)Every output character is appended once, and the output has at most n lines of maxWidth characters; this is the size of the answer itself.O(maxWidth)Only the line being built, apart from the output.Pack each line greedily as before, but compute the gap sizes directly instead of handing out spaces one at a time. With extra = maxWidth - letters spaces and gaps gaps, every gap gets extra / gaps spaces and the first extra % gaps gaps get one more. Each character of the output is written exactly once.
- Take words i..j-1 while letters + (number of words - 1) <= maxWidth.
- If this is the last line or it has one word: join with single spaces, then pad the right up to maxWidth.
- Otherwise: base = extra / gaps, more = extra % gaps; after word number g (0-based, g < gaps) write base spaces, plus one if g < more.
- Add the line to the answer and continue from j.
class Solution {
public List<String> fullJustify(String[] words, int maxWidth) {
List<String> res = new ArrayList<>();
int n = words.length, i = 0;
while (i < n) {
int j = i, letters = 0;
while (j < n && letters + words[j].length() + (j - i) <= maxWidth) {
letters += words[j].length();
j++;
}
StringBuilder sb = new StringBuilder();
int gaps = j - i - 1;
if (j == n || gaps == 0) {
for (int k = i; k < j; k++) {
if (k > i) sb.append(' ');
sb.append(words[k]);
}
while (sb.length() < maxWidth) sb.append(' ');
} else {
int extra = maxWidth - letters;
int base = extra / gaps, more = extra % gaps;
for (int k = i; k < j; k++) {
sb.append(words[k]);
if (k < j - 1) {
int s = base + (k - i < more ? 1 : 0);
for (int t = 0; t < s; t++) sb.append(' ');
}
}
}
res.add(sb.toString());
i = j;
}
return res;
}
}class Solution:
def fullJustify(self, words: List[str], maxWidth: int) -> List[str]:
res = []
n, i = len(words), 0
while i < n:
j, letters = i, 0
while j < n and letters + len(words[j]) + (j - i) <= maxWidth:
letters += len(words[j])
j += 1
gaps = j - i - 1
if j == n or gaps == 0:
line = " ".join(words[i:j])
line += " " * (maxWidth - len(line))
else:
base, more = divmod(maxWidth - letters, gaps)
parts = []
for k in range(i, j):
parts.append(words[k])
if k < j - 1:
parts.append(" " * (base + (1 if k - i < more else 0)))
line = "".join(parts)
res.append(line)
i = j
return resclass Solution {
public:
vector<string> fullJustify(vector<string>& words, int maxWidth) {
vector<string> res;
int n = words.size(), i = 0;
while (i < n) {
int j = i, letters = 0;
while (j < n && letters + (int)words[j].size() + (j - i) <= maxWidth) {
letters += words[j].size();
j++;
}
string line;
int gaps = j - i - 1;
if (j == n || gaps == 0) {
for (int k = i; k < j; k++) {
if (k > i) line += ' ';
line += words[k];
}
line += string(maxWidth - line.size(), ' ');
} else {
int extra = maxWidth - letters;
int base = extra / gaps, more = extra % gaps;
for (int k = i; k < j; k++) {
line += words[k];
if (k < j - 1) line += string(base + (k - i < more ? 1 : 0), ' ');
}
}
res.push_back(line);
i = j;
}
return res;
}
};function fullJustify(words, maxWidth) {
const res = [];
const n = words.length;
let i = 0;
while (i < n) {
let j = i, letters = 0;
while (j < n && letters + words[j].length + (j - i) <= maxWidth) {
letters += words[j].length;
j++;
}
let line = "";
const gaps = j - i - 1;
if (j === n || gaps === 0) {
line = words.slice(i, j).join(" ");
line += " ".repeat(maxWidth - line.length);
} else {
const extra = maxWidth - letters;
const base = Math.floor(extra / gaps), more = extra % gaps;
for (let k = i; k < j; k++) {
line += words[k];
if (k < j - 1) line += " ".repeat(base + (k - i < more ? 1 : 0));
}
}
res.push(line);
i = j;
}
return res;
}Edge cases to test
- A line with a single word (not the last line): the word is left-aligned and padded with spaces on the right
- Spare spaces that do not divide evenly: the leftmost gaps get one extra space each
- The last line is never stretched: single spaces between words, padding at the end
- A word whose length equals
maxWidthtakes a whole line - Only one word in total
Hints
Hint 1
First decide which words go on each line: keep adding words while their lengths plus one space between each still fit in maxWidth.
Hint 2
For a full line with k words and total letter count L, there are k - 1 gaps that must share maxWidth - L spaces.
Hint 3
Each gap gets (maxWidth - L) / (k - 1) spaces, and the first (maxWidth - L) % (k - 1) gaps get one more. The last line and single-word lines are special: join with single spaces and pad the right.
FAQ
What is the best time complexity for Text Justification?
Optimal (greedy packing + arithmetic spacing) runs in O(n · maxWidth) time and O(maxWidth) extra space. Every output character is appended once, and the output has at most n lines of maxWidth characters; this is the size of the answer itself.
Which pattern does Text Justification use?
It is a arrays & hashing problem that uses the simulation pattern. Other problems with the same pattern: Integer to English Words, String to Integer (atoi), Remove Comments.
Is there a brute force solution for Text Justification?
Yes. Brute force (hand out spaces one at a time) takes O(n · maxWidth) time and O(maxWidth) space. Pack words greedily into a line.
Which edge cases should I test for Text Justification?
A line with a single word (not the last line): the word is left-aligned and padded with spaces on the right; Spare spaces that do not divide evenly: the leftmost gaps get one extra space each; The last line is never stretched: single spaces between words, padding at the end; A word whose length equals maxWidth takes a whole line; Only one word in total.