186. Reverse Words in a String II

Problem Description

The problem provided is one of reversing the order of words within a character array s. Each word within the array is defined as a contiguous sequence of characters without spaces, and each word is separated by a single space. The key constraint is that the reversal of the word order must be done in-place, which means the solution cannot use additional memory to store a new array or other data structure.

Intuition

To solve this problem, the intuition is to think about the desired end state: we want the words in reverse order, but each word itself should remain in its original order. An efficient way to achieve this is by applying a two-step process:

Reverse each individual word.
Reverse the entire character array.

Step 1 ensures that when we perform Step 2, each word will appear in the correct order since they were individually reversed in the first step.

Implementing Step 1 involves iterating over the character array and reversing characters within each word boundary, defined by spaces. When a space is encountered, it signals the end of the current word, prompting a reversal of all characters from the start of that word to the character immediately before the space.

For the last word, since there’s no trailing space, a check is needed to trigger the reversal when reaching the end of the array.

After all words are individually reversed, Step 2 simply reverses the entire array from start to end. As each word is already correctly ordered internally, this step places the words in the reverse order.

The solution employs helper method reverse that takes a subsection of the array s between indices i and j, swapping the elements at i and j, then moving i forward and j backward, repeating this process until the subsection is completely reversed.

Learn more about Two Pointers patterns.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

Solution Approach

The solution approach follows a systematic process:

Initialize Pointers: We start by initializing two pointers, i and j, along with n that holds the length of the character array s. Here, i will serve as the start index of a word, and j will iterate through the array to find the end of a word.
Iterate Through s: We begin iterating over the array with j. The loop continues until j has reached the end of the array.
Reverse Individual Words: As j encounters a space, we realize that it marks the end of a word. At this point, we call the reverse helper function with the current start index i and the end index j - 1. After the reversal of the current word, we move i past the space to the beginning of the next word (i = j + 1).
- The reverse helper function takes two indices and reverses the subsection of s between these indices. It does this by swapping the elements at i and j, then moves i forward and j backward, repeating the process until i meets or passes j.
Edge Case for Last Word: Since there’s no trailing space after the last word, the condition j == n - 1 checks if j has reached the end of the array, signaling the end of the last word, and a reversal is performed for this last word segment.
Reverse Entire Array: Once all words are reversed, the final step is to reverse the entire character array. This is again done by calling the reverse function with the indices 0 and n - 1.

This algorithm does not use any extra space and operates entirely in-place, modifying the original array to achieve the desired result. The data structure used is simply the input array, and the algorithm leverages the two-pointer technique to identify and reverse each word, followed by the reversal of the entire array. The reversing of elements within the array is based on the classic pattern of using a temporary variable to swap two elements, a fundamental operation in many sorting and reversing algorithms.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's use a simple example to illustrate the solution approach. Suppose we have an array s representing the sentence: "the sky is blue"

The initial state of the array s:

['t', 'h', 'e', ' ', 's', 'k', 'y', ' ', 'i', 's', ' ', 'b', 'l', 'u', 'e']

Now, let's walk through the process:

Initialize Pointers:
- We initialize a pointer i at 0 and n as the length of the array s, which is 15.
Iterate Through s:
- We start iterating forward through the array with a pointer j. Initially, j is also at 0.
Reverse Individual Words:
- As j moves forward, it encounters the first space at j = 3. This means the first word "the" (from i = 0 to j - 1 = 2) needs to be reversed. Using the reverse helper function, the array now looks like this:
```
['e', 'h', 't', ' ', 's', 'k', 'y', ' ', 'i', 's', ' ', 'b', 'l', 'u', 'e']
```
- i is then updated to j + 1, which is 4, the start of the next word "sky".

Continue Iterating and Reversing Words:

This process is repeated for the remaining words. After reversing "sky" and "is", the array looks like:

['e', 'h', 't', ' ', 'y', 'k', 's', ' ', 's', 'i', ' ', 'b', 'l', 'u', 'e']

When j reaches the end of the array after "blue", j = n - 1, it triggers the last reversal from i = 11 to j = 14, resulting in:

['e', 'h', 't', ' ', 'y', 'k', 's', ' ', 's', 'i', ' ', 'e', 'u', 'l', 'b']

Reverse Entire Array:

Finally, we reverse the entire array from 0 to n - 1. After this, the array s looks like:

['b', 'l', 'u', 'e', ' ', 'i', 's', ' ', 's', 'k', 'y', ' ', 't', 'h', 'e']

Now, the character array s correctly represents the sentence "blue is sky the", with the words in reverse order, and each word internally in the correct order. All this has been achieved in-place, without using any additional memory for a new array or data structure.

Solution Implementation

1class Solution:
2    def reverseWords(self, s: List[str]) -> None:
3        """
4        This method reverses the words in the input list in-place.
5      
6        Parameters:
7        s (List[str]): A list of characters representing a string with words
8                        separated by single spaces.
9        """
10
11        def reverse_partial(section: List[str], start: int, end: int) -> None:
12            """
13            Helper function that reverses a substring of the list in-place.
14
15            Parameters:
16            section (List[str]): The list of characters which substring to be reversed
17            start (int): The starting index of the substring
18            end (int): The ending index of the substring
19            """
20            while start < end:
21                section[start], section[end] = section[end], section[start]
22                start += 1
23                end -= 1
24
25        length = len(s)
26        # Initialize the starting index of the current word
27        word_start = 0
28        # Traverse the list of characters
29        for idx in range(length):
30            # If a space is found, reverse the word before the space
31            if s[idx] == ' ':
32                reverse_partial(s, word_start, idx - 1)
33                # Update the starting index for the next word
34                word_start = idx + 1
35            # If end of the list is reached, reverse the last word
36            elif idx == length - 1:
37                reverse_partial(s, word_start, idx)
38      
39        # Reverse the whole modified list to get words in correct order
40        reverse_partial(s, 0, length - 1)
41

