Given an array of strings words and a width maxWidth, format the text such that each line has exactly maxWidth characters and is fully (left and right) justified.
You should pack your words in a greedy approach; that is, pack as many words as you can in each line. Pad extra spaces ' ' when necessary so that each line has exactly maxWidth characters.
Extra spaces between words should be distributed as evenly as possible. If the number of spaces on a line does not divide evenly between words, the empty slots on the left will be assigned more spaces than the slots on the right.
For the last line of text, it should be left-justified, and no extra space is inserted between words.
Note:
0 and not exceed maxWidth.words contains at least one word.Example 1:
Input: words = ["This", "is", "an", "example", "of", "text", "justification."], maxWidth = 16 Output: [ "This is an", "example of text", "justification. " ]
Example 2:
Input: words = ["What","must","be","acknowledgment","shall","be"], maxWidth = 16 Output: [ "What must be", "acknowledgment ", "shall be " ] Explanation: 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 " ]
Constraints:
1 <= words.length <= 3001 <= words[i].length <= 20words[i] consists of only English letters and symbols.1 <= maxWidth <= 100words[i].length <= maxWidthThe Text Justification problem is typically solved using a greedy simulation approach. The idea is to process the list of words and build lines one by one while ensuring each line does not exceed the given maximum width. For each line, keep adding words until adding another word would exceed maxWidth.
Once the words for a line are selected, distribute the required spaces between them so the total length becomes exactly maxWidth. Spaces should be distributed as evenly as possible from left to right. If the spaces cannot be divided evenly, the left gaps receive extra spaces. The final line is treated differently—it is left-justified, meaning words are separated by a single space and the remaining spaces are added at the end.
This approach processes each word once and simulates spacing distribution efficiently, resulting in a linear pass over the input.
Time Complexity: O(n) where n is the total number of words (or characters processed). Space Complexity: O(1) auxiliary space excluding the output.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Greedy Line Building with Space Distribution | O(n) | O(1) auxiliary (excluding output) |
Tushar Roy - Coding Made Simple
This approach involves iterating through the given words and greedily forming a line by adding as many words as possible without exceeding the maxWidth. When a line is completed, the algorithm distributes spaces evenly between words. If the number of spaces doesn’t divide evenly, more spaces are added to the left slots. The last line is treated differently by left-justifying the text.
Time Complexity: O(n), where n is the total number of characters in all words.
Space Complexity: O(n), where n is the number of lines formed times maxWidth for the justified text.
1def fullJustify(words, maxWidth):
2 def justify_line(line, width, maxWidth):
3 if len(line) == 1:
4 return line[0] + ' ' * (maxWidth - width)
5 total_spaces = maxWidth - width + len(line) - 1
6 space, extra = divmod(total_spaces, len(line) - 1)
7 for i in range(extra):
8 line[i] += ' '
9 return (' ' * space).join(line)
10
11 res, line, width = [], [], 0
12 for word in words:
13 if width + len(word) + len(line) > maxWidth:
14 res.append(justify_line(line, width, maxWidth))
15 line, width = [], 0
16 line.append(word)
17 width += len(word)
18
19 last_line = ' '.join(line)
20 res.append(last_line + ' ' * (maxWidth - len(last_line)))
21 return resThe code defines a helper function, justify_line, to construct each justified line. While adding words to the current line, if adding another word exceeds maxWidth, the line is justified and appended to the result. The last line is treated separately for left-justification.
This method leverages dynamic programming to minimize a hypothetical cost function that combines badness or uneven space distribution along with total number of lines used, aiming to determine the optimal setup of words per line.
Time Complexity: O(n^2), due to potential double iterations required for exploring word positions.
Space Complexity: O(n), since it uses extra space for storing dp and path arrays.
1#include <iostream>
2#include <vector>
3#include <string>
4#include <climits>
5using namespace std;
vector<string> fullJustify(vector<string>& words, int maxWidth) {
int n = words.size();
vector<int> dp(n + 1, INT_MAX);
vector<int> path(n);
dp[n] = 0;
for (int i = n - 1; i >= 0; --i) {
int len = -1;
for (int j = i; j < n; ++j) {
len += words[j].length() + 1;
if (len > maxWidth) break;
int last_cost = j == n - 1 ? 0 : maxWidth - len;
if (dp[i] > last_cost + dp[j + 1]) {
dp[i] = last_cost + dp[j + 1];
path[i] = j + 1;
}
}
}
vector<string> res;
for (int i = 0; i < n; i = path[i]) {
int j = path[i];
string line = words[i];
for (int k = i + 1; k < j; ++k) {
line += " " + words[k];
}
line += string(maxWidth - line.length(), ' ');
res.push_back(line);
}
return res;
}Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, Text Justification is a common interview-style problem that tests string manipulation, greedy thinking, and attention to detail. Variants of this problem have appeared in coding interviews at large tech companies.
Arrays or lists are typically used to store the words for the current line. String builders or similar structures help efficiently construct the final justified line with properly distributed spaces.
The optimal approach uses a greedy strategy. You group as many words as possible into each line without exceeding the maximum width, then distribute spaces evenly between words. Special handling is applied to the last line, which is left-justified.
The challenge lies in correctly distributing spaces between words and handling edge cases such as single-word lines and the final left-justified line. Careful simulation and string manipulation are required to meet all formatting constraints.
This C++ implementation uses a dynamic programming table, dp, to compute the minimum penalty of breaking words into lines. path is used to store optimal partitioning. The final step reconstructs justified text using information stored in path.