Text Justification - Practice Coding Problems

Text Justification - Problem

Given an array of strings words and a width maxWidth, format the text such that each line has exactly maxWidth characters and is fully justified (both left and right aligned).

Requirements:

Pack words in a greedy approach: pack as many words as possible in each line
Pad extra spaces when necessary so each line has exactly maxWidth characters
Distribute extra spaces as evenly as possible between words
If spaces don't divide evenly, give more spaces to left slots
The last line should be left-justified with no extra spaces between words

Each word contains only non-space characters and has length ≤ maxWidth.

Input & Output

Example 1 — Basic Multiple Lines

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

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

💡 Note: Line 1: "This", "is", "an" fit with 8 chars + 8 spaces = 16. Line 2: "example", "of", "text" with 11 chars + 5 spaces = 16. Line 3: Last line left-justified.

Example 2 — Single Word Line

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

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

💡 Note: "acknowledgment" alone fills 14 chars, needs 2 trailing spaces. Last line "shall be" is left-justified with trailing spaces.

Example 3 — Minimum Width

$ Input: words = ["a", "b", "c", "d", "e"], maxWidth = 3

› Output: ["a b", "c d", "e "]

💡 Note: Each line fits 2 single-letter words with 1 space between (3 chars total). Last line "e" gets 2 trailing spaces.

Constraints

1 ≤ words.length ≤ 300
1 ≤ words[i].length ≤ 20
words[i] consists of only English letters and symbols
1 ≤ maxWidth ≤ 100
words[i].length ≤ maxWidth

Visualization

Tap to expand

Understanding the Visualization

Input

Array of words and maximum width constraint

Pack & Justify

Group words into lines, distribute spaces evenly

Output

Fully justified lines with exact maxWidth characters

Key Takeaway

🎯 Key Insight: Use greedy word packing and mathematical space distribution for efficient full justification

Asked in

G Google 42 a Amazon 35 f Facebook 28 M Microsoft 22

The key insight is to use greedy packing for words and mathematical calculation for space distribution. Pack as many words as possible per line, then use division and modulo operations to distribute spaces evenly. Best approach is Optimized Greedy. Time: O(n × w), Space: O(n × w)

Common Approaches

Approach	Time	Space	Notes
✓ Optimized Greedy	O(n × w)	O(n × w)	Efficiently calculate space distribution using math operations
Brute Force Simulation	O(n × w)	O(n × w)	Simulate the formatting process step by step

Optimized Greedy — Algorithm Steps

Step 1: For each line, pack maximum words that fit within maxWidth
Step 2: Use division for base spaces per gap, modulo for extra spaces
Step 3: Build justified line in single pass with calculated spacing

Visualization

Tap to expand

Step-by-Step Walkthrough

Pack & Count

Pack words greedily, count total spaces needed

Math Division

Use totalSpaces ÷ gaps and totalSpaces % gaps

Build Line

Construct justified line in single pass

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char** solution(char** words, int wordsSize, int maxWidth, int* returnSize) {
    char** result = (char**)malloc(wordsSize * sizeof(char*));
    *returnSize = 0;
    int i = 0;
    
    while (i < wordsSize) {
        // Pack words for current line
        char* lineWords[1000];
        int lineWordsSize = 0;
        lineWords[lineWordsSize++] = words[i];
        int lineLength = strlen(words[i]);
        i++;
        
        // Greedy packing: add words while they fit
        while (i < wordsSize && lineLength + 1 + strlen(words[i]) <= maxWidth) {
            lineWords[lineWordsSize++] = words[i];
            lineLength += 1 + strlen(words[i]);
            i++;
        }
        
        // Format line based on position and word count
        char* line = (char*)calloc(maxWidth + 1, sizeof(char));
        int pos = 0;
        
        if (i == wordsSize) { // Last line: left-justify
            for (int j = 0; j < lineWordsSize; j++) {
                strcpy(line + pos, lineWords[j]);
                pos += strlen(lineWords[j]);
                if (j < lineWordsSize - 1) {
                    line[pos++] = ' ';
                }
            }
            while (pos < maxWidth) {
                line[pos++] = ' ';
            }
        } else if (lineWordsSize == 1) { // Single word: left-align
            strcpy(line, lineWords[0]);
            pos = strlen(lineWords[0]);
            while (pos < maxWidth) {
                line[pos++] = ' ';
            }
        } else { // Multiple words: fully justify
            int totalChars = 0;
            for (int j = 0; j < lineWordsSize; j++) {
                totalChars += strlen(lineWords[j]);
            }
            int totalSpaces = maxWidth - totalChars;
            int gaps = lineWordsSize - 1;
            
            // Mathematical distribution
            int spacesPerGap = totalSpaces / gaps;
            int extraSpaces = totalSpaces % gaps;
            
            // Build justified line
            for (int j = 0; j < lineWordsSize; j++) {
                strcpy(line + pos, lineWords[j]);
                pos += strlen(lineWords[j]);
                if (j < gaps) { // Add spaces between words
                    for (int k = 0; k < spacesPerGap; k++) {
                        line[pos++] = ' ';
                    }
                    if (j < extraSpaces) { // Extra space to left gaps
                        line[pos++] = ' ';
                    }
                }
            }
        }
        
        line[maxWidth] = '\0';
        result[(*returnSize)++] = line;
    }
    
    return result;
}

int main() {
    char input[10000];
    fgets(input, sizeof(input), stdin);
    
    char* words[1000];
    int wordsSize = 0;
    
    // Parse words array manually
    char* token = strtok(input, "[],\"");
    while (token != NULL && wordsSize < 1000) {
        while (*token == ' ') token++;
        if (strlen(token) > 0) {
            words[wordsSize] = (char*)malloc(strlen(token) + 1);
            strcpy(words[wordsSize], token);
            wordsSize++;
        }
        token = strtok(NULL, "[],\"");
    }
    
    int maxWidth;
    scanf("%d", &maxWidth);
    
    int returnSize;
    char** result = solution(words, wordsSize, maxWidth, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("\"%s\"", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × w)

n words processed, w characters per line for string building

✓ Linear Growth

Space Complexity

O(n × w)

Result array stores all justified lines

⚡ Linearithmic Space

285.0K Views

Medium Frequency

~25 min Avg. Time

1.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Optimized Greedy — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler