Solving: sentenceReverse

In this article, I’ll be breaking down the sentenceReverse problem in a few different ways in Javascript. Then I’ll walk through my process of solving the problem and discuss its BigO.

Let’s begin!

Question

You are given an array of characters arr that consists of sequences of characters separated by space characters. Each space-delimited sequence of characters defines a word.

Implement a function reverseWords that reverses the order of the words in the array in the most efficient manner.

input:  arr = [ 'p', 'e', 'r', 'f', 'e', 'c', 't', '  ',
'm', 'a', 'k', 'e', 's', ' ',
'p', 'r', 'a', 'c', 't', 'i', 'c', 'e' ]
output: [ 'p', 'r', 'a', 'c', 't', 'i', 'c', 'e', ' ',
'm', 'a', 'k', 'e', 's', ' ',
'p', 'e', 'r', 'f', 'e', 'c', 't' ]

Constraints:

  • [time limit] 5000ms
  • [input] array.character arr → 0 ≤ arr.length ≤ 100
  • [output] array.character

Let’s analyze the problem.

We’re given an array of characters where every character set that defines a word is placed in reverse order. So we know that the words are spelt correctly however their sequence is in reverse.

A logical approach would be to iterate through the array and stop at any point we hit an empty space character ‘ ‘. Once we hit an empty space, we know that we’ve found the end of a word and the beginning of the next. We can isolate the characters between the start index and first empty space character, then the characters between each empty space character, and then finally the characters between the last space character and the end of the index.

As we run through this process, we can take each word (contained within a temporary array) and push it to a stack, then in another for loop take the last word from the stack and add it to a results array, spreading each word as we add it to the results array.

Let’s look at the code.

Now this solution doesn’t seem too shabby. The time complexity is O(n) and the space complexity is the same.

Honestly, if you came up with this solution, good job. It’s not a bad solution by any means, but there is another way to approach it where we get to save a bit on the space complexity.

Let’s think about it this way. If we refrain from thinking about isolating words from the array and focus on the positioning of the character’s indices we could create a ‘mirror’ helper function that swaps the items between 2 given indices (reverses the characters between 2 given indices), that would allow us to both reverse the order of the characters as a whole from 0 — arr.length-1 as well as between every two empty space characters.

This way we can first reverse the order of the characters → effectively providing us the proper order for the words, which leaves us with words in the correct order but the spelling of each word in reverse. With this we can then iterate through the array and reverse every character set between the empty space characters to effectively ‘flip’ the word to the correct order.

We can do this with just the given array and a temp variable allowing for a reduced space complexity.

Let’s look at the code.

With the given solution, our time complexity remains at O(n) and our space complexity gets reduced to O(1).

As a broad overview what we’re doing here is reversing the order of the characters on the first pass (line 108). Then iterating through the array to isolate the start and end of each word by tracking the empty space character. When we find the value we run our mirrorReverse function passing in the start and end indices of the word to flip it into the correct order.

Conclusion

Hope this helps out with the next algo. Good job and good luck!