message = 'cake pound steal' reverse_words!(message) puts message # Prints: 'steal pound cake'

We can do this in space. Remember, in place.

We can do this in time.

If you're swapping individual words one at a time, consider what happens when the words are different lengths. Isn't each swap time in the worst case?

It might be tempting to think about using the split method to separate our words, but we have to do this in place and splitting will create a new array of words.

Instead, can we just move characters around inside the message?

Well, we could swap the first character with the last character, then the second character with the second to last character, and so on, moving towards the middle. Can you implement this in code?

We're using a cute one-liner to do the swap. In other languages you might need to do the swap by hand, recording one of the values in a temp variable.

Alternatively, we could use Ruby's reverse! function. But let's keep this code—it might be helpful later on if we want to reverse smaller parts of the message.

Ok, looks good. Does this help us?

Can we use the same concept but apply it to words instead of characters?

Probably. We'll have to figure out a couple things:

1. How do we figure out where words begin and end? (No split allowed!)
2. Once we know the start and end indices of two words, how do we swap those two words?

We could attack either of those first, but I'm already seeing a potential problem in terms of runtime. Can you guess what it is?

What happens when you swap two words that aren't the same length?

Supposing we already knew the start and end indices of 'the' and 'landed', how long would it take to swap them?

time, where n is the total length of the message!

Why? Notice that in addition to moving 'the' to the back and moving 'landed' to the front, we have to "scoot over" everything in between, since 'landed' is longer than 'the'.

So what'll be the total time cost with this approach? Assume we'll be able to learn the start and end indices of all of our words in just one pass ( time).

total time. Why? In the worst case we have almost as many words as we have characters, and we're always swapping words of different lengths. For example:

We take time to swap the first and last words (we have to move all n characters):

Then for the second swap:

We have to move all n characters except the first and last words, and a couple spaces. So we move n-5 characters in total.

For the third swap, we have another 5 characters we don't have to move. So we move n-10 in total. We'll end up with a series like this:

This is a subsection of the common triangular series. We're just skipping 4 terms between each term!

So we have the sum of "every fifth number" from that triangular series. That means our sum will be about a fifth the sum of the original series! But in big O notation dividing by 5 is a constant, so we can throw it out. The original triangular series is , and so is our series with every fifth element!

Okay, so time. That's pretty bad. It's possible that's the best we can do...but maybe we can do better?

Let's try manipulating a sample input by hand.

And remember what we did for our character-level reversal...

Look what happens when we do a character-level reversal:

Notice anything?

What if we put it up against the desired output:

The character reversal reverses the words! It's a great first step. From there, we just have to "unscramble" each word.

More precisely, we just have to re-reverse each word!

def reverse_words!(message) # First we reverse all the characters in the entire message. reverse_characters!(message, 0, message.length - 1) # This gives us the right word order # but with each word backward. # Now we'll make the words forward again # by reversing each word's characters. # We hold the index of the *start* of the current word # as we look for the *end* of the current word. current_word_start_index = 0 (0..message.length).each do |i| # Skip unless we're at the end of the current word. next unless i == message.length || message[i] == ' ' reverse_characters!(message, current_word_start_index, i - 1) # If we haven't exhausted the string our # next word's start is one character ahead. current_word_start_index = i + 1 end end def reverse_characters!(message, left_index, right_index) # Walk towards the middle, from both sides. while left_index < right_index # Swap the left char and right char. message[left_index], message[right_index] = message[right_index], message[left_index] left_index += 1 right_index -= 1 end end