Log inSign up
hardleetcodeNot Started

Text Justification

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Strings
Solve on leetcode
Lesson

Problem Statement

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 0 and not exceed maxWidth. - The input array words contains at least one word.

Example 1 · Example:

Input: words = ["This", "is", "an", "example", "of", "text", "justification."], maxWidth = 16
Output: ["This is an","example of text","justification. "]
Explanation: Line 1: 3 words, 16 - (4+2+2) = 8 spaces split into 2 gaps (4 each). Line 2: 3 words, 16 - (7+2+4) = 3 spaces split into 2 gaps (2 then 1). Line 3: Last line is left-justified.

Example 2 · Example:

Input: words = ["What","must","be","acknowledgment","shall","be"], maxWidth = 16
Output: ["What must be","acknowledgment ","shall be "]
Explanation: Single word line "acknowledgment " is left justified with trailing padding.

Constraints:

  • 1 <= words.length <= 300
  • 1 <= words[i].length <= 20
  • words[i] consists of only English letters and symbols.
  • 1 <= maxWidth <= 100
  • words[i].length <= maxWidth

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Simulate greedy line packing with width constraints.
  • Formulate integer division and modulo space distribution.
  • Distinguish between standard full justification and last-line left justification.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Typesetting and text justification algorithms.
  • Exact-width block formatting with custom alignment rules.

Algorithmic Decision Tree:

  • Greedy Line Partitioning
  • Space Redistribution

Connected Patterns:

Zigzag ConversionString CompressionRearrange String

1. Iterative Word Buffer Accumulation

Intuition

Maintain currentLine buffer. Iterate through words: if adding word exceeds maxWidth, format currentLine, add to result, and start new line. Format remaining words as the last left-justified line.

When to apply: Basic baseline comparison.

Algorithm

  1. Initialize res = [], line = [], lineChars = 0.
  2. For word in words:
  3. If lineChars + word.length + line.length > maxWidth:
  4. Format line with spaces and push to res.
  5. Reset line = [], lineChars = 0.
  6. line.push(word); lineChars += word.length.
  7. Format last line (left-justified) and push to res.
  8. Return res.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <vector>
4
5class Solution {
6public:
7 std::vector<std::string> fullJustify(std::vector<std::string>& words, int maxWidth) {
8 std::vector<std::string> res;
9 int i = 0, n = words.size();
10
11 while (i < n) {
12 int j = i, lineLen = 0;
13 while (j < n && lineLen + (int)words[j].size() + (j - i) <= maxWidth) {
14 lineLen += words[j].size();
15 j++;
16 }
17
18 std::string line = "";
19 int numWords = j - i;
20 int totalSpaces = maxWidth - lineLen;
21
22 // Last line or single-word line -> left justify
23 if (j == n || numWords == 1) {
24 for (int k = i; k < j; ++k) {
25 line += words[k];
26 if (k < j - 1) line += " ";
27 }
28 while ((int)line.size() < maxWidth) line += " ";
29 } else {
30 int baseSpaces = totalSpaces / (numWords - 1);
31 int extraSpaces = totalSpaces % (numWords - 1);
32
33 for (int k = i; k < j - 1; ++k) {
34 line += words[k];
35 int spaces = baseSpaces + (k - i < extraSpaces ? 1 : 0);
36 line.append(spaces, ' ');
37 }
38 line += words[j - 1];
39 }
40
41 res.push_back(line);
42 i = j;
43 }
44 return res;
45 }
46};
47
48int main() {
49 Solution sol;
50 std::vector<std::string> words = {"This", "is", "an", "example", "of", "text", "justification."};
51 auto ans = sol.fullJustify(words, 16);
52 for (const auto& line : ans) std::cout << '"' << line << '"' << std::endl;
53 return 0;
54}

Time & Space Complexity

  • Time complexity: O(Total Characters) — Every character and space is created and appended in linear time.
  • Space complexity: O(Total Characters)

Why Brute Force Doesn't Scale:

Two-pointer slice evaluation in O(N) total character complexity.

Exact string pre-allocation (reserve(maxWidth)).

2. Clean Two-Pointer Line Boundary Scanner

Intuition

Pointer i marks line start, j advances greedily while words fit. Format current slice words[i...j-1]. Update i = j.

When to apply: Standard production layout.

Algorithm

  1. While i < n:
  2. Find maximum j such that words fit.
  3. Build line string handling 1-word/last-line vs multi-word cases.
  4. Append to output and advance i = j.
  5. Return result.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <vector>
