Problem statement

You are laying out a paragraph for a fixed-width display. Given the words of the paragraph (in order) and the line width maxWidth, return the lines of the fully justified text — every line exactly maxWidth characters long.

Fill the lines greedily: put as many words on a line as fit when consecutive words are separated by at least one space.

Then pad each line with spaces:

• A line that is not the last line and holds two or more words spreads its spaces between the words as evenly as possible. If the gaps cannot all be equal, the gaps further left get one extra space.
• The last line, and any line holding a single word, is left-justified: words separated by exactly one space, with the remaining spaces added at the end.

A word never contains a space, and no word is longer than maxWidth.

Example 1

Input: words = ["Practice","makes","progress","on","CodeKairo","every","day."], maxWidth = 16
Output: ["Practice   makes","progress      on","CodeKairo  every","day.            "]
Explanation: Each full line gets all its spare spaces in its single gap; `day.` is the last line, so it is padded on the right.

Example 2

Input: words = ["a","b","c","d","e"], maxWidth = 3
Output: ["a b","c d","e  "]

Example 3

Input: words = ["consistency","beats","talent"], maxWidth = 14
Output: ["consistency   ","beats talent  "]
Explanation: The first line holds a single word, so it is left-justified even though it is not the last line.

Constraints

• 1 <= words.length <= 300
• 1 <= words[i].length <= 20
• words[i] consists of English letters, digits and the symbols . , ! ? ( )
• 1 <= maxWidth <= 100
• words[i].length <= maxWidth

Hints for Text Justification

1. Hint 1

   Handle the paragraph one line at a time: first decide which words go on the line, then decide how to space them.

2. Hint 2

   Words i..j-1 fit on a line when the sum of their lengths plus j - i - 1 single spaces is at most maxWidth. Extend j while the next word still fits.

3. Hint 3

   For a middle line with g gaps and S spare spaces, every gap gets S / g spaces and the first S % g gaps get one more. The last line and single-word lines are joined with single spaces and padded on the right.

How to solve Text Justification

The greedy rule fixes which words share a line, so the problem is pure bookkeeping: pack a line, then distribute its spaces with integer division, giving the remainder to the leftmost gaps.

Approach

1. Start at word i = 0. Grow j from i while len + words[j].length + (j - i) <= maxWidth, where len is the total letters already on the line and j - i counts the single spaces needed before word j.
2. Words i..j-1 form the line. Let gaps = j - i - 1 and spaces = maxWidth - len.
3. If j reached the end, or gaps == 0, join the words with one space and pad the end with spaces up to maxWidth.
4. Otherwise each gap gets spaces / gaps spaces, and the first spaces % gaps gaps get one extra.
5. Append the line, set i = j and repeat until every word is placed.

Why it works

Greedy packing is what the statement prescribes, so each line's word set is forced. Within a line the spaces must total maxWidth - len; an even split differs by at most one between gaps, and the rule that the left gaps are larger pins down exactly which gaps get the extra space — so the output is unique and the construction produces it.

Complexity

• Time — O(total characters)
• Space — O(maxWidth) besides the output

Pitfalls

• A single-word line in the middle of the paragraph is left-justified — dividing by zero gaps is the usual crash.
• The last line is left-justified even when it has several words, and it still needs trailing spaces up to maxWidth.
• When counting whether word j fits, include one space for every word already on the line (j - i of them), not j - i - 1.

Reference solution

Python

from typing import List

def fullJustify(words: List[str], maxWidth: int) -> List[str]:
    res = []
    n, i = len(words), 0
    while i < n:
        j, length = i, 0
        while j < n and length + len(words[j]) + (j - i) <= maxWidth:
            length += len(words[j])
            j += 1
        gaps = j - i - 1
        if j == n or gaps == 0:
            line = " ".join(words[i:j])
            res.append(line + " " * (maxWidth - len(line)))
        else:
            spaces = maxWidth - length
            base, extra = divmod(spaces, gaps)
            parts = []
            for g in range(i, j):
                parts.append(words[g])
                if g < j - 1:
                    parts.append(" " * (base + (1 if g - i < extra else 0)))
            res.append("".join(parts))
        i = j
    return res

Java

public static String[] fullJustify(String[] words, int maxWidth) {
    List<String> res = new ArrayList<>();
    int n = words.length, i = 0;
    while (i < n) {
        int j = i, len = 0;
        while (j < n && len + words[j].length() + (j - i) <= maxWidth) {
            len += words[j].length();
            j++;
        }
        int gaps = j - i - 1;
        StringBuilder sb = new StringBuilder();
        if (j == n || gaps == 0) {
            for (int g = i; g < j; g++) {
                if (g > i) sb.append(' ');
                sb.append(words[g]);
            }
            while (sb.length() < maxWidth) sb.append(' ');
        } else {
            int spaces = maxWidth - len, base = spaces / gaps, extra = spaces % gaps;
            for (int g = i; g < j; g++) {
                sb.append(words[g]);
                if (g < j - 1) {
                    int cnt = base + (g - i < extra ? 1 : 0);
                    for (int c = 0; c < cnt; c++) sb.append(' ');
                }
            }
        }
        res.add(sb.toString());
        i = j;
    }
    return res.toArray(new String[0]);
}

C++

vector<string> fullJustify(vector<string>& words, int maxWidth) {
    vector<string> res;
    int n = words.size(), i = 0;
    while (i < n) {
        int j = i, len = 0;
        while (j < n && len + (int)words[j].size() + (j - i) <= maxWidth) {
            len += words[j].size();
            j++;
        }
        int gaps = j - i - 1;
        string line;
        if (j == n || gaps == 0) {
            for (int g = i; g < j; g++) {
                if (g > i) line += ' ';
                line += words[g];
            }
            line += string(maxWidth - (int)line.size(), ' ');
        } else {
            int spaces = maxWidth - len, base = spaces / gaps, extra = spaces % gaps;
            for (int g = i; g < j; g++) {
                line += words[g];
                if (g < j - 1) line += string(base + (g - i < extra ? 1 : 0), ' ');
            }
        }
        res.push_back(line);
        i = j;
    }
    return res;
}

JavaScript

var fullJustify = function(words, maxWidth) {
    var res = [];
    var n = words.length, i = 0;
    while (i < n) {
        var j = i, len = 0;
        while (j < n && len + words[j].length + (j - i) <= maxWidth) {
            len += words[j].length;
            j++;
        }
        var gaps = j - i - 1;
        var line = "";
        if (j === n || gaps === 0) {
            line = words.slice(i, j).join(" ");
            while (line.length < maxWidth) line += " ";
        } else {
            var spaces = maxWidth - len;
            var base = Math.floor(spaces / gaps), extra = spaces % gaps;
            for (var g = i; g < j; g++) {
                line += words[g];
                if (g < j - 1) {
                    var cnt = base + (g - i < extra ? 1 : 0);
                    for (var c = 0; c < cnt; c++) line += " ";
                }
            }
        }
        res.push(line);
        i = j;
    }
    return res;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Design Movie Rental System Hard
• Prefix and Suffix Search Hard
• Height of Binary Tree After Subtree Removal Queries Hard
• Stamping the Grid Hard
• Maximum Number of Ways to Partition an Array Hard
• Smallest Rotation with Highest Score Hard