1class Solution {
2  
3    // Function to reverse words in place within a character array
4    public void reverseWords(char[] str) {
5        int n = str.length;
6
7        // First, reverse each word in the array
8        for (int start = 0, end = 0; end < n; ++end) {
9            if (str[end] == ' ') {
10                // When we find a space, reverse the previous word
11                reverse(str, start, end - 1);
12                // Move to the start of the next word
13                start = end + 1;
14            } else if (end == n - 1) {
15                // If this is the end of the last word, reverse it
16                reverse(str, start, end);
17            }
18        }
19
20        // After all words are reversed, reverse the entire array to put words into the correct order
21        reverse(str, 0, n - 1);
22    }
23
24    // Helper function to reverse a section of the character array from index i to j
25    private void reverse(char[] str, int i, int j) {
26        // Swap characters from the starting and ending indices until they meet in the middle
27        while (i < j) {
28            char temp = str[i];
29            str[i] = str[j];
30            str[j] = temp;
31            i++;
32            j--;
33        }
34    }
35}
36

1#include <vector>
2#include <algorithm>  // for std::swap
3
4class Solution {
5public:
6    // Function to reverse words in a given character array.
7    void reverseWords(std::vector<char>& s) {
8        int n = s.size(); // Get the size of the character array
9        // Iterate through the array to find words and reverse them
10        for (int start = 0, end = 0; end < n; ++end) {
11            if (s[end] == ' ') {
12                // A word is found, reverse it
13                reverse(s, start, end - 1);
14                // Update 'start' to the next word's starting index
15                start = end + 1;
16            } else if (end == n - 1) {
17                // Last word is found, reverse it
18                reverse(s, start, end);
19            }
20        }
21        // After reversing all the words individually, reverse the entire array to get the final result
22        reverse(s, 0, n - 1);
23    }
24
25    // Helper function to reverse characters in the array between indices i and j.
26    void reverse(std::vector<char>& s, int i, int j) {
27        // Swap characters from both ends moving towards the center
28        while (i < j) {
29            std::swap(s[i], s[j]);
30            ++i;
31            --j;
32        }
33    }
34};
35

1// Function to reverse a portion of the array between indices start and end.
2function reverse(arr: string[], start: number, end: number): void {
3    while (start < end) {
4        // Swap elements at indices start and end.
5        let temp = arr[start];
6        arr[start] = arr[end];
7        arr[end] = temp;
8        start++;
9        end--;
10    }
11}
12
13// Function to reverse the words in a given character array.
14function reverseWords(s: string[]): void {
15    const n: number = s.length; // Get the size of the character array
16
17    // Iterate through the array to find words and reverse them.
18    let start: number = 0;
19    for (let end = 0; end < n; end++) {
20        // Check if the current character is a space or if we're at the end of the array.
21        if (s[end] === ' ' || end === n - 1) {
22            // Calculate the position to end the reversal (consider the last word case).
23            let reverseEnd = (s[end] === ' ') ? end - 1 : end;
24            // Reverse the current word.
25            reverse(s, start, reverseEnd);
26            // Update 'start' to the next word's starting index.
27            start = end + 1;
28        }
29    }
30
31    // After reversing all the words individually, reverse the entire array to get the final result.
32    reverse(s, 0, n - 1);
33}
34

Time and Space Complexity

The given Python code is designed to reverse the words in a string in-place. Here's the analysis of its complexity:

Time Complexity:

To analyze the time complexity, we observe each part of the code:

The reverse function is a part of the total operation, which is called for each word and once for the entire string. It takes O(k) time for each word, where k is the length of that word, and O(n) for the entire string, where n is the total length of the input string.
The while loop runs through each character in the string, which takes O(n) time.

Combining these, each character is involved in two operations: once in the main loop, and once when its word is reversed. Including the final reversal of the entire string, we have:

For each word of length k: O(k)
For the entire string: O(n)

Since the sum of the lengths k of all words is n, we can order these operations as O(n) + O(n) = O(2n). However, in Big O notation, we would drop the constant to simplify the expression to O(n).

Space Complexity:

No additional space is needed except for a few variables (i, j, n), since the reversal is done in place.
The reverse function does not use any additional space and is performed in place.

Hence, the space complexity is O(1), which indicates constant space usage.

In conclusion, the code has a time complexity of O(n) and a space complexity of O(1).

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

You are given an array of intervals where intervals[i] = [start_i, end_i] represent the start and end of the ith interval. You need to merge all overlapping intervals and return an array of the non-overlapping intervals that cover all the intervals in the input.

Sort the intervals by their start time, then iterate through the sorted intervals, merging any overlapping intervals.

Brute force through all interval combinations and find the answer with the least total intervals.

Iterate through the intervals in their original order, merging any overlapping intervals.

Use a priority queue to keep track of the intervals, merging any overlapping intervals.

I don't know