Problem Description

You are given a character array s that contains words separated by single spaces. Your task is to reverse the order of the words in the array while keeping each word's internal character order intact.

A word is defined as a sequence of non-space characters. Words in the array are separated by exactly one space character.

The key constraint is that you must solve this problem in-place, meaning you cannot use any extra space for another array or data structure. You must modify the given array directly.

For example, if the input array represents "the sky is blue", after reversing the words, it should become "blue is sky the".

The solution uses a two-step approach:

1. First, reverse each individual word in the array. This is done by identifying word boundaries (spaces or array ends) and reversing the characters within each word.
2. Then, reverse the entire array. This final reversal puts the words in the opposite order while maintaining the correct character order within each word (since they were pre-reversed in step 1).

The algorithm uses two pointers i and j where i marks the start of a word and j scans through the array. When a space is encountered at position j, the word from position i to j-1 is reversed. After processing all words individually, the entire array is reversed from position 0 to n-1 to achieve the final result.

Intuition

When we need to reverse the order of words in-place, we face a challenge: we can't simply pick up words and move them around because that would require extra space. We need a clever trick.

Think about what happens when you reverse an entire string - everything gets flipped, including the individual words themselves. For example, if we have "the sky is blue" and reverse it entirely, we get "eulb si yks eht". Notice that the words are now in the correct order (blue, is, sky, the), but each word is backwards!

This observation leads us to a key insight: if we first reverse each word individually, and then reverse the entire array, we'll get the desired result.

Let's trace through this logic:

1. Original: "the sky is blue"
2. After reversing each word: "eht yks si eulb"
3. After reversing the entire array: "blue is sky the"

Why does this work? When we reverse the entire array in step 3, two things happen:

• The order of words gets reversed (which is what we want)
• Each word gets reversed again (which cancels out the first reversal from step 2)

It's like a double negative in mathematics - reversing a reversal brings us back to the original orientation. By pre-reversing each word, we ensure that when the final reversal happens, the words end up in their correct character order while their positions in the array are swapped.

This approach is elegant because it only uses the swap operation on the existing array elements, requiring no extra space beyond a few variables to track positions, thus satisfying the in-place requirement.

Solution Approach

The implementation uses a two-pointer technique to achieve the in-place reversal. Here's how the algorithm works step by step:

Helper Function - reverse(i, j): This function reverses a portion of the array from index i to index j. It uses the classic two-pointer swap approach:

• Start with pointers at positions i and j
• Swap elements at these positions: s[i], s[j] = s[j], s[i]
• Move pointers toward each other: i increases, j decreases
• Continue until pointers meet or cross

Main Algorithm:

1. Initialize variables: Set i = 0 to track the start of each word, and n = len(s) for the array length.

2. First pass - Reverse individual words:

   • Iterate through the array using index j and character c
   • When a space is encountered (c == " "):
     • Reverse the current word from position i to j-1
     • Update i = j + 1 to point to the start of the next word
   • When reaching the last character (j == n - 1):
     • Reverse the last word from position i to j
     • This handles the case where the array doesn't end with a space

3. Second pass - Reverse entire array:

   • Call reverse(0, n - 1) to reverse the complete array
   • This puts the words in the opposite order while restoring each word's correct character sequence

Example Walkthrough: For array ['t','h','e',' ','s','k','y']:

1. After reversing individual words: ['e','h','t',' ','y','k','s']
2. After reversing entire array: ['s','k','y',' ','t','h','e']

The time complexity is O(n) where n is the length of the array, as we traverse the array twice. The space complexity is O(1) since we only use a constant amount of extra variables, meeting the in-place requirement.

Example Walkthrough

Let's walk through a small example with the input array: ['c','a','t',' ','i','s']

Initial State:

['c','a','t',' ','i','s']
  0   1   2   3   4   5

Step 1: Reverse individual words

Set i = 0 (start of first word), scan with j:

• j = 0: 'c' is not a space, continue
• j = 1: 'a' is not a space, continue
• j = 2: 't' is not a space, continue
• j = 3: ' ' is a space! Reverse word from i=0 to j-1=2
  • Reverse ['c','a','t'] → ['t','a','c']
  • Array becomes: ['t','a','c',' ','i','s']
  • Set i = j + 1 = 4 (start of next word)

