68. Text Justification - Explanation

Description

You are 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:

Input: words = ["This","is","an","example","of","text","justification."], maxWidth = 16

Output: [
   "This    is    an",
   "example  of text",
   "justification.  "
]

Example 2:

Input: words = ["What","must","be","acknowledgment","shall","be"], maxWidth = 16

Output: [
  "What   must   be",
  "acknowledgment  ",
  "shall be        "
]

Explanation: Note that the last line is "shall be " instead of "shall be", because the last line must be left-justified instead of fully-justified.
Note that the second line is also left-justified because it contains only one word.

Example 3:

Input: words = ["Science","is","what","we","understand","well","enough","to","explain","to","a","computer.","Art","is","everything","else","we","do"], maxWidth = 20

Output: [
  "Science  is  what we",
  "understand      well",
  "enough to explain to",
  "a  computer.  Art is",
  "everything  else  we",
  "do                  "
]

Constraints:

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

Topics

Company Tags

Please upgrade to NeetCode Pro to view company tags.

Prerequisites

Before attempting this problem, you should be comfortable with:

String Manipulation - Building justified lines requires precise string concatenation and padding
Greedy Algorithms - Words are greedily packed into each line until no more fit
Modular Arithmetic - Space distribution uses division and remainder to spread spaces evenly among gaps

1. Iteration

Intuition

Text justification requires packing words into lines of fixed width, distributing extra spaces as evenly as possible between words. The challenge is handling three distinct cases: regular lines with multiple words (distribute spaces evenly, with extra spaces going to the left gaps), single-word lines (pad with trailing spaces), and the last line (left-justified with trailing spaces).

The key is to greedily fit as many words as possible on each line, then calculate how to distribute the remaining space among the gaps between words.

Algorithm

Initialize an empty result list and track the current line's words and total character length.
For each word, check if it fits on the current line (considering at least one space between words):
- If it fits, add it to the current line.
- If not, justify the current line:
  - Calculate total extra spaces needed (maxWidth - length).
  - Divide spaces evenly among gaps. Distribute remaining spaces one extra each to leftmost gaps.
  - For single-word lines, add all spaces after the word.
  - Join words and add to result. Start a new line.
Handle the last line separately: left-justify (single space between words) and pad with trailing spaces.
Return the result.

class Solution:
    def fullJustify(self, words: List[str], maxWidth: int) -> List[str]:
        res = []
        line, length = [], 0
        i = 0

        while i < len(words):
            if length + len(words[i]) + len(line) <= maxWidth:
                line.append(words[i])
                length += len(words[i])
                i += 1
            else:
                # Line complete
                extra_space = maxWidth - length
                remainder = extra_space % max(1, (len(line) - 1))
                space = extra_space // max(1, (len(line) - 1))
                for j in range(max(1, len(line) - 1)):
                    line[j] += " " * space
                    if remainder:
                        line[j] += " "
                        remainder -= 1
                res.append("".join(line))
                line, length = [], 0

        # Handling last line
        last_line = " ".join(line)
        trail_space = maxWidth - len(last_line)
        res.append(last_line + " " * trail_space)
        return res

public class Solution {
    public List<String> fullJustify(String[] words, int maxWidth) {
        List<String> res = new ArrayList<>();
        List<String> line = new ArrayList<>();
        int length = 0, i = 0;

        while (i < words.length) {
            // If the current word can fit in the line
            if (length + words[i].length() + line.size() <= maxWidth) {
                line.add(words[i]);
                length += words[i].length();
                i++;
            } else {
                // Line complete
                int extra_space = maxWidth - length;
                int remainder = extra_space % Math.max(1, (line.size() - 1));
                int space = extra_space / Math.max(1, (line.size() - 1));

                for (int j = 0; j < Math.max(1, line.size() - 1); j++) {
                    line.set(j, line.get(j) + " ".repeat(space));
                    if (remainder > 0) {
                        line.set(j, line.get(j) + " ");
                        remainder--;
                    }
                }

                res.add(String.join("", line));
                line.clear();
                length = 0;
            }
        }

        // Handling last line
        String last_line = String.join(" ", line);
        int trail_space = maxWidth - last_line.length();
        res.add(last_line + " ".repeat(trail_space));

        return res;
    }
}

