arrow_backBack to blog

Solving The Problem: Text Justification

Solving The Problem: Text Justification

Solving The Problem: Text Justification

Here's a medium to hard level question from CodeFights that I've actually encountered in interviews. This tutorial should help newer programmers solidify their understanding of an approach to this problem in JavaScript.

The time complexity for this solution would be O(n), as we are looping through our array of words at a constant rate.

Unlike other questions, this question really challenges your ability to think through a problem and implement a solution rather than knowing a random arbitrary algorithm.

It took me quite a while to figure it out initially, but I'm hoping this explanation will make someone else's life easier.

The question is as follows:

Given an array of words and a length L, format the text such that each line has exactly L characters and is fully (left and right) justified. Words should be packed in a greedy approach; that is, pack as many words as it is possible in each line. Add extra spaces when necessary so that each line has exactly L characters.

Extra spaces between words should be distributed as evenly as possible. If the number of spaces on a line do 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 and lines with one word only, it should be left justified and no extra space is inserted between words.

Example

For the list of words ['This', 'is', 'an', 'example', 'of', 'text', 'justification.'] and L = 16 the answer is:

[
    'This    is    an',
    'example  of text',
    'justification.  '
]

Structure the function however you want, but if you want a base function in JavaScript, it would look like:

  function textJustification(words, L) {
  
  }
  • [input] array.string words

    an array of words, each word is guaranteed not to exceed L in length.

  • [input] integer L

    length of lines

  • [output] array.string

    formatted text as an array of lines

STEP 1: Thinking through the solution

what the... This was me when I was told the question.

Before we even START to think about efficient solutions, we should think about the problem logically.

The whole problem lies behind going through each line and making sure the number of characters in each line doesn't go over the length.

Once we get in a line, we will just need to try and add spaces as evenly as possible, unless we're in the last line.

STEP 2: Define our variables and find the words for each line

Like the step says, we will start by defining our outer most variables using the ES6 "let" keyword:

  1. An array called lines which we will return at the end of our loop
  2. An index to represent our position in the array of words.
// variables
let lines = [];
let index = 0;

Now that we have defined our variables, we will need to start looking through our list of words.

// outer loop to loop through wwords
while (index < words.length) {
  
}

Let's define some variables:

  1. A count of how many letters are in the word at that index
  2. The position of the next word.
let count = words[index].length;
let last = index + 1;

Next, we need to go through all of the words and find out where the number of characters is greater than our length L. If it's not greater than L, then we continue to go on to the next word.

The code for that will look something like this:

while(last < words.length) {

  // we've reached the limit for chars in a line.
  if(words[last].length + count + 1 > L) break;
  
  // otherwise increase the amount of chars, and go   // to the next word
  count += words[last].length + 1;
  last++;
}

Phew.

The hardest part is over, we now have the words for each line. The last thing we need to do is add the spaces in between the words.

WE GOT THIS.™

STEP 3: Adding spaces in between the words in the line to match length L

Now that we have the words in a line, the last thing we need to do is obviously add the spaces in to the line. However there's two situations that we need to remember that were stated in the original problem:

  1. If we are on the last line, the line should be lest justified and no extra space should be inserted in between the words
  2. If the number of spaces on a line do not divide evenly, the empty slots on the left will be assigned more than the slots on the right.

Let's go and define some more variables:

  1. An empty string to represent the line we will add to our lines array
  2. The difference or the number of words between the first and last word in the line
  let line = "";
  let difference = last - index - 1; 

Like the question said, if we're on the last line or if there is only one word in the line we will left justify.

  if (last === words.length || difference === 0) {
    // left justify code goes here...
  }

First, we will loop through the words in our line using our index and last variables and add a space after each word like normal.

  for(let i = index; i < last; i++) {
    line += words[i] + " ";
  }

This will add an extra space at the end, so we will remove it using JavaScript's substr function. Now we just have to add spaces to fill in the rest of the line with spaces:

  line = line.substr(0, line.length - 1);
  for(let i = line.length; i < L; i++) {
    line += " ";
  }

Now that we've handled the last line, we need to handle the rest of the lines which will be middle justified.

In our else statement, let's define two more variables:

  1. A variable to calculate the number of spaces already in the line (max characters minus number of chars in the words, all divided by the difference)
  2. A variable to calculate the remaining spaces to add (using the modulo operator it would be (L - count) % difference)
  let spaces = (L - count) / difference;
  let remainder = (L - count) % difference;

Using our index and last variables again, we can loop through the words for the line and start adding them in.

As long as we're not at the last word, we can calculate the max amount of spaces we can have based on the remainder, and add those spaces into the line:

  else {
    for (let i = index; i < last; i++) {
      line += words[i];
    
      if( i < last - 1) {
        let limit = spaces + ((i - index) < remainder ? 1 : 0)
        
        for (let j = 0; j <= limit; j++) {
          line += " ";
        }
      }
    }
  }

STEP 4: Adding our line to the list

The last thing we need to do in our loop is:

  • Add the line to our list, and set our new index to the position of the last word in our previous line:
  lines.push(line);
  index = last;

Our lines array now has our properly formatted strings, so we can go ahead and return our newly formed array of text justified strings:

  return lines;

We're done with the solution!

HELL YEAH

The whole solution together should be as follows if you were following along:

  function textJustification(words, L) {
    let lines = [], index = 0;
    
    while(index < words.length) {
        let count = words[index].length;
        let last = index + 1;
        
        while(last < words.length) {
            if (words[last].length + count + 1 > L) break;
            count += words[last].length + 1;
            last++;
        }
        
        let line = "";
        let difference = last - index - 1;
        
        // if we're on the last line or the number of words in the line is 
        // 1, we left justify
        if (last === words.length || difference === 0) {
            for (let i = index; i < last; i++) {
                line += words[i] + " ";
            }
            
            line = line.substr(0, line.length - 1);
            for (let i = line.length; i < L; i++) {
                line += " ";
            }
        } else {
            // now we need to middle justify, which is putting equal amount 
            // of spaces between words
            let spaces = (L - count) / difference;
            let remainder = (L - count) % difference;
            
            for (let i = index; i < last; i++) {
                line += words[i];
                
                if( i < last - 1) {
                    let limit = spaces + ((i - index) < remainder ? 1 : 0)
                    for (let j = 0; j <= limit; j++) {
                        line += " ";
                    }
                }
            }
        }
        lines.push(line);
        index = last;
    }
    return lines
}

That's the slightly complicated text justification problem. If you liked this post or found the solution helpful, leave a comment below!

You can follow me on twitter for more posts and updates related to my blog and YouTube channel.

Never Give Up: Forging Your Own Path

Choosing a path after graduation can be really difficult. The options are seemingly limitless, but you can only choose one.

By Malik Browne ·

Contentful and Netlify: The Dynamic Duo of Static Site Management

Thinking about a solution for a simple front-end blog? Check out this post about how Contentful and Netlify tie together to create an awesome developer experience for a static site.

By Malik Browne ·

© Malik Browne 2018. All rights reserved.