Text Justification
Understanding the Problem
This reads like a simple string formatting task, but the bookkeeping is what makes it hard. There are three separate decisions: which words go on each line, how many spaces go between those words, and which lines follow a different rule.
The spacing is the part that takes care. When the extra spaces on a line do not divide evenly among the gaps between words, the leftmost gaps each get one extra space. Two lines also ignore even distribution entirely: a line holding a single word is left-justified and padded on the right, and the last line is always left-justified no matter how many words it holds.
Underneath, this is a greedy packing problem. Pack as many words as fit on a line, then format that line according to the justification rules.
Key Constraints:
1 <= words.length <= 300→ A line scan that visits each word once is more than fast enough; no asymptotic concern drives the design here.1 <= words[i].length <= 20→ Every word fits withinmaxWidth, so no word ever needs to be split across lines.1 <= maxWidth <= 100→ Lines are short, so string building per line is cheap.
Approach 1: Greedy Line Packing (Simulation)
Intuition
There is no brute-force-to-optimal progression here. The problem fixes a single strategy: pack words into lines greedily, then format each line. The difficulty is in the formatting, not in choosing an algorithm.
Fill a line one word at a time. Keep adding words while the running total (the words plus one space between each adjacent pair) stays within maxWidth. When the next word would push the line over, the current line is complete. Distribute its spaces, then start the next line at the word that did not fit.
Formatting a finished line splits into three cases:
- A middle line with multiple words: spread the spaces across the gaps between words. When the spaces do not divide evenly, the leftmost gaps each take one extra space.
- A line with a single word: place the word at the left and pad the rest of the width with spaces.
- The last line: put single spaces between words, then pad the remaining width on the right.
The greedy packing is forced by the problem, which requires as many words per line as will fit. Leaving room on a line never helps, because the rules judge each line on its own, not on the raggedness of the paragraph (which is what would call for dynamic programming). Once the words on a line are fixed, the spacing is determined: with g gaps and s total spaces, each gap gets s / g spaces and the first s % g gaps take one more. That places (s % g) extra spaces, so the widths sum back to s and the leftmost gaps stay widest, exactly as the rules require.
Algorithm
- Initialize an index
i = 0to track the current word. - While
i < words.length: - Find which words fit on the current line. Start with
words[i]and keep adding words as long as the total length (words + minimum one space between each) does not exceedmaxWidth. - Calculate the total character length of the words on this line.
- If this is the last line OR the line has only one word, left-justify: join words with single spaces and pad the right with spaces.
- Otherwise, calculate the number of gaps between words. Divide total extra spaces evenly among gaps, with leftmost gaps getting one extra space if there's a remainder.
- Build the line string and add it to the result.
- Return the result.
Visualization and Code
Loading animation...
- Time Complexity: O(n * maxWidth). Each word is visited once while grouping words into lines, and building each formatted line takes O(maxWidth). With n up to 300 and maxWidth up to 100, the total work stays well under a few tens of thousands of operations.
- Space Complexity: O(n * maxWidth) for the output, which holds every justified line. Beyond the output, only a few integer variables are used, so the auxiliary space is O(1).