Re: [algogeeks] [amazon]: dutch national flag algorithm
Let array contains 3 types of elements R,G,B. Now, if we place all the R elements from the left and B elements from the right then G elements will automatically be between the two. Thus we only have to keep indexes for the R and B elements inserted till now and update their positions accordingly to the current array element we are accessing. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] [amazon]: dutch national flag algorithm
it can be solved in o(n) , keep one pointer at start and another pointer at the last , traverse the string if u get R swap it at the start position and then increament it , if u get B swap it with last pointer pointing to last position .and then decrement it . in this way all things will come in place . On Sat, Jun 9, 2012 at 11:36 PM, Navin Kumar algorithm.i...@gmail.comwrote: Given a character array as input. Array contains only three types of characters 'R', 'G' and 'B'. Sort the array such that all 'R's comes before 'G's and all 'G's comes before 'B's. Constraint :- No extra space allowed(except O(1) space like variables) and minimize the time complexity. You can only traverse the array once. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/54GHWSwHHw8J. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Cheers, Nishant Pandey |Specialist Tools Development | npan...@google.comgvib...@google.com | +91-9911258345 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
RE: [algogeeks] [amazon]: dutch national flag algorithm
Just use the counting sort and keep the counts in variables int R, int G, int B. Traverse the array and increment each respective variable (R or G or B) as soon as you encounter upon it. Once finished, you will have all the counts of frequencies stored in those three variables. Now, start traversing the array of counts (R, G, B) and fill the original array with data. Space O(1), time O(N) Rgds, Ashot Madatyan From: algogeeks@googlegroups.com [mailto:algogeeks@googlegroups.com] On Behalf Of Nishant Pandey Sent: Saturday, June 09, 2012 10:16 PM To: algogeeks@googlegroups.com Subject: Re: [algogeeks] [amazon]: dutch national flag algorithm it can be solved in o(n) , keep one pointer at start and another pointer at the last , traverse the string if u get R swap it at the start position and then increament it , if u get B swap it with last pointer pointing to last position .and then decrement it . in this way all things will come in place . On Sat, Jun 9, 2012 at 11:36 PM, Navin Kumar algorithm.i...@gmail.com wrote: Given a character array as input. Array contains only three types of characters 'R', 'G' and 'B'. Sort the array such that all 'R's comes before 'G's and all 'G's comes before 'B's. Constraint :- No extra space allowed(except O(1) space like variables) and minimize the time complexity. You can only traverse the array once. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/54GHWSwHHw8J. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com mailto:algogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Cheers, Nishant Pandey | Specialist Tools Development | npandey mailto:gvib...@google.com @google.com | +91-9911258345 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] [amazon]: dutch national flag algorithm
int low,mid,high;
low = mid = 0;
high = (int)(sizeof(arr)/sizeof(arr[0]))-1;
/*
According to Dutch national flag problem there are three types of
quantities in an array and we have to combine these elements together
but in a certain order
Let the elements in the array are in the form 0,1,2 then these elements in
an array should appear in order 0 then 1 then 2
( low to middle-1 ) - elements having 0 as a number
(middle to high-1 ) - 1 as a number
( high to arr - size) - 2 as a number
/
n = high;
for ( int i = 0; i = n; i++ ) {
if ( arr[mid] == 0 ) {
swap(arr[low],arr[mid]);
low++;
mid++;
}
else if ( arr[mid] == 2 ) {
swap(arr[mid],arr[high]);
high--;
}
else {
mid++;
}
}
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] [amazon]: dutch national flag algorithm
@Ashot: You can traverse array one time. In your case you are traversing
twice. First for counting occurrence of R , G and B then again traversing
for assigning values. But constraints is that you have to traverse only
once.
On Sun, Jun 10, 2012 at 5:13 PM, Akshat Sapra sapraaks...@gmail.com wrote:
int low,mid,high;
low = mid = 0;
high = (int)(sizeof(arr)/sizeof(arr[0]))-1;
/*
According to Dutch national flag problem there are three types of
quantities in an array and we have to combine these elements together
but in a certain order
Let the elements in the array are in the form 0,1,2 then these elements in
an array should appear in order 0 then 1 then 2
( low to middle-1 ) - elements having 0 as a number
(middle to high-1 ) - 1 as a number
( high to arr - size) - 2 as a number
/
n = high;
for ( int i = 0; i = n; i++ ) {
if ( arr[mid] == 0 ) {
swap(arr[low],arr[mid]);
low++;
mid++;
}
else if ( arr[mid] == 2 ) {
swap(arr[mid],arr[high]);
high--;
}
else {
mid++;
}
}
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] [amazon]: dutch national flag algorithm
sorry for the above post , there was careless mistake of mine. The code
will be
[code]
int low,mid,high;
low = mid = 0;
high = (int)(sizeof(arr)/sizeof(arr[0]))-1;
/*
According to Dutch national flag problem there are three types of
quantities in an array and we have to combine these elements together
but in a certain order
Let the elements in the array are in the form 0,1,2 then these elements in
an array should appear in order 0 then 1 then 2
( low to middle-1 ) - elements having 0 as a number
(middle to high-1 ) - 1 as a number
( high to arr - size) - 2 as a number
/
n = high;
while ( mid = high ) {
if ( arr[mid] == 0 ) {
swap(arr[low],arr[mid]);
low++;
mid++;
}
else if ( arr[mid] == 2 ) {
swap(arr[mid],arr[high]);
high--;
}
else {
mid++;
}
}
[/code]
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] [amazon]: dutch national flag algorithm
Given a character array as input. Array contains only three types of characters 'R', 'G' and 'B'. Sort the array such that all 'R's comes before 'G's and all 'G's comes before 'B's. Constraint :- No extra space allowed(except O(1) space like variables) and minimize the time complexity. You can only traverse the array once. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/54GHWSwHHw8J. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] [amazon]: dutch national flag algorithm
http://www.geeksforgeeks.org/archives/8133 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