Continue scanning:

• j = 4: 'i' is not a space, continue
• j = 5: 's' is the last character (j == n-1), reverse word from i=4 to j=5
  • Reverse ['i','s'] → ['s','i']
  • Array becomes: ['t','a','c',' ','s','i']

After Step 1:

['t','a','c',' ','s','i']
  0   1   2   3   4   5

Step 2: Reverse the entire array

Reverse from index 0 to 5:

• Swap positions 0↔5: 't'↔'i' → ['i','a','c',' ','s','t']
• Swap positions 1↔4: 'a'↔'s' → ['i','s','c',' ','a','t']
• Swap positions 2↔3: 'c'↔' ' → ['i','s',' ','c','a','t']

Final Result:

['i','s',' ','c','a','t']

The original "cat is" has been transformed to "is cat" - words reversed while maintaining character order within each word!

Solution Implementation

Time and Space Complexity

Time Complexity: O(n), where n is the length of the character array s.

The algorithm consists of two main parts:

1. First loop through the array to reverse individual words: This iterates through each character exactly once (O(n)), and for each word encountered, it reverses that word. The reversal operation for each word takes time proportional to the word's length. Since each character is involved in exactly one reversal operation (as part of its word), the total work done across all word reversals is O(n).

2. Final reversal of the entire array: This performs n/2 swaps, which is O(n).

Therefore, the overall time complexity is O(n) + O(n) = O(n).

Space Complexity: O(1)

The algorithm only uses a constant amount of extra space:

• Variables i, j, n, and c for iteration and tracking positions
• The reverse helper function uses local variables i and j (shadows the outer scope)
• All operations are performed in-place on the input array

No additional data structures are created that scale with the input size, resulting in constant space complexity.

Common Pitfalls

1. Forgetting to Handle the Last Word

One of the most common mistakes is forgetting to reverse the last word in the array. Since the last word doesn't have a trailing space, the condition char == " " won't trigger for it.

Incorrect approach:

for current_index, char in enumerate(s):
    if char == " ":
        reverse(word_start, current_index - 1)
        word_start = current_index + 1
# Forgot to handle the last word!

Solution: Add an explicit check for the last character:

for current_index, char in enumerate(s):
    if char == " ":
        reverse(word_start, current_index - 1)
        word_start = current_index + 1
    elif current_index == array_length - 1:  # Don't forget this!
        reverse(word_start, current_index)

2. Incorrect Boundary Indices When Reversing

Another frequent error is using wrong indices when calling the reverse function, especially off-by-one errors.

Common mistakes:

• Using reverse(word_start, current_index) instead of reverse(word_start, current_index - 1) when a space is found
• Using reverse(word_start, current_index - 1) instead of reverse(word_start, current_index) for the last word

Solution: Remember that when you encounter a space at index j, the word ends at index j-1. But when processing the last character (which is part of a word), include it in the reversal.

3. Handling Edge Cases with Multiple Spaces

The problem states words are separated by exactly one space, but if the input could have multiple consecutive spaces or leading/trailing spaces, the current solution would fail.

Issue with multiple spaces:

# Input: ['a', ' ', ' ', 'b']
# Current algorithm would try to reverse empty "words" between spaces

Solution for robust handling:

def reverseWords(self, s: List[str]) -> None:
    def reverse(start: int, end: int) -> None:
        while start < end:
            s[start], s[end] = s[end], s[start]
            start += 1
            end -= 1
  
    word_start = 0
    in_word = False
  
    for i in range(len(s)):
        if s[i] != ' ':
            if not in_word:
                word_start = i
                in_word = True
        else:
            if in_word:
                reverse(word_start, i - 1)
                in_word = False
  
    # Handle last word if array doesn't end with space
    if in_word:
        reverse(word_start, len(s) - 1)
  
    reverse(0, len(s) - 1)

4. Modifying the Loop Variable Inside the Loop

Some might try to manually increment the index variable, which can lead to skipped characters or index out of bounds errors.

Incorrect approach:

j = 0
while j < len(s):
    if s[j] == " ":
        reverse(i, j - 1)
        i = j + 1
        j = j + 2  # Trying to skip the space - DON'T DO THIS
    j += 1

Solution: Use enumerate() or a simple for loop that handles iteration automatically, avoiding manual index manipulation.