Sentence Reverse
2 min readOct 23, 2021
Can you do this in place with O(1) cost for space?
Sentence Reverse
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.
Explain your solution and analyze its time and space complexities.
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
To do this in-place and with O(1) space complexity. We can
- reverse the whole array first
- reverse each of the words:
Time Complexity: traversing the array twice with a constant number of actions for each item is linear O(N).
Space Complexity: using iteration indices and one temp variable takes constant O(1) memory.
