← Back to companies
[ OK ] Loaded —
[ INFO ]
$ cd
$ ls -lt
01
02
03
04
05
$ ls -lt
01
02
03
04
05
user@intervues:~/$
You are given an array of words and a maximum line width. Your task is to format the text such that each line contains exactly maxWidth characters and is fully justified.
Pack as many words as possible into each line using a greedy approach: start with the first word and keep adding words until adding the next word would exceed maxWidth. Then format that line according to these rules:
maxWidth.Return an array of strings representing the formatted lines.
maxWidth charactersExample 1:
Input: words = ["This", "is", "an", "example", "of", "text", "justification."], maxWidth = 16 Output: ["This is an", "example of text", "justification. "] Explanation: Line 1: "This is an" = 10 chars, 6 spaces needed → distribute as 4-2 Line 2: "example of text" = 15 chars, 1 space needed → distribute evenly Line 3: Last line, left-justified with trailing spaces
Example 2:
Input: words = ["What", "must", "be", "acknowledgment", "shall", "be"], maxWidth = 16 Output: ["What must be", "acknowledgment ", "shall be "] Explanation: Line 1: Three words with 3 spaces distributed as 3-0 Line 2: Single word, left-justified Line 3: Last line, left-justified
Example 3:
Input: words = ["a"], maxWidth = 5 Output: ["a "] Explanation: Single word is left-justified with trailing spaces.
Hint 1: Greedy Line Packing First, determine which words belong on each line. Start with the first word and keep adding words while the total length (including at least one space between words) doesn't exceed
maxWidth. This greedy approach ensures you pack as many words as possible per line.
Hint 2: Space Distribution For a line with multiple words that isn't the last line, calculate the total number of spaces needed. Divide this by the number of gaps between words to get the base number of spaces per gap. The remainder tells you how many gaps need one extra space, and these should be the leftmost gaps.
Hint 3: Edge Cases Handle these special cases differently:
- Single word on a line: left-justify with trailing spaces
- Last line of text: left-justify with single spaces between words
- Normal lines: fully justify with even distribution
Full Solution `` Approach:
Greedy Packing: Iterate through words and pack as many as possible into each line. A word fits if
current_length + number_of_gaps + word_length ≤ maxWidth.Line Formatting: Once a line is full, format it based on whether it's the last line:
- Last line or single word: Left-justify with single spaces between words and trailing spaces
- Regular line: Calculate total spaces needed, divide by gaps to get base spaces per gap, and distribute remainder to leftmost gaps
Space Distribution: For full justification with
kgaps andstotal spaces:
- Each gap gets
s // kspaces- The first
s % kgaps get one additional spaceTime Complexity: O(n) where n is the total number of characters across all words. We process each word once and build each line once.
Space Complexity: O(n) for storing the result array and temporary line buffers.
def fullJustify(words, maxWidth):
"""
Format text with full justification.
Time Complexity: O(n) where n is the total number of characters across all words
Space Complexity: O(n) for storing the result
"""
result = []
current_line = []
current_length = 0
for word in words:
# Check if adding this word would exceed maxWidth
# We need: current_length + len(current_line) spaces + len(word)
if current_length + len(current_line) + len(word) > maxWidth:
# Format and add the current line
result.append(format_line(current_line, current_length, maxWidth, False))
current_line = []
current_length = 0
current_line.append(word)
current_length += len(word)
# Add the last line (left-justified)
result.append(format_line(current_line, current_length, maxWidth, True))
return result
def format_line(words, total_chars, maxWidth, is_last):
"""
Format a single line according to justification rules.
Args:
words: List of words in this line
total_chars: Total character count of all words
maxWidth: Target width for the line
is_last: Whether this is the last line
"""
if is_last or len(words) == 1:
# Left-justify: single space between words, rest at the end
line = ' '.join(words)
return line + ' ' * (maxWidth - len(line))
# Full justification
total_spaces = maxWidth - total_chars
gaps = len(words) - 1
spaces_per_gap = total_spaces // gaps
extra_spaces = total_spaces % gaps
# Build the line
line = []
for i, word in enumerate(words):
line.append(word)
if i < gaps:
# Add base spaces plus one extra for leftmost gaps
spaces = spaces_per_gap + (1 if i < extra_spaces else 0)
line.append(' ' * spaces)
return ''.join(line)