class Solution {
public:
    vector<string> fullJustify(vector<string>& words, int maxWidth) {
        vector<string> res;
        vector<string> line;
        int length = 0, i = 0;

        while (i < words.size()) {
            if (length + words[i].size() + line.size() <= maxWidth) {
                line.push_back(words[i]);
                length += words[i].size();
                i++;
            } else {
                // Line complete
                int extra_space = maxWidth - length;
                int remainder = extra_space % max(1, (int)(line.size() - 1));
                int space = extra_space / max(1, (int)(line.size() - 1));

                for (int j = 0; j < max(1, (int)line.size() - 1); j++) {
                    line[j] += string(space, ' ');
                    if (remainder > 0) {
                        line[j] += " ";
                        remainder--;
                    }
                }

                string justified_line = accumulate(line.begin(), line.end(), string());
                res.push_back(justified_line);
                line.clear();
                length = 0;
            }
        }

        // Handling last line
        string last_line = accumulate(line.begin(), line.end(), string(),
                                      [](string a, string b) {
                                            return a.empty() ? b : a + " " + b;
                                        });
        int trail_space = maxWidth - last_line.size();
        last_line += string(trail_space, ' ');
        res.push_back(last_line);

        return res;
    }
};

class Solution {
    /**
     * @param {string[]} words
     * @param {number} maxWidth
     * @return {string[]}
     */
    fullJustify(words, maxWidth) {
        let res = [];
        let line = [],
            length = 0,
            i = 0;

        while (i < words.length) {
            if (length + words[i].length + line.length <= maxWidth) {
                line.push(words[i]);
                length += words[i].length;
                i++;
            } else {
                // Line complete
                let extra_space = maxWidth - length;
                let remainder = extra_space % Math.max(1, line.length - 1);
                let space = Math.floor(
                    extra_space / Math.max(1, line.length - 1),
                );

                for (let j = 0; j < Math.max(1, line.length - 1); j++) {
                    line[j] += ' '.repeat(space);
                    if (remainder > 0) {
                        line[j] += ' ';
                        remainder--;
                    }
                }

                res.push(line.join(''));
                line = [];
                length = 0;
            }
        }

        // Handling last line
        let last_line = line.join(' ');
        let trail_space = maxWidth - last_line.length;
        res.push(last_line + ' '.repeat(trail_space));

        return res;
    }
}

public class Solution {
    public List<string> FullJustify(string[] words, int maxWidth) {
        List<string> res = new List<string>();
        List<string> line = new List<string>();
        int length = 0, i = 0;

        while (i < words.Length) {
            // If the current word can fit in the line
            if (length + words[i].Length + line.Count <= maxWidth) {
                line.Add(words[i]);
                length += words[i].Length;
                i++;
            } else {
                // Line complete
                int extra_space = maxWidth - length;
                int space = extra_space / Math.Max(1, line.Count - 1);
                int remainder = extra_space % Math.Max(1, line.Count - 1);

                for (int j = 0; j < Math.Max(1, line.Count - 1); j++) {
                    line[j] += new string(' ', space);
                    if (remainder > 0) {
                        line[j] += " ";
                        remainder--;
                    }
                }

                res.Add(string.Join("", line));
                line.Clear();
                length = 0;
            }
        }

        // Handling last line
        string last_line = string.Join(" ", line);
        int trail_space = maxWidth - last_line.Length;
        res.Add(last_line + new string(' ', trail_space));

        return res;
    }
}

func fullJustify(words []string, maxWidth int) []string {
    res := []string{}
    line := []string{}
    length := 0
    i := 0

    for i < len(words) {
        if length+len(words[i])+len(line) <= maxWidth {
            line = append(line, words[i])
            length += len(words[i])
            i++
        } else {
            // Line complete
            extraSpace := maxWidth - length
            gaps := max(1, len(line)-1)
            remainder := extraSpace % gaps
            space := extraSpace / gaps

            for j := 0; j < max(1, len(line)-1); j++ {
                line[j] += strings.Repeat(" ", space)
                if remainder > 0 {
                    line[j] += " "
                    remainder--
                }
            }

            res = append(res, strings.Join(line, ""))
            line = []string{}
            length = 0
        }
    }

    // Handling last line
    lastLine := strings.Join(line, " ")
    trailSpace := maxWidth - len(lastLine)
    res = append(res, lastLine+strings.Repeat(" ", trailSpace))

    return res
}

