Efficiently Reverse the Order of Words in a Character Array

Reversing the order of words in a character array is a classic problem that tests your understanding of algorithms and string manipulation. Whether you’re preparing for an interview or just sharpening your programming skills, mastering this challenge is quite rewarding. In this post, we’ll explore the problem in detail and break down an efficient solution in C/C++.

The Problem

Given an array of characters forming a sentence, we aim to reverse the order of the words without altering the individual letters in the words. For example, if you input:

"this is a string"

The output should be:

'string a is this'

The challenge specifies that this operation should be achieved in O(N) time and O(1) space, meaning you cannot use functions like split() or any data structures like stacks that manipulate extra space.

Analyzing the Problem

Time Complexity

The requirement for O(N) time complexity means that the algorithm must make a linear pass through the data. Hence, we should avoid nested loops that increase the time complexity.

Space Complexity

For O(1) space complexity, we can’t use any additional data structures for storage. This means operations must take place directly within the input array.

The Solution

Let’s break down the solution step by step. We will utilize a two-pass approach to solve this problem efficiently.

Step 1: Reverse the Entire String

The first step is to reverse the entire array. This transforms the original string into a string where all the characters are reversed. For our example "this is a string" after reversal:

"gnirts a si siht"

Step 2: Reverse Each Word

Now that we have reversed the entire string, we need to reverse each individual word to get them back in the correct order. Here’s how we can implement these steps in C/C++:

void swap(char* str, int i, int j) {
    char t = str[i];
    str[i] = str[j];
    str[j] = t;
}

void reverse_string(char* str, int length) {
    for(int i = 0; i < length / 2; i++) {
        swap(str, i, length - i - 1);
    }
}

void reverse_words(char* str) {
    int l = strlen(str);
    // Reverse the whole string
    reverse_string(str, strlen(str));
    int p = 0;
 
    // Find word boundaries and reverse word by word
    for(int i = 0; i < l; i++) {
        if(str[i] == ' ') {
            reverse_string(&str[p], i - p);  // Reverse the word identified
            p = i + 1;
        }
    }
    // Finally reverse the last word.
    reverse_string(&str[p], l - p);
}

Explanation of the Code

1. Swap Function: We use a helper function swap to interchange characters in the array.
2. Reverse String Function: This function reverses the characters of the string using the swap function.
3. Reverse Words Function: The core function first reverses the entire character array and then iterates through it to reverse individual words identified by spaces. The last word is handled after the loop ends.

Complexity Analysis

The reversing through the array twice makes the time complexity O(N):

• First pass: O(N) for reversing the entire string.
• Second pass: O(N) for reversing each word.

Thus, the final time complexity remains O(N). The space complexity is O(1) as no extra space is utilized other than variables for iteration.

Conclusion

Reversing the order of words in a character array efficiently requires a combination of string manipulations and an understanding of indexed access. The algorithm presented here demonstrates a clear approach that meets the O(N) time and O(1) space requirements while using C/C++. Practice this solution, and you’ll find it an excellent addition to your programming toolkit!