Text Justification

Text Justification

What is this problem about?

The Text Justification coding problem is a notoriously difficult "Hard" problem that simulates how word processors align text. You are given an array of strings (words) and a maximum width L. You need to format the text such that each line has exactly L characters and is fully justified. This means you must distribute spaces as evenly as possible between words. The last line of text should be left-justified, and lines with only one word should also be left-justified.

Why is this asked in interviews?

This is one of the most common "Hard" problems, asked by dozens of companies including Apple, Uber, and Google. It is a pure simulation problem that tests your attention to detail, handling of edge cases, and string manipulation efficiency. There is no complex "trick" or data structure; it’s about writing clean, robust code that handles various spacing rules correctly. It evaluates whether you can translate a complex set of requirements into working software.

Algorithmic pattern used

The primary pattern is Simulation and String Manipulation. The process involves:

1. Grouping: Iterate through words and decide how many can fit on a single line (sum of word lengths + at least one space between them).
2. Spacing: For each line (except the last), calculate the total number of spaces needed. Distribute them evenly between word slots. If the spaces don't divide evenly, the slots on the left get more spaces than those on the right.
3. Left Justification: Handle the last line and single-word lines by placing one space between words and padding the rest with spaces on the right.

Example explanation

Words: ["This", "is", "an", "example"], Width: 16.

1. First line: "This", "is", "an". Total length = 4+2+2 = 8.
   • Spaces needed = 16 - 8 = 8.
   • Two slots (between "This"/"is" and "is"/"an").
   • 8 / 2 = 4 spaces per slot.
   • Line: "This is an"
2. Second line: "example". (Last line).
   • Left justified: "example " The result is perfectly aligned text blocks.

Common mistakes candidates make

The most frequent error is an "off-by-one" error when calculating how many words fit on a line. Another mistake is incorrect space distribution—forgetting that the leftmost slots should get the extra spaces when the total number of spaces isn't perfectly divisible by the number of slots. Handling the last line incorrectly (justifying it instead of left-aligning) is also a very common pitfall.

Interview preparation tip

To excel in the Text Justification interview question, practice breaking your code into small, manageable functions (e.g., getWordsForLine, justifyLine). This makes the logic much easier to track. Mastery of the String interview pattern and being comfortable with modular arithmetic (for space distribution) are essential for this high-pressure problem.