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

Advertisements

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

  1. Raj says:

    String str = “welcome to javaj2ee forum”;
    //take two pointers, one pointing to the start of String and another to the end of the string
    // while traversing the String increment starting pointer and decrement ending pointer and continue this till we reach the middle of the string by this time String will be reversed
    int i = 0;
    int j = str.length();
    String tmp;

    for(i=0; i< j/2; i++) {
    // swap first letter with the last letter in the
    String tmp = str;
    str = str[j-1];
    str[j-1] = tmp;
    // move the pointer
    j–;
    }

    this logic is not working…how come are you modifying a string.

    • Niranjan says:

      thanks for pointing it out, I was dealing with string array(not string itself as String in java is immutable and we dont have array access with square brackets) I corrected it.

  2. Pingback: algorithm to reverse words of a string | java tech stack

  3. Sid says:

    I don’t understand what O(n/2) is?

  4. sachin says:

    // I guess this should work

    public static String reverseRecursively (String str){

    if (str.length() <= 1) {
    return str;
    }
    String afterRev = reverseRecursively(str.substring(1)) + str.charAt(0);
    return afterRev;

    }

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

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

Diabolical or Smart

Nitwit, Blubber, Oddment, Tweak !!

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