68. Text Justification

HardArrayStringSimulation
Leetcode Link

Problem Description

The given problem requires us to format an array of strings words into a text that has to be justified according to a given width maxWidth. Being justified means that each line of the text should have exactly maxWidth characters, if necessary, by adding extra spaces between words. The text formatting must be done in the following way:

  1. Words are aligned in a greedy manner, meaning we need to fit as many words as possible on each line.
  2. The spaces added to reach maxWidth should be as evenly distributed as possible amongst the words on a line.
  3. If spaces don't evenly divide between the words, the extra spaces should be added to the leftmost gaps first.
  4. The last line of the text should be left-justified, which means it should not have extra space between words other than necessary, and no extra spaces should be added at the end of the last line to reach the maxWidth.

Some additional constraints are given to define what constitutes a word and the conditions that any given word and input will adhere to.

Intuition

To arrive at the solution, we follow these steps:

  1. We initialize an empty list ans to hold the formatted lines of text. We also set up a couple of indices i and n to keep track of our current position in the words list and the total number of words respectively.

  2. Then we loop over the words using the index i:

    • For each iteration (new line), we initialize a temporary list t to store the words on the current line and a cnt variable to keep track of the character count including spaces. We add the first word to t and increase i and cnt accordingly.
    • We continue adding words to t while ensuring we do not exceed maxWidth when adding the next word along with a space. For each word we add, we update cnt.

  3. We check if we reached the end of words or if the line has only one word. In these cases, we format the line as left-justified by joining the words with spaces and then adding extra spaces to the right to reach maxWidth. We add this line to ans and continue to the next iteration.

  4. If we have more than one word and we're not at the last line, we need to distribute additional spaces evenly between words. We calculate the total width of spaces space_width required. We then evenly divide this space_width between the gaps by using divmod to get the number of spaces for most gaps (w) and the remainder (m) that tells us how many gaps should have an extra space.

  5. We create the formatted line by adding each word from t to a new list row, followed by the appropriate number of spaces based on the remainder m. The last word is just added without extra space because we need to right justify the rest of the line.

  6. We join together the words with the added spaces to form the fully justified line and append it to ans.

  7. Once all words have been processed and all lines formatted, we return ans containing the justified text.

This approach ensures that each line is fully justified according to the rules given in the problem description, and all lines contain exactly maxWidth characters.

Solution Approach

The solution uses a few common list operations, string manipulation techniques, and simple arithmetic to achieve the text justification. Here's an in-depth look at the algorithm and data structures used:

  1. Initialization: We start off with initializing necessary variables:

    • ans is a list that will eventually contain all our justified lines.
    • Two pointers, i and n, serve as the current index in the words array and the total number of words, respectively.

  2. Greedy Word Packing: We execute a while loop that goes through each word:

    • Within this loop, we keep adding words to a temporary list t until adding another word would exceed the maxWidth.
    • The cnt variable helps us keep track of the number of characters added so far (including spaces that will be necessary between words).

  3. Condition for Last Line or a Single Word:

    • If i is equal to n, indicating we’re processing the last line, or if the temporary list t has only one word, we know that we need to left-justify this line.
    • We create the line by joining the words in t with a single space and append the needed number of spaces to reach maxWidth.

  4. Justifying Lines with Multiple Words:

    • For all other lines, we calculate the total space_width required by subtracting the length of characters in words and the default single spaces that will be between words from maxWidth.
    • The divmod(space_width, len(t) - 1) expression gives us the number of spaces to add between each word (w) and how many extra spaces we need to distribute from left to right (m).

  5. Preparing the Formatted Line:

    • We prepare the justified line by iterating through the words in t. For each word except the last, we append the word and the calculated number of spaces to row.
    • When adding spaces, we also consider additional space if we have extra spaces left, which is decided by m.
    • The last word is appended to row without additional spaces because we want the line to be right-justified.

  6. Building the Final String: Once the justified line is prepared, we use ''.join(row) to create a string representation of the line, which is then appended to our ans list.

  7. Continuation: This process repeats until i reaches n, at which point all words have been packed into justified lines.

  8. Returning the Result: Finally, the ans list contains the fully justified text, which we return.

Through the use of elementary operations and control structures, the algorithm formats the input words array into a list of strings that meets the specifications of full justification according to the maxWidth provided.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's illustrate the solution approach with a small example.

Given:

  • An array of words: ["This", "is", "an", "example", "of", "text", "justification."]
  • maxWidth: 16

Initial Setup:

  • ans will hold our justified text lines.
  • i is the current index in the words array; n is the total number of words.

