1. Problem Statement (Simple Explanation)
You’re given:
An array of words words (non-empty strings, no spaces inside).
An integer maxWidth.
You must format the text so that:
Each line has exactly maxWidth characters.
Lines are fully justified (both left and right), except the last line which is left-justified.
You must pack words greedily in each line: take as many words as can fit in that line.
You pad with spaces ' ' as necessary.
Space distribution rules for non-last lines:
Extra spaces between words should be distributed as evenly as possible.
If spaces do not divide evenly, left slots get more spaces than right slots.
If a line has only one word, it is left-justified (word at left, rest spaces).
2. Examples
Example 1:
Input:
words = ["This", "is", "an", "example", "of", "text", "justification."]
maxWidth = 16
Output:
[
"This is an",
"example of text",
"justification. "
]
Line 1: "This is an" → 3 words, total letters = 4+2+2=8, spaces to add = 16-8=8.
2 gaps → each at least 8 / 2 = 4 spaces → "This****is****an" (* denotes a space).Line 2: "example of text" → letters = 7+2+4=13, spaces = 3, 2 gaps → base = 3/2=1 space, remainder 1 → leftmost gap gets 2 spaces: "example__of_text".
Line 3 (last line): left-justified: "justification. ".
Example 2:
Input:
words = ["What","must","be","acknowledgment","shall","be"]
maxWidth = 16
Output:
[
"What must be",
"acknowledgment ",
"shall be "
]
The last two lines each contain a single word (or effectively one big word line), which are left-justified.
3. Approach – Greedy Line Packing + Justification
We proceed in two main phases:
Group words into lines (by index ranges) using greedy packing.
Format each line:
Either full-justified (inner lines)
Or left-justified (last line or single-word line).
3.1 Greedy Packing
We iterate over words with index i:
Start a new line at lineStart = i.
Use variable lineLen = 0 for total letters in current line.
While i < n and adding words[i] with needed spaces fits in maxWidth:
Condition to add words[i]: lineLen + (i - lineStart) + len(words[i]) <= maxWidth
lineLen = sum of word lengths in line so far.
(i - lineStart) = number of spaces between words already added (minimum one space between words).
If fits: add len(words[i]) to lineLen, increment i.
When loop stops, words in this line are words[lineStart .. i-1].
Determine:
isLastLine = (i == n)
Then we format this line.
3.2 Formatting a Line
Let:
count = i - lineStart = number of words in this line.
totalChars = sum of word lengths in line.
There are two cases:
Case A – Last Line OR Single-Word Line
Left-justify:
Join words with single spaces: line = "word1 word2 ... wordK"
Compute remaining = maxWidth - len(line)
Append remaining spaces at the end.
Case B – Full Justification (multiple words, not last line)
Number of gaps between words: gaps = count - 1.
Total spaces = maxWidth - totalChars.
Base spaces per gap: base = totalSpaces // gaps.
Extra spaces: extra = totalSpaces % gaps.
First extra gaps get base + 1 spaces.
Remaining gaps get base spaces.
Build line:
Start with words[lineStart].
For each gap g from 0 to gaps-1:
Insert ' ' * (base + (1 if g < extra else 0)).
Append next word.
Result line length will be maxWidth.
Pseudo-code (High Level):
Let:
n = len(words)
L = maxWidth
Total characters across words is at most n * 20. Each word is processed a constant number of times.
Time: O(total characters) ≈ O(n * average word length), bounded by O(n * 20) ~ O(n).
Space: O(total characters) for result; extra is O(1).
4. Java code
8. C code(outline)
In C, you’d:
Use char** result with enough capacity (worst case words.length lines).
For each line, allocate a char* of size maxWidth + 1 and fill it according to logic above.
Carefully track returnSize and returnColumnSizes.
Due to pointer management verbosity, C++/Java/Python/JS are usually preferred for this problem.
Comments
Post a Comment