algorithm to reverse a string array in O(n/2) complexity

This problem is a subcase of ‘reversing words of a string‘.

There are many ways of reversing a string but best possible case should be considered keeping space and time complexities in mind. Complete source code can be downloaded from here.

Steps to solve this algorithm

• take two pointers, one pointing to the start of the array and another to the end of the array and swap the values at respective pointers.
• While traversing the array increment starting pointer and decrement ending pointer and continue swap the values at respective pointers
• continue this till we reach the middle of the array

by this time array will be reversed as

'welcome to coding algorithms' would become 'smhtirogla gnidoc ot emoclew'

Psuedocode for O(n/2) complexity:

    /**
	 * Algorithm to reverse a string
	 * @param arr
	 * @param wordIdx
	 * @param wordMidIdx
	 * @param wordLastIdx
	 * 
	 * @return reversed string array
	 */
	public char[] reverse(char[] arr, int wordIdx, int wordMidIdx,
	        int wordLastIdx) {
	    for (; wordIdx < wordMidIdx; wordIdx++) {
	        // swap first letter with the last letter in the
	        char tmp = arr[wordIdx];
	        arr[wordIdx] = arr[wordLastIdx - 1];
	        arr[wordLastIdx - 1] = tmp;
	        wordLastIdx--;
	    }
	    return arr;
	}

Output is: smhtirogla gnidoc ot emoclew

Space Complexity: No additional space is required as we are just swapping the letters within the same array
Time Complexity: Order of this algorithm: O(n/2), where is ‘n’ is the length of the input array

O(2n) Complexity
We can use character array stack also to do this operation but to build the stack we need O(n) time and to dump the stack which print the char array in reverse order will take O(n) order.

Complete source code can be downloaded from here.

Note: how to build stack can be looked at here