Walkthrough:

  1. Start with i = 0, n = 7. The first loop begins.
  2. Initialize t = ["This"] and cnt = 4 (since "This" consists of 4 characters).
  3. For i = 1 (word "is"), we check if cnt + 1 + len("is") <= maxWidth.
    • cnt + 1 + len("is") = 4 + 1 + 2 = 7, which is within maxWidth, so we add "is" to t and update cnt.
  4. Repeat step 3 for i = 2 and i = 3.
    • Now, t = ["This", "is", "an", "example"] and cnt = 15.
  5. For i = 4 (word "of"), cnt + 1 + len("of") > maxWidth. We cannot add "of" to the current line, so we format the words in t.

Formatting the Line: 6. Since there's more than one word, and it's not the last line, we distribute spaces. The space_width is maxWidth - cnt with one space already between words.

  • space_width = 16 - 15 = 1
  • There are 3 gaps between the 4 words in t. Using divmod(1, 3), we get w = 0 and m = 1. That means each gap gets 0 extra spaces, except for the leftmost gap which gets 1 extra space.
  1. Construct the justified line:
    • Start with "This" + 2 spaces (1 extra) + "is" + 1 space + "an" + 1 space + "example".
    • We get: "This is an example".
  2. Append this justified line to ans and start the next line with ["of"].

Continuing with the Word "of":

  1. Words for next line: t = ["of"], cnt = 2.
  2. Adding "text", "justification." works, but adding "justification." alone would exceed maxWidth. So, we add "text" and justify this line, which now contains 2 words.

Justifying the Last Line:

  1. For the last line, t = ["of", "text", "justification."], and we left-justify it.
    • Join: "of" + 1 space + "text" + 1 space + "justification." and fill the rest with spaces.
    • We get: "of text justification." (which has 4 extra spaces at the end to reach maxWidth).

Final Result:

  • The ans list after justifying both lines will look like this: 
    ["This  is an example", "of text justification."]
  • This ans reflects the justified text lines of maxWidth 16, conforming to the rules set out in the problem description.

The example demonstrates the algorithm's ability to iterate over an array of words and format them into justified text according to the specified width. Each loop handles the addition of words to a line and formats the line when it's complete or when no more words can be added without exceeding the maxWidth. The process repeats for all words, and the result is a list of strings that are fully justified.

Solution Implementation

