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
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:
- An array called lines which we will return at the end of our loop
- 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:
- A count of how many letters are in the word at that index
- 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++;
}
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:
- If we are on the last line, the line should be lest justified and no extra space should be inserted in between the words
- 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:
- An empty string to represent the line we will add to our lines array
- 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:
- 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)
- 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!
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.