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.
Example:
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
I like this problem because it illustrates how even perfectly respectable solutions with a clear logic/action plan can still be optimized if we choose to take a look at the problem from a completely different angle. It also shows how useful a single helper function can be for implementing a concept (reverse the order of values in an array) at a macro and micro level (reverse all character to correct the order of the words, then reverse the characters of each word), and finally how a single concept can be used at the macro and micro level to provide an elegant and optimized solution.
Hope this helps out with the next algo. Good job and good luck!