1class Solution:
2    def fullJustify(self, words, maxWidth):
3        """
4        Given a list of words and a maximum width maxWidth, format the text 
5        such that each line has exactly maxWidth characters and is 
6        fully (left and right) justified. Words should be packed in a greedy approach.
7        """
8        justified_text = []  # Resultant list that will contain the fully justified text
9        current_index, total_words = 0, len(words)  # Initialize current index and get the total number of words
10      
11        # Iterate over words to construct each line
12        while current_index < total_words:
13            line_words = []  # Words to be included in the current line
14            count = len(words[current_index])  # Character count in the current line, starting with the first word
15            line_words.append(words[current_index])  # Add first word to the line
16            current_index += 1  # Move to the next word
17          
18            # Try to fit as many words as possible into the current line
19            while current_index < total_words and count + 1 + len(words[current_index]) <= maxWidth:
20                count += 1 + len(words[current_index])  # Update count including spaces between words
21                line_words.append(words[current_index])  # Add next word to the line
22                current_index += 1  # Move to the next word
23          
24            # Check if it's the last line or contains only one word
25            if current_index == total_words or len(line_words) == 1:
26                # Left-justify the line
27                line_left_justified = ' '.join(line_words)
28                # Calculate the remaining spaces on the right
29                spaces_on_right = ' ' * (maxWidth - len(line_left_justified))
30                # Add the left-justified and right-padded line to result
31                justified_text.append(line_left_justified + spaces_on_right)
32                continue
33          
34            # Not the last line or a single word, fully justify the line
35            total_spaces = maxWidth - (count - len(line_words) + 1)  # Calculate total spaces to fill
36            space_width, extra_spaces = divmod(total_spaces, len(line_words) - 1)  # Evenly distribute spaces
37          
38            constructed_line = []
39            # Distribute space_width (+1 for extra_spaces) among words
40            for index, word in enumerate(line_words[:-1]):
41                constructed_line.append(word)
42                # Append the appropriate number of spaces after the current word
43                constructed_line.append(' ' * (space_width + (1 if index < extra_spaces else 0)))
44              
45            constructed_line.append(line_words[-1])  # Append the last word without extra spaces
46            justified_text.append(''.join(constructed_line))  # Add the fully justified line to result
47          
48        return justified_text  # Return the justified text as a list of lines
49
1import java.util.ArrayList;
2import java.util.List;
3
4class Solution {
5    public List<String> fullJustify(String[] words, int maxWidth) {
6        List<String> justifiedText = new ArrayList<>();
7        int index = 0;
8        int numOfWords = words.length;
9
10        // Process all the words
11        while (index < numOfWords) {
12            List<String> currentLineWords = new ArrayList<>();
13            currentLineWords.add(words[index]);
14            int currentLineWidth = words[index].length();
15            index++;
16
17            // Try to fit as many words in the current line as possible
18            while (index < numOfWords && currentLineWidth + 1 + words[index].length() <= maxWidth) {
19                currentLineWidth += 1 + words[index].length();
20                currentLineWords.add(words[index++]);
21            }
22
23            // If it's the last line or the line contains only one word
24            if (index == numOfWords || currentLineWords.size() == 1) {
25                String leftAlignedText = String.join(" ", currentLineWords);
26
27                // Fill the remaining space on the right with spaces
28                String rightPadding = " ".repeat(maxWidth - leftAlignedText.length());
29                justifiedText.add(leftAlignedText + rightPadding);
30                continue;
31            }
32
33            // Distribute spaces evenly amongst words
34            int totalSpaces = maxWidth - (currentLineWidth - currentLineWords.size() + 1);
35            int spaceWidth = totalSpaces / (currentLineWords.size() - 1);
36            int extraSpacesCount = totalSpaces % (currentLineWords.size() - 1);
37
38            StringBuilder justifiedLine = new StringBuilder();
39            for (int wordIndex = 0; wordIndex < currentLineWords.size() - 1; wordIndex++) {
40                justifiedLine.append(currentLineWords.get(wordIndex));
41
42                // Append the base number of spaces
43                justifiedLine.append(" ".repeat(spaceWidth));
44
45                // Add an extra space to the leftmost gaps if needed
46                if (wordIndex < extraSpacesCount) {
47                    justifiedLine.append(" ");
48                }
49            }
50
51            // Append the last word in the line
52            justifiedLine.append(currentLineWords.get(currentLineWords.size() - 1));
53            justifiedText.add(justifiedLine.toString());
54        }
55
56        return justifiedText;
57    }
58}
59
1#include <vector>
2#include <string>
3
4using namespace std;
5
6class Solution {
7public:
8    // Formats an array of words such that each line has exactly maxWidth characters
9    vector<string> fullJustify(vector<string>& words, int maxWidth) {
10        vector<string> justifiedText; // The result containing all justified lines
11
12        // Iterate over all words
13        for (size_t i = 0, n = words.size(); i < n;) {
14            vector<string> currentLine = {words[i]}; // Words in the current line
15            int currentLineWidth = words[i].length(); // Current line width
16            ++i;
17          
18            // Greedily add words to the current line if they fit
19            while (i < n && currentLineWidth + 1 + words[i].length() <= maxWidth) {
20                currentLineWidth += 1 + words[i].length(); // Increment line width
21                currentLine.push_back(words[i++]); // Append word to the line
22            }
23          
24            // Handle the last line or a line with a single word
25            if (i == n || currentLine.size() == 1) {
26                string leftJustified = currentLine[0]; // Start with the first word
27              
28                // Append remaining words separated by a single space
29                for (size_t j = 1; j < currentLine.size(); ++j) {
30                    leftJustified += " " + currentLine[j];
31                }
32              
33                // Add trailing spaces to make the line of maxWidth length
34                string trailingSpaces = string(maxWidth - leftJustified.size(), ' ');
35                justifiedText.push_back(leftJustified + trailingSpaces); // Add line to the result
36                continue;
37            }
38          
39            // Calculate the total amount of space width to distribute among words
40            int totalSpaceWidth = maxWidth - (currentLineWidth - currentLine.size() + 1);
41            int spaceBetweenWords = totalSpaceWidth / (currentLine.size() - 1); // Base space width between words
42            int additionalSpaces = totalSpaceWidth % (currentLine.size() - 1); // Additional spaces to distribute
43          
44            string row; // The justified row as a string
45            for (size_t j = 0; j < currentLine.size() - 1; ++j) {
46                // Create a string of spaces for the current gap between words
47                row += currentLine[j] + string(spaceBetweenWords + (j < additionalSpaces ? 1 : 0), ' ');
48            }
49          
50            // Append the last word
51            row += currentLine.back();
52          
53            // Add the fully justified line to the result
54            justifiedText.push_back(row);
55        }
56      
57        return justifiedText;
58    }
59};
60
1function fullJustify(words: string[], maxWidth: number): string[] {
2    const justifiedText: string[] = []; // This will hold the result.
3
4    // Process each word in the input array.
5    for (let i = 0, totalWords = words.length; i < totalWords; ) {
6        const currentLine: string[] = [words[i]]; // Start with the current word.
7        let currentLineCharCount = words[i++].length; // Char count includes current word.
8      
9        // Keep adding words while they fit in maxWidth including spaces.
10        while (i < totalWords && currentLineCharCount + 1 + words[i].length <= maxWidth) {
11            currentLine.push(words[i]);
12            // Update char count, adding one for the new space before the word.
13            currentLineCharCount += 1 + words[i++].length;
14        }
15      
16        // If this is the last line or the line contains only one word.
17        if (i === totalWords || currentLine.length === 1) {
18            // Join all the words with a single space
19            const leftJustified = currentLine.join(' ');
20            // Create the right padding with spaces to fill up to maxWidth.
21            const rightPadding = ' '.repeat(maxWidth - leftJustified.length);
22            // Add the final line to the answer.
23            justifiedText.push(leftJustified + rightPadding);
24            continue;
25        }
26
27        // Calculate the width of spaces needed and the width to distribute evenly.
28        const totalSpaceWidth = maxWidth - (currentLineCharCount - currentLine.length + 1);
29        const evenSpaceWidth = Math.floor(totalSpaceWidth / (currentLine.length - 1));
30        // Determine if any extra spaces are needed.
31        const remainderSpaces = totalSpaceWidth % (currentLine.length - 1);
32        const currentRow: string[] = []; // This will hold the contents of the line.
33
34        // Distribute the spaces to the current row.
35        for (let j = 0; j < currentLine.length - 1; ++j) {
36            currentRow.push(currentLine[j]); // Add the word to the line.
37            // Add the appropriate number of spaces after the word.
38            currentRow.push(' '.repeat(evenSpaceWidth + (j < remainderSpaces ? 1 : 0)));
39        }
40      
41        // Add the last word without extra spaces after it.
42        currentRow.push(currentLine[currentLine.length - 1]);
43
44        // Join all elements of the row into a string and add to the result.
45        justifiedText.push(currentRow.join(''));
46    }
47
48    return justifiedText; // Return the fully justified text.
49}
50