4
5class Solution {
6public:
7 std::vector<std::string> fullJustify(std::vector<std::string>& words, int maxWidth) {
8 std::vector<std::string> res;
9 int n = words.size();
10
11 for (int i = 0; i < n; ) {
12 int j = i, len = 0;
13 while (j < n && len + (int)words[j].size() + (j - i) <= maxWidth) {
14 len += words[j].size();
15 j++;
16 }
17
18 std::string s;
19 int numWords = j - i;
20 int spaces = maxWidth - len;
21
22 if (numWords == 1 || j == n) {
23 for (int k = i; k < j; ++k) {
24 s += words[k];
25 if (k < j - 1) s += ' ';
26 }
27 s.append(maxWidth - (int)s.size(), ' ');
28 } else {
29 int base = spaces / (numWords - 1);
30 int rem = spaces % (numWords - 1);
31
32 for (int k = i; k < j - 1; ++k) {
33 s += words[k];
34 s.append(base + (k - i < rem ? 1 : 0), ' ');
35 }
36 s += words[j - 1];
37 }
38 res.push_back(s);
39 i = j;
40 }
41 return res;
42 }
43};
44
45int main() {
46 Solution sol;
47 std::vector<std::string> words = {"What","must","be","acknowledgment","shall","be"};
48 auto ans = sol.fullJustify(words, 16);
49 for (const auto& line : ans) std::cout << '"' << line << '"' << std::endl;
50 return 0;
51}

Time & Space Complexity

  • Time complexity: O(Total Characters) — Each word is visited once to find line bounds and once to build the line.
  • Space complexity: O(Total Characters)

3. Modular Dynamic Buffer Construction (Optimal)

Intuition

Using two pointers i and j, we determine line bounds in greedy O(1) checks per word. For full justification, the extra spaces totalSpaces % (numWords - 1) are added to the first extraSpaces word gaps. Single word lines and last lines pad spaces strictly to the right.

When to apply: The standard gold standard solution.

Algorithm

  1. Initialize res = [] and pointer i = 0.
  2. While i < n:
  3. Greedily find j such that lineLen + wordLen + (j - i) <= maxWidth.
  4. If j == n || j - i == 1: format left-justified with single spaces and trailing pad.
  5. Else: distribute spaces / (j - i - 1) base spaces and spaces % (j - i - 1) remainder spaces to left gaps.
  6. Push formatted line to res.
  7. Advance i = j.
  8. Return res.

Greedy Line Fitting and Round-Robin Space Distribution

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [This, is, an, example, of, text, justification.]
Current operationSTEP 1 OF 6
Observation: Test words for Line 1: "This" (4), "is" (2), "an" (2)
Visual state
Values and pointers at this exact step
array
S
This
is
an
example
0
↑ Line 1 candidates: ["This", "is", "an"]
1
2
3
Variables at this step
lineWords
["This","is","an"]
charCount
8
minSpaces
2
totalLen
10
maxWidth
16
Why this step matters

Observation: Test words for Line 1: "This" (4), "is" (2), "an" (2). Word character sum = 8. With 2 mandatory single spaces, length is 8 + 2 = 10 <= 16.

Decision: Adding next word "example" (7 chars) would need 10 + 1 + 7 = 18 > 16. Close Line 1 with 3 words.

Invariant: Each formatted line never exceeds maxWidth.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <vector>
4
5class Solution {
6public:
7 std::vector<std::string> fullJustify(std::vector<std::string>& words, int maxWidth) {
8 std::vector<std::string> res;
9 int n = words.size();
10 int i = 0;
11
12 while (i < n) {
13 int j = i, lineChars = 0;
14 while (j < n && lineChars + (int)words[j].size() + (j - i) <= maxWidth) {
15 lineChars += words[j].size();
16 j++;
17 }
18
19 std::string line;
20 line.reserve(maxWidth);
21 int count = j - i;
22 int totalSpaces = maxWidth - lineChars;
23
24 if (j == n || count == 1) {
25 for (int k = i; k < j; ++k) {
26 line += words[k];
27 if (k < j - 1) line += ' ';
28 }
29 line.append(maxWidth - (int)line.size(), ' ');
30 } else {
31 int baseSpaces = totalSpaces / (count - 1);
32 int extraSpaces = totalSpaces % (count - 1);
33
34 for (int k = i; k < j - 1; ++k) {
35 line += words[k];
36 line.append(baseSpaces + (k - i < extraSpaces ? 1 : 0), ' ');
37 }
38 line += words[j - 1];
39 }
40
41 res.push_back(std::move(line));
42 i = j;
43 }
44 return res;
45 }
46};
47
48int main() {
49 Solution sol;
50 std::vector<std::string> words = {"This", "is", "an", "example", "of", "text", "justification."};
51 auto ans = sol.fullJustify(words, 16);
52 for (const auto& line : ans) std::cout << '"' << line << '"' << std::endl;
53 return 0;
54}

Time & Space Complexity

  • Time complexity: O(Total Characters) strictly — Optimal linear time matching total character output size.
  • Space complexity: O(Total Characters)

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Dividing spaces by count instead of count - 1 gaps between words.

Pitfall 2:

Distributing extra remainder spaces from right to left instead of left to right.

Pitfall 3:

Applying full justification to the last line instead of left justification.

Crucial Edge Cases to Validate:

  • Single word fills entire line (word.length == maxWidth): Places word with 0 extra spaces, perfectly filling line.
  • Single word shorter than maxWidth on middle line: Left-justifies with trailing spaces.
  • Last line has multiple words: Joins with single spaces and pads remaining width at the end.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Structure code into three clear sections: line boundary detection, justification mode selection, and string construction.
  2. Always check for count == 1 before performing modulo operations to avoid division by zero.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.How are extra remaining spaces distributed when totalSpaces % (numWords - 1) != 0?

Back to DSA Sheet