There is char array of n length. Array can have elements only from of any order R, B, W.
You need to sort array so that order should R,B,W i.e. all R will come first followed by B and then W.
Constraints: Time complexity is O(n) and space complexity should be O(1) Assumption: You can assume one swap method is given with signature swap(int index1, int index2) that swaps number in unit time. method given to implement: public sort(char[]array);
Please leave your comments and suggestions that improves the logic above.
Constraints: Time complexity is O(n) and space complexity should be O(1) Assumption: You can assume one swap method is given with signature swap(int index1, int index2) that swaps number in unit time. method given to implement: public sort(char[]array);
public static void sort(char[] arr){
int rIndex = 0, wIndex = arr.length -1;
for (int i = 0 ; i <= wIndex; ){
if ( arr[i] == 'R' ){
swap(arr, i , rIndex ++ );
i ++ ;
} else if (arr[i] == 'W' ){
swap(arr, i , wIndex -- );
}else{
i ++;
}
}
}
//a dummy implementation just for testing sake
private static void swap(char[] arr, int index1, int index2){
char temp = arr[index1];
arr[index1] = arr[index2];
arr[index2] = temp;
}
No comments:
Post a Comment