Time and Space Complexity

Time Complexity

The time complexity of the fullJustify function can be analyzed as follows:

  • The main loop runs until every word is processed, which happens in O(n) time, where n is the total number of words.
  • Inside the loop, concatenating words together and calculating the length happens in O(k) time for each line, where k is the number of words on that line.
  • The while loop for adding words to the current line will execute in constant time considering the operation inside the loop runs in O(1) for each word.
  • The process of appending spaces in proportion for justified lines will take O(k) time because it goes through all but the last word in the current line.

The overall time complexity is a result of going through all the words and forming each line according to the rules, which results in O(n * k). However, since each word is considered only once when forming the lines and k is limited by the maxWidth, the time complexity can also be considered to be O(n).

Space Complexity

The space complexity can be analyzed as follows:

  • We use additional space to store the result list ans, which, in the worst-case scenario, will have the same number of strings as the number of words, giving us O(n).
  • Additional temporary space t and row are used to construct each line of the output. In the worst-case scenario, these will contain all words if all words can fit in a single line, resulting in O(n) space for that line.

However, since these temporary spaces are reused for each line and do not grow proportionally to the number of words n, the overall space complexity is O(n) for storing the result. The intermediate space used for assembling each line is not dependent on n but rather on maxWidth, which is a constant with respect to the input size.

Therefore, the final space complexity of the function is O(n).

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

What's the output of running the following function using input 56?

1KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13    def dfs(path, res):
14        if len(path) == len(digits):
15            res.append(''.join(path))
16            return
17
18        next_number = digits[len(path)]
19        for letter in KEYBOARD[next_number]:
20            path.append(letter)
21            dfs(path, res)
22            path.pop()
23
24    res = []
25    dfs([], res)
26    return res
27
1private static final Map<Character, char[]> KEYBOARD = Map.of(
2    '2', "abc".toCharArray(),
3    '3', "def".toCharArray(),
4    '4', "ghi".toCharArray(),
5    '5', "jkl".toCharArray(),
6    '6', "mno".toCharArray(),
7    '7', "pqrs".toCharArray(),
8    '8', "tuv".toCharArray(),
9    '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13    List<String> res = new ArrayList<>();
14    dfs(new StringBuilder(), res, digits.toCharArray());
15    return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19    if (path.length() == digits.length) {
20        res.add(path.toString());
21        return;
22    }
23    char next_digit = digits[path.length()];
24    for (char letter : KEYBOARD.get(next_digit)) {
25        path.append(letter);
26        dfs(path, res, digits);
27        path.deleteCharAt(path.length() - 1);
28    }
29}
30
1const KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13    let res = [];
14    dfs(digits, [], res);
15    return res;
16}
17
18function dfs(digits, path, res) {
19    if (path.length === digits.length) {
20        res.push(path.join(''));
21        return;
22    }
23    let next_number = digits.charAt(path.length);
24    for (let letter of KEYBOARD[next_number]) {
25        path.push(letter);
26        dfs(digits, path, res);
27        path.pop();
28    }
29}
30

Recommended Readings

LeetCode Patterns: The Smart, Data-Driven Way to Prepare for Tech Interviews

LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Runtime to Algo Cheat Sheet

Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More