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

Mawazo

Mostly technology with occasional sprinkling of other random thoughts

amintabar

Amir Amintabar's personal page

101 Books

Reading my way through Time Magazine's 100 Greatest Novels since 1923 (plus Ulysses)

Seek, Plunnge and more...

My words, my world...

ARRM Foundation

Do not wait for leaders; do it alone, person to person - Mother Teresa

Executive Management

An unexamined life is not worth living – Socrates

javaproffesionals

A topnotch WordPress.com site

thehandwritinganalyst

Just another WordPress.com site

coding algorithms

"An approximate answer to the right problem is worth a good deal more than an exact answer to an approximate problem." -- John Tukey