class Solution {
    fun fullJustify(words: Array<String>, maxWidth: Int): List<String> {
        val res = mutableListOf<String>()
        val line = mutableListOf<String>()
        var length = 0
        var i = 0

        while (i < words.size) {
            if (length + words[i].length + line.size <= maxWidth) {
                line.add(words[i])
                length += words[i].length
                i++
            } else {
                // Line complete
                val extraSpace = maxWidth - length
                val gaps = maxOf(1, line.size - 1)
                var remainder = extraSpace % gaps
                val space = extraSpace / gaps

                for (j in 0 until maxOf(1, line.size - 1)) {
                    line[j] = line[j] + " ".repeat(space)
                    if (remainder > 0) {
                        line[j] = line[j] + " "
                        remainder--
                    }
                }

                res.add(line.joinToString(""))
                line.clear()
                length = 0
            }
        }

        // Handling last line
        val lastLine = line.joinToString(" ")
        val trailSpace = maxWidth - lastLine.length
        res.add(lastLine + " ".repeat(trailSpace))

        return res
    }
}

class Solution {
    func fullJustify(_ words: [String], _ maxWidth: Int) -> [String] {
        var res = [String]()
        var line = [String]()
        var length = 0
        var i = 0

        while i < words.count {
            if length + words[i].count + line.count <= maxWidth {
                line.append(words[i])
                length += words[i].count
                i += 1
            } else {
                // Line complete
                let extraSpace = maxWidth - length
                let gaps = max(1, line.count - 1)
                var remainder = extraSpace % gaps
                let space = extraSpace / gaps

                for j in 0..<max(1, line.count - 1) {
                    line[j] += String(repeating: " ", count: space)
                    if remainder > 0 {
                        line[j] += " "
                        remainder -= 1
                    }
                }

                res.append(line.joined())
                line = []
                length = 0
            }
        }

        // Handling last line
        let lastLine = line.joined(separator: " ")
        let trailSpace = maxWidth - lastLine.count
        res.append(lastLine + String(repeating: " ", count: trailSpace))

        return res
    }
}

impl Solution {
    pub fn full_justify(words: Vec<String>, max_width: i32) -> Vec<String> {
        let max_width = max_width as usize;
        let mut res: Vec<String> = Vec::new();
        let mut line: Vec<String> = Vec::new();
        let mut length = 0usize;
        let mut i = 0;

        while i < words.len() {
            if length + words[i].len() + line.len() <= max_width {
                line.push(words[i].clone());
                length += words[i].len();
                i += 1;
            } else {
                // Line complete
                let extra_space = max_width - length;
                let gaps = 1.max(line.len() - 1);
                let mut remainder = extra_space % gaps;
                let space = extra_space / gaps;

                for j in 0..1.max(line.len() - 1) {
                    line[j].push_str(&" ".repeat(space));
                    if remainder > 0 {
                        line[j].push(' ');
                        remainder -= 1;
                    }
                }

                res.push(line.concat());
                line.clear();
                length = 0;
            }
        }

        // Handling last line
        let last_line = line.join(" ");
        let trail_space = max_width - last_line.len();
        res.push(format!("{}{}", last_line, " ".repeat(trail_space)));

        res
    }
}

Time & Space Complexity

Time complexity: $O(n * m)$
Space complexity: $O(n * m)$

Where $n$ is the number of words and $m$ is the average length of the words.

Common Pitfalls

Forgetting to Account for Spaces When Checking Line Capacity

When determining if a word fits on the current line, you must include the mandatory spaces between words. The check should be length + word.length + numberOfWordsOnLine <= maxWidth, not just length + word.length <= maxWidth. Forgetting the space count causes lines to exceed the maximum width.

Division by Zero with Single-Word Lines

When a line contains only one word, there are zero gaps between words, leading to division by zero when calculating space distribution. Always use max(1, gaps) when dividing to handle single-word lines, where all extra spaces go after the word.

Incorrect Handling of the Last Line

The last line follows different rules: it should be left-justified with single spaces between words and trailing spaces to reach maxWidth. A common mistake is applying the same full-justification logic to the last line, resulting in incorrectly distributed spaces.

Uneven Space Distribution Going to Wrong Gaps

Extra spaces that cannot be evenly distributed must go to the leftmost gaps first. A mistake is distributing remainder spaces to the rightmost gaps or distributing them randomly. The remainder should decrement as you add one extra space to each gap from left to right.

Not Padding Lines to Exact Width

Every line must be exactly maxWidth characters. For single-word lines or the last line, forgetting to append trailing spaces results in lines shorter than required. Always calculate and append maxWidth - currentLineLength spaces at the end.