68. Text Justification

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.

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.

7. Construct the justified line:
   • Start with "This" + 2 spaces (1 extra) + "is" + 1 space + "an" + 1 space + "example".
   • We get: "This is an example".
8. 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:

  1["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

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.