Text Justification
Hard
1 view
Topics:
ArraysStrings
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:
- A word is defined as a character sequence consisting of non-space characters only.
- Each word's length is guaranteed to be greater than
0and not exceedmaxWidth. - The input array
wordscontains 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 <= maxWidth
Solution
Clarifying Questions
When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:
- What is the range for `maxWidth` and the length of each string in `words`? Is it possible for a single word to be longer than `maxWidth`?
- Should I handle edge cases like an empty `words` array, or a `maxWidth` of 0?
- If a line can only fit one word, how should it be justified (left, right, or center)?
- For lines that are not the last line, and the spaces don't distribute evenly, which side (left or right) should receive the extra spaces?
- What should the output be if the input `words` is null or contains null strings?
Brute Force Solution
Approach
The brute force approach to text justification means we explore every possible way to break the given words into lines. We test each arrangement to see if it fits the length constraint. Then, from all valid arrangements, we pick the best one.
Here's how the algorithm would work step-by-step:
- Consider putting the first word alone on the first line.
- Then, consider putting the first and second words on the first line, then the first, second, and third words, and so on. Each time, check if the combined length of the words and the spaces between them exceeds the maximum line length.
- If the line length is exceeded, discard that arrangement and try the next.
- If a combination of words fits on the first line, repeat this process for the remaining words on the second line.
- Continue this process, trying every possible combination of words for each line until all words are placed.
- Store each valid arrangement of words into lines that doesn't exceed the length constraint.
- Finally, compare all the valid arrangements and choose the one that distributes spaces evenly across the lines, following the specific justification rules for the last line and other lines.
Code Implementation
def full_justify_brute_force(words, max_width):
all_arrangements = []
def explore_arrangements(current_arrangement, remaining_words):
if not remaining_words:
all_arrangements.append(current_arrangement)
return
for i in range(1, len(remaining_words) + 1):
first_line_words = remaining_words[:i]
line_length = sum(len(word) for word in first_line_words) + (len(first_line_words) - 1)
if line_length <= max_width:
# Found a valid line, so explore further
explore_arrangements(current_arrangement + [first_line_words], remaining_words[i:])
explore_arrangements([], words)
def justify_line(words_on_line, line_width, is_last_line):
number_of_words = len(words_on_line)
total_characters = sum(len(word) for word in words_on_line)
number_of_gaps = number_of_words - 1
if number_of_gaps == 0 or is_last_line:
# Last line or single word, left-justify with one space
return ' '.join(words_on_line).ljust(line_width)
else:
spaces_to_distribute = line_width - total_characters
base_space = spaces_to_distribute // number_of_gaps
extra_spaces = spaces_to_distribute % number_of_gaps
justified_line = ''
for i in range(number_of_words - 1):
justified_line += words_on_line[i]
justified_line += ' ' * (base_space + (1 if i < extra_spaces else 0))
justified_line += words_on_line[-1]
return justified_line
justified_text_all_arrangements = []
for arrangement in all_arrangements:
justified_text = []
for i in range(len(arrangement)):
is_last_line = (i == len(arrangement) - 1)
justified_line = justify_line(arrangement[i], max_width, is_last_line)
justified_text.append(justified_line)
justified_text_all_arrangements.append('
'.join(justified_text))
# In a real brute-force approach, we'd score each solution based on space distribution.
# Here, we'll just return the first valid arrangement.
if justified_text_all_arrangements:
return justified_text_all_arrangements[0]
else:
return ''Big(O) Analysis
Time Complexity
O(2^n) – The brute force approach explores all possible line breaks within the input word list. In the worst case, for each of the n-1 spaces between words, we have the option of inserting a line break or not. This results in 2^(n-1) possible combinations of line breaks to explore. Since 2^(n-1) is proportional to 2^n, the time complexity grows exponentially with the number of words. Therefore, the algorithm's runtime is O(2^n).
Space Complexity
O(N^2) – The brute force approach explores all possible ways to split the words into lines. It implicitly maintains a list of possible arrangements of words into lines. In the worst-case scenario, it explores an exponential number of combinations; however, to store the "best" arrangement and intermediate arrangements, the algorithm might need to store a list of line arrangements, each of which can contain at most N words, and there might be at most N possible lines since there are N words. Therefore, auxiliary space can grow up to O(N^2) since at any point we might be storing combinations of lines and words.
Optimal Solution
Approach
The best way to solve this problem is to build each line one at a time by picking as many words as possible for each line. We then distribute the spaces as evenly as we can and repeat the process for the next line. The last line is handled differently by adding spaces to the end.
Here's how the algorithm would work step-by-step:
- Take as many words as possible from the list to fill each line up to the maximum width.
- For each line (except the last), figure out how much space is left over after placing the words.
- Divide the extra spaces as evenly as possible between the words on the line. If the division is not even, add the extra spaces to the spaces on the left.
- For the very last line, just put one space between each word, and add all the extra spaces to the end of the line.
Code Implementation
def full_justify(words, max_width):
result = []
current_line = []
current_line_length = 0
for word in words:
if current_line_length + len(word) + len(current_line) > max_width:
# Time to justify and add the current line to the result.
if len(current_line) == 1:
justified_line = current_line[0] + ' ' * (max_width - current_line_length)
else:
spaces_needed = max_width - current_line_length
space_per_gap = spaces_needed // (len(current_line) - 1)
extra_spaces = spaces_needed % (len(current_line) - 1)
justified_line = ''
for i in range(len(current_line) - 1):
justified_line += current_line[i] + ' ' * (space_per_gap + (1 if i < extra_spaces else 0))
justified_line += current_line[-1]
result.append(justified_line)
# Start a new line with the current word.
current_line = [word]
current_line_length = len(word)
else:
# Add the current word to the current line.
current_line.append(word)
current_line_length += len(word)
# Justify the last line, left-justified.
last_line = ' '.join(current_line)
last_line += ' ' * (max_width - len(last_line))
result.append(last_line)
return resultBig(O) Analysis
Time Complexity
O(n) – The algorithm iterates through the words array (of size n) once to determine the words on each line. Then for each line, it distributes spaces which is proportional to the number of words on the line, but this cost is still bounded by n as all words are processed. Therefore the dominant operation is a single pass through the input words, making the time complexity O(n).
Space Complexity
O(N) – The described algorithm constructs lines of words. Each line is built and then justified before moving on to the next. In the worst case, all words may fit on a single line, or each word could form its own line. While the plain English explanation doesn't explicitly dictate *how* each line is constructed, storing the words for a single line prior to justification implies maintaining a list of words whose maximum size will be the number of input words. Thus, the auxiliary space required to store the words for the current line scales linearly with the number of input words, N. Therefore, the space complexity is O(N).
Edge Cases
| Case | How to Handle |
|---|---|
| Empty input array of words | Return an empty list of strings as there are no words to justify. |
| maxWidth is zero or negative | Return an empty list or throw an exception, as a zero or negative width is invalid. |
| Single word longer than maxWidth | Return a list containing the truncated word (or the whole word if truncation is not desired), left-justified, filling the rest with spaces. |
| Single word input | Left-justify the single word and pad with spaces to maxWidth. |
| maxWidth is just large enough to hold one word and spaces | Handle this case correctly without creating extra lines or failing to justify properly. |
| Last line with only one word | Left-justify the single word and pad with spaces to maxWidth. |
| Input with many short words resulting in a long last line | Ensure last line is left-justified even if it's close to maxWidth. |
| Words containing leading or trailing spaces | Trim the leading/trailing spaces from the words before processing to avoid unexpected justification results. |
Explore Interview QuestionsGoogle Interview QuestionsMeta Interview QuestionsAmazon Interview QuestionsApple Interview QuestionsNetflix Interview Questions
Explore Jobs By LevelEntry-Level Software Engineer JobsMid-Level Software Engineer JobsSenior Software Engineer JobsStaff Software Engineer Jobs
