186. Reverse Words in a String II
Model: qwen3.5:9b
Topics: String
FAANG asked: 0
Acceptance rate: 46.0%
Problem Breakdown
We are given a character array s containing words separated by single spaces, with no leading or trailing spaces. The goal is to reverse the order of these words within the same array without allocating extra space proportional to the input size ( auxiliary space).
Key Constraints & Edge Cases:
- In-Place Modification: We must modify
sdirectly; creating a new string/list violates the constraint. - Input Format: Words are separated by exactly one space, with no leading/trailing spaces (per constraints), which simplifies parsing logic significantly compared to general whitespace handling problems.
- Single Word Case: If the array contains only one word or a single character, it should remain unchanged in structure but technically still satisfies “reversing words” if we consider that list as valid output.
Intuition
The naive approach is to split s into individual strings using .split(), reverse the resulting list of strings, and then join them back together with spaces. However, this violates the follow-up constraint because splitting creates new string objects (O(N) space), and joining requires a buffer for the result.
To achieve O(1) auxiliary space while modifying s in-place, we can leverage the properties of reversal operations:
- Reverse the entire array: This puts the words in reverse order relative to their original positions, but it also reverses the characters within each word (e.g., “the” becomes “eht”).
- Restore character orientation within words: Since we now have the correct sequence of words (just with internal letters flipped), we can iterate through
sand reverse every individual word back to its original reading order.
This two-step reversal strategy ensures that by the end, the words are in reversed positions relative to each other, but their characters are oriented correctly. This is a classic “reverse subarray” technique often used for palindrome checks or permutation problems where O(1) space is required.
Approach
We will use a pointer-based approach to identify word boundaries and perform reversals without creating new lists (to strictly adhere to the in-place constraint).
Step-by-Step Algorithm:
- Global Reversal: Reverse the entire list
susing manual swapping or built-in methods that modify the object directly. This flips the order of words but also flips characters inside them. - Iterate and Localize Words: Traverse the array to find indices where spaces occur (or end-of-array). These delimit individual word segments.
- Local Reversal: For each identified segment between two spaces, reverse that specific sub-segment of
sback to normal character order using manual swaps or slice assignment on a buffer if acceptable, but here we use pointer swapping for strict O(1) space adherence in explanation. - Update Pointers: Move the pointer past the current space and repeat until the end of the array is reached.
This ensures we only use a constant amount of extra space for pointers (i, j) and temporary variables used in swapping/reversing logic. No new data structures proportional to N are allocated (ignoring internal Python implementation details like slice buffers, which is standard interpretation for this constraint).
Complexity Analysis
- Time Complexity: O(N) where N is
s.length. We traverse the list once to reverse it globally, then iterate through each character again during the word reversal phase. Each element is touched at most twice (once in global pass, once in local passes). - Space Complexity: O(1). We only use a constant amount of extra space for pointers (
i,j) and temporary variables used in swapping/reversing logic. No new data structures proportional to N are allocated.
Solution
class Solution:
def reverseWords(self, s):
"""
Reverses the order of words in a character array in-place.
Args:
s (List[str]): List of characters representing the string.
Returns:
None (modifies list in place), but returns self for consistency with LeetCode style if needed,
though usually we just return nothing or modify and let caller check.
For this signature, I will assume standard function returning modified s is not strictly required by prompt
but good practice to show modification happened.
"""
n = len(s)
# Step 1: Reverse the entire array in-place (swaps word order + reverses chars inside words)
left, right = 0, n - 1
while left < right:
s[left], s[right] = s[right], s[left]
left += 1
right -= 1
# Step 2: Reverse each word individually in-place to fix character orientation within them
start = 0
for i in range(n):
if s[i] == ' ':
end = i - 1
# If we found a valid word segment, reverse it back to normal order manually
while start < end:
s[start], s[end] = s[end], s[start]
start += 1
end -= 1
# Move the start pointer past this space for next iteration
start = i + 1
# Handle the last word (since there are no trailing spaces per constraints,
# we must ensure the segment after the last space is reversed if it exists).
while start < n:
left_word, right_word = start, n - 1
while left_word < right_word:
s[left_word], s[right_word] = s[right_word], s[left_word]
left_word += 1
right_word -= 1
return s