Problem of The Day: Text Justification

Problem Statement

Intuition

The idea is to simulate the process of justifying text by greedily packing as many words as possible into one line. While adding words to a line, a whitespace is also added between words. Special attention is given to handling available spaces and addressing edge cases where additional whitespace may not be needed.

Approach

I first created a hash_map to store the length of each word for quick access. Then, I iterated through the words to form lines. For each word, I checked if adding it to the current line would exceed the maximum width. If it didn’t, I added the word to the current line and adjusted the available spaces. If adding the word would exceed the width, I started a new line.

After forming the lines, I went through each line and distributed the spaces between words to justify the line. I calculated the number of spaces needed and distributed them evenly. If there were remaining spaces, I added them to the leftmost words.

Complexity

• Time complexity: O(n), where n is the total number of characters in the words list.

• Space complexity: O(n), as I used a hash_map to store the lengths of the words and created lists to store the lines and final result.

Code

class Solution:
    def fullJustify(self, words: List[str], maxWidth: int) -> List[str]:
        hash_map = defaultdict(int)
        for word in words:
            hash_map[word] = len(word)
        
        res = []
        curr = []
        available_spaces = maxWidth
        for word in words:
            if available_spaces - hash_map[word] == 0:
                available_spaces -= hash_map[word]
            else:
                available_spaces -= (hash_map[word] + 1)

            if available_spaces >= 0:
                curr.append(word)
            else:
                if curr:
                    res.append(curr[:])
                available_spaces = maxWidth
                available_spaces -= (hash_map[word] + 1)
                curr = [word]
        
        if curr:
            res.append(curr[:])

        for i in range(len(res) - 1):
            arr = res[i]
            num_of_chars = 0
            num_of_words = len(arr)
            for s in arr:
                num_of_chars += hash_map[s]
            
            spaces = maxWidth - num_of_chars
            spaces_in_between = spaces // (num_of_words - 1) if num_of_words > 1 else 0
            spaces_left = spaces % (num_of_words - 1) if num_of_words > 1 else 0
            for j in range(spaces_left):
                arr[j] = ''.join(list(arr[j]) + [' '])
            
            if spaces_in_between > 0:
                delimiter = ' ' * spaces_in_between
                res[i] = str(delimiter.join(arr))
            else:
                res[i] = str(''.join(arr))
                if len(res[i]) < maxWidth:
                    res[i] += ' ' * (maxWidth - len(res[i]))

        
        if res:
            res[-1] = str(' '.join(res[-1]))
            if len(res[-1]) < maxWidth:
                res[-1] += ' ' * (maxWidth - len(res[-1]))

        return res

Editorial Solution - clean code

class Solution:
    def fullJustify(self, words: List[str], maxWidth: int) -> List[str]:
        def get_words(i):
            current_line = []
            curr_length = 0

            while i < len(words) and curr_length + len(words[i]) <= maxWidth:
                current_line.append(words[i])
                curr_length += len(words[i]) + 1
                i += 1

            return current_line
        
        def create_line(line, i):
            base_length = -1
            for word in line:
                base_length += len(word) + 1

            extra_spaces = maxWidth - base_length

            if len(line) == 1 or i == len(words):
                return " ".join(line) + " " * extra_spaces

            word_count = len(line) - 1
            spaces_per_word = extra_spaces // word_count
            needs_extra_space = extra_spaces % word_count

            for j in range(needs_extra_space):
                line[j] += " "

            for j in range(word_count):
                line[j] += " " * spaces_per_word

            return " ".join(line)

        ans = []
        i = 0

        while i < len(words):
            current_line = get_words(i)
            i += len(current_line)
            ans.append(create_line(current_line, i))

        return ans

• Time complexity: O(n * k) where n is length of words and k is the average length of a word
• Space complexity: O(m) where m is the maxWidth