Coding Challenge: Full Justify (LeetCode Hard)

Lately I've been retraining my brain with some algorithmic coding challenges on LeetCode. After years of experience as a working Principal Engineer, you would think that this kind of thing comes easy, but software development in the modern age rarely has you reinvent the wheel, and most established algorithms are well documented. Challenging your brain in this way to implement an algorithm or process from just its definition or description is good practice to keep you sharp.

I came across an interesting hard level question that was asking to implement a Text Justification algorithm given an array of words, and a max line length integer.

The exact wording of the question looks like this:

---

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.

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                  "
]

---

Diving in, I knew we had to consider every word, and never had a reason to revisit a previous line with new information, so setting up a loop over every word, with some instance variables to store current state of lines and output seemed to be a good first approach at a algorithmic framework. Determining what to do with each word also seemed pretty straight forward. We seem to have 3 options when considering a new word:

1. We have perfect spacing on the line with the word included
2. We have enough room to add the word and potentially more
3. We don't have enough room to add the word at all

Setting up some code from this framework, I came up with the following solution:

# @param {String[]} words
# @param {Integer} max_width
# @return {String[]}
def full_justify(words, max_width)
    lines = []
    line_words = []

    while words.any?
        word = words.shift # consider a new word from fron of array

        current_line_word_length = line_words.join.length # length of words without spaces
        # determine length of words with new word, and single spaces between, perfect condition
        normal_spacing_length = current_line_word_length + line_words.count + word.length

        if normal_spacing_length == max_width
            # have enough space for perfect spacing with new word, join line_words and word with one space padding
            line_words << word
            lines << line_words.join(' ')
            line_words = []

        elsif normal_spacing_length < max_width
            # have enough space to consider next word
            line_words << word

        else # normal_spacing_length > max_width
            # No space for new word, so put it back in the list
            words.unshift(word)
            # join line_words with variable padding between, determine how much is needed

            missing_space = max_width - current_line_word_length
            if line_words.length == 1
                lines << line_words[0] + (' ' * missing_space) # Add right padding

            else
                while missing_space > 0
                    last_word = line_words.pop # remove last word
                    line_words.map! do |word|
                        if missing_space == 0
                            word
                        else
                            missing_space -= 1
                            word + " "
                        end
                    end
                    line_words << last_word # add last word back
                end
                # The line_words already have padded spaces added so just join them
                lines << line_words.join
            end

            line_words = []
        end
    end

    # Handle the last line if any line words are left.
    if line_words.any?
        last_line = line_words.join(' ') # Normal spacing
        missing_space = max_width - last_line.length
        last_line = last_line + (' ' * missing_space) # Add right padding
        lines << last_line
    end

    # Finally, return the lines
    lines
end

Let's go over this line-by-line.

• Lines 5-6: Set up some variables to hold the output (lines), and the words we are considering for any given line line_words.
• Lines 8-9: Loop over every single word in the input array words, removing the first one from the list for consideration.
• Line 11: Calculate how many characters the current set of line_words has.
• Line 13: Calculate how many characters the current set of line_words has, with the new words, and with single spacing.
• Lines 15-19: If a max_width length line is possible with perfect single spaces, join it! Then add it to the output lines and clear the line_words array for the next word/line.
• Lines 21-23: If a perfectly spaced line is less than max_width, it is possible we can consider another word to add. So put the current word in the line_words array, and move on to the next word.
• Lines 25-26: We enter this condition when there is not enough space to include the current word on the current line, so put it back into the words list before we handle the justification.
• Line 30: Determine how much whitespace we need to add to the line to make it max_width long.
• Lines 31-32: If there is only 1 word on this line, we just need to right-pad the word.
• Lines 34-35: Otherwise, while we still have missing space to add to the line,
• Line 36: Pull out the last word, as that will never get additional padding added.
• Lines 37-44: Transform the other words by appending a single whitespace to the right side, unless we don't need any more space added.
• Line 45: Add the non-padded last word back into line_words.
• Line 48: Since all of the line_words already have padding added, just join them all.
• Line 51: Reset the line_words array for the next line!
• Lines 56-61: Handle the very last line by joining any remaining words directly, and padding out the right side, as per the instructions.
• Line 64: We can simply return the output lines array!

Submitting this code to LeetCode passess all of their tests, and has the following stats:

Runtime: 52 ms, Beats 84.62% of users with Ruby.
Memory Usage: 211.30 MB, Beats 94.23% of users with Ruby.

Onward to the next problem!

Was this page helpful for you? Buy me a slice of 🍕 to say thanks!