algorithm to reverse a string array in O(n/2) complexity
October 5, 2012 6 Comments
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
coding algorithms 
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.
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.
Pingback: algorithm to reverse words of a string | java tech stack
I don’t understand what O(n/2) is?
// 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;
}
Sachin, this works but not at the best time complexity.