Skip to main content
Talentd

Text Justification - Solution & Explanation

HardArrayStringSimulation16 min readAsked at: Amazon, Microsoft, Apple +41
Practice this problem

Problem Statement

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.

Example 3:

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

 

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

Approach Overview

Problem Overview: Given an array of words and a maximum line width, format the text so every line has exactly maxWidth characters. Words must stay in order, and extra spaces are distributed between words so the line becomes fully justified. The last line is left‑justified.

Approach 1: Greedy Line Construction (O(n) time, O(1) extra space)

The most practical solution processes words line by line using a greedy strategy. Iterate through the input and keep adding words to the current line while the total length plus required spaces does not exceed maxWidth. Once the next word would overflow the line, finalize the current line by distributing spaces between its words. Compute the total remaining spaces and spread them evenly across the gaps; the first gaps receive one extra space when the division is uneven. If the line has a single word, pad spaces to the right. For the final line, join words with a single space and pad the remaining characters at the end. This approach scans each word once and performs constant work per line, giving O(n) time where n is the number of words (or total characters processed). Only a few counters and temporary variables are used, so the extra space is O(1) excluding the output. The logic mainly involves sequential processing of arrays and strings, which fits well with problems under Array and String.

Approach 2: Dynamic Programming Line Breaking (O(n²) time, O(n²) space)

A more theoretical approach treats the task like classic text formatting. Use dynamic programming to evaluate every possible break point between words and choose the configuration that minimizes uneven spacing or raggedness. Precompute line lengths for word ranges, then define dp[i] as the minimum penalty for formatting words starting at index i. Try placing words i..j on the same line, calculate the cost for unused spaces, and combine it with dp[j+1]. This explores many candidate layouts and guarantees an optimal formatting score under the chosen penalty rule. However, evaluating all word pairs leads to O(n²) time and memory. It’s rarely required for this specific problem because the platform’s rules already define exact spacing behavior rather than minimizing raggedness.

Recommended for interviews: Interviewers expect the greedy line construction approach. It directly simulates the formatting process and demonstrates strong control over indexing, spacing math, and edge cases like single‑word lines or the final line. The DP approach shows deeper understanding of text layout algorithms but is usually unnecessary overhead for this problem. From a patterns perspective, the greedy method is a clean example of Simulation combined with string manipulation.

Approach 1: Greedy Line Construction

This approach involves iterating through the given words and greedily forming a line by adding as many words as possible without exceeding the maxWidth. When a line is completed, the algorithm distributes spaces evenly between words. If the number of spaces doesn’t divide evenly, more spaces are added to the left slots. The last line is treated differently by left-justifying the text.

The code defines a helper function, justify_line, to construct each justified line. While adding words to the current line, if adding another word exceeds maxWidth, the line is justified and appended to the result. The last line is treated separately for left-justification.

Code

PythonJavaJavaScript

Python

Java

JavaScript

Complexity

Time Complexity: O(n), where n is the total number of characters in all words.
Space Complexity: O(n), where n is the number of lines formed times maxWidth for the justified text.

Try this approach in the editor →

Approach 2: Dynamic Programming Approach

This method leverages dynamic programming to minimize a hypothetical cost function that combines badness or uneven space distribution along with total number of lines used, aiming to determine the optimal setup of words per line.

This C++ implementation uses a dynamic programming table, dp, to compute the minimum penalty of breaking words into lines. path is used to store optimal partitioning. The final step reconstructs justified text using information stored in path.

Code

C++C#

C++

C#

Complexity

Time Complexity: O(n^2), due to potential double iterations required for exploring word positions.
Space Complexity: O(n), since it uses extra space for storing dp and path arrays.

Try this approach in the editor →

Approach 3: Simulation

We can simulate the process according to the problem's requirements. Note that if it is the last line, or if there is only one word in the line, then we should align to the left. Otherwise, we should distribute the spaces evenly.

The time complexity is O(L), and the space complexity is O(L). Here, L is the sum of the lengths of all words.

Code

PythonJavaC++GoTypeScriptC#

Python

Java

C++

Go

TypeScript

C#

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Greedy Line Construction

Time Complexity: O(n), where n is the total number of characters in all words.
Space Complexity: O(n), where n is the number of lines formed times maxWidth for the justified text.

Dynamic Programming Approach

Time Complexity: O(n^2), due to potential double iterations required for exploring word positions.
Space Complexity: O(n), since it uses extra space for storing dp and path arrays.

Simulation—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Greedy Line ConstructionO(n)O(1)Standard interview solution. Efficient when words must be processed sequentially and spacing rules are fixed.
Dynamic Programming Line BreakingO(n²)O(n²)Useful when optimizing text layout with scoring functions such as minimizing raggedness or uneven spacing.

Video Solution

Text Justification - Leetcode 68 - Python • NeetCodeIO • 55,907 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Text Justification easy or hard?
Text Justification is classified as a Hard problem because the implementation has many edge cases. Correctly distributing spaces, handling single‑word lines, and formatting the final line requires careful logic even though the underlying idea is greedy.
Text Justification Python/Java solution
Python, Java, and JavaScript implementations typically follow the same greedy pattern: collect words for a line, compute the number of spaces needed, distribute them across gaps, and handle the last line separately with left justification.
How to solve Text Justification in O(n)?
Process the words sequentially and build one line at a time. Keep adding words until adding the next word would exceed maxWidth, then calculate how many spaces must be inserted between existing words. Distribute spaces evenly, with extra spaces placed in the leftmost gaps, and move to the next line.
What is the best approach for Text Justification?
Greedy line construction is the standard solution. Iterate through the words, pack as many as possible into the current line, then distribute the remaining spaces evenly between gaps. This runs in O(n) time and uses O(1) extra space, making it ideal for interview settings.
Is Text Justification asked at Google/Amazon/Meta?
Text formatting and string simulation problems like Text Justification have appeared in interviews at large companies including Google, Amazon, and Meta. The problem tests careful edge‑case handling, greedy reasoning, and string manipulation under constraints.
What data structure is used in Text Justification?
The main structures are arrays (or lists) to store words and strings to construct each line. The algorithm relies on counters, index pointers, and simple arithmetic for space distribution rather than complex data structures.
What is the time complexity of Text Justification?
The optimal greedy solution runs in O(n) time where n is the number of words or total characters processed. Each word is visited once while constructing lines and distributing spaces. Space complexity is O(1) excluding the output list of formatted lines.

Ready to solve this problem?

Practice Text Justification with our built-in code editor and test cases.

Practice on FleetCode
Previous

Divide a String Into Groups of Size k

Next

Rearrange Spaces Between Words