Abstract / Summary

Given a list of words and a line length, format the text so each line has the specified width using full justification.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 52% (1+ million submissions).

Typical patterns to solve this problem:

• Array
• Simulation
• String

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The implementation builds a fully justified paragraph from a list of words and a maximum line width. It proceeds in two distinct phases: first it groups the input words into lines that respect the width constraint, then it distributes spaces across each line to achieve full justification, handling the final line as a special left-justified case. The algorithm gracefully deals with empty input, lines that contain a single word, and situations where the words exactly fill a line.

Line Construction

The first phase iterates over the original words vector, extracting the front element on each iteration. When the current line buffer is empty, the word starts a new line. Otherwise the code computes the length already occupied by the words in the buffer plus the minimal single spaces between them:

auto used = 0;
for (auto l : line)
    used += l.size();
used += line.size() - 1;

If adding the next word plus a separating space would exceed maxWidth, the current buffer is stored in text and a fresh line is started with the word. Otherwise the word is appended to the existing buffer. After the loop, any remaining words in line are pushed to text. This logic ensures that each sub-vector in text contains the exact set of words that will appear on one output line.

Edge conditions covered here include:

• An empty words vector returns an empty result immediately.
• A word that alone exceeds maxWidth is never encountered because the problem guarantees that each word’s length is ≤ maxWidth.
• When a word fits exactly at the end of a line, the condition used + 1 + w.size() > maxWidth prevents an extra space from being added, so the line is closed precisely at the width limit.

Justification of Intermediate Lines

The second phase processes every line except the last one. For each line l the code first checks whether it contains a single word:

if (l.size() == 1)
{
    auto one = l.front();
    while (one.size() < maxWidth)
        one += ' ';
    result.push_back(one);
    continue;
}

In this case the word is left-padded with spaces until the line reaches maxWidth. This satisfies the requirement that a line with a single word be left-justified.

For lines with multiple words, the algorithm calculates the total number of spaces that must be inserted:

int need = maxWidth;
for (auto w : l)
    need -= w.size();

need now holds the exact count of spaces to distribute among the gaps. The first word is placed in the output string, then each subsequent word is preceded by a calculated number of spaces:

string line = l.front();
for (int j = 1; j < l.size(); j++)
{
    int all   = need / (l.size() - 1);
    int extra = need % (l.size() - 1);

    while (all-- > 0)
        line += ' ';
    if (extra >= j)
        line += ' ';

    line += l[j];
}

all represents the base number of spaces for every gap, while extra captures the remainder that must be distributed one by one starting from the leftmost gaps. The condition extra >= j ensures that the first extra gaps receive one additional space. By recomputing all and extra inside the loop, the code guarantees that the distribution remains consistent even as need is unchanged throughout the iteration.

The resulting line, now exactly maxWidth characters long, is appended to result.

Handling the Last Line

The final line is treated differently: it is left-justified with a single space between words, and any remaining width is filled with trailing spaces.

string last;
for (auto l : text.back())
{
    if (!last.empty())
        last += ' ';
    last += l;
}
while (last.size() < maxWidth)
    last += ' ';
result.push_back(last);

This loop concatenates the words with a single space separator, then pads the end of the line until the required width is met. The approach naturally handles cases where the last line consists of a single word or where the words already occupy the full width.

Edge Cases Addressed

• Empty input - The early return if (words.empty()) return {}; avoids unnecessary processing.
• Single-word lines - Both intermediate and final single-word scenarios are padded with spaces to meet the width requirement.
• Exact fit - When the cumulative length of words plus minimal spaces equals maxWidth, the condition for starting a new line prevents an extra line from being created, and the justification step distributes zero extra spaces, leaving the line unchanged.
• Last line with fewer words - The left-justified handling ensures that the last line never receives the full space distribution logic, preserving the required formatting.

Performance Optimizations

The code minimizes redundant calculations during line construction by computing the occupied length (used) only once per word addition, rather than recomputing the total after each insertion. The use of vector::push_back for both text and result avoids costly reallocations because the vectors grow geometrically. Space padding for single-word lines and the final line is performed with simple while loops that append characters directly to the string, which is efficient given the known final size. The distribution of spaces leverages integer division and modulus to compute the base and extra spaces in constant time per gap, ensuring that the inner loop runs proportionally to the number of words in the line rather than to the width of the line.

Overall, the implementation delivers a clear separation of concerns-line grouping followed by justification-while handling all required edge conditions and employing straightforward arithmetic to achieve the desired layout.

Imagine you have a long list of building blocks that are words, and you want to organize them into neat rows so they all fit perfectly on a page. The page has a fixed width, so you cannot make the rows go past a certain point.

First, the code looks at all the words you have. It starts picking them up one by one and putting them into a row. It is very careful to check if the next word will fit. If the row gets too long, it sets that row aside and starts a new one. It keeps doing this until all the word blocks are sorted into rows.

Once all the rows are ready, the code goes back to make them look tidy. For most of the rows, it takes the empty spaces between the words and spreads them out evenly. It makes sure that the words are pushed to the very left and the very right of the line so that everything looks balanced, almost like blocks perfectly stacked on a shelf.

The very last row of words is a little different. It does not try to spread those words out wide. Instead, it puts the words right next to each other with a single space, and if there is any extra room left over at the end of the line, it just fills that empty spot with invisible space character blocks until the row reaches the edge. After all these steps, the words are all lined up and ready to be read.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

not analyzed yet

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Python	Java						TS
	WalkCCC	C++	Python	Java
	leetcode.ca	C++	Python	Java			C#		Go	TS
	LeetcodeHelp	C++	Python	Java
	MemoryLimitExceeded	C++	Python
	Progiez	C++	Python	Java
github	aylei				Rust
	begeekmyfriend							C
	BigEggStudy						C#
	black-shadows	C++
	charles-wangkai			Java
	everthis					JS
	fengvyi	C++
	gaosq0604		Python
	gouthampradhan			Java
	haoel	C++
	JoshCrozier					JS
	keineahnung2345	C++
	lkwq007		Python
	qiyuangong		Python
	ruoru				Rust
	sonugiri1043	C++
	suxrobGM						C#
	varunu28			Java
	vli02							C
	wisdompeak	C++
	XiaotaoGuo	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, C#, Go, Java, Python, TypeScript
LeetcodeHelp	C++, Java, Python
MemoryLimitExceeded	Python, C++
Progiez	C++, Java, Python
aylei	Rust
begeekmyfriend	C
BigEggStudy	C#
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fengvyi	C++
gaosq0604	Python
gouthampradhan	Java
haoel	C++
JoshCrozier	JavaScript
keineahnung2345	C++
lkwq007	Python
qiyuangong	Python
ruoru	Rust
sonugiri1043	C++
suxrobGM	C#
varunu28	Java
vli02	C
wisdompeak	C++
XiaotaoGuo	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality