If-else based implementation of the Dutch National Flag problem is giving RunTime Error while submitting whereas switch-case based implementation got accepted successfully.
Test case which was giving error having 65,754 number of elements.
class Solution
{
public static void sort012(int a[], int n)
{
// code here
int l=0,m=0,h=n-1;
int temp=0;
while(m<=h){
switch(a[m]){
case 0:
temp = a[l];
a[l] = a[m];
a[m] = temp;
l=l+1;
m=m+1;
break;
case 1:
m=m+1;
break;
case 2:
temp = a[h];
a[h] = a[m];
a[m] = temp;
h = h-1;
break;
}
}
}
}
And the if-else based implementation:
class Solution
{
public static void sort012(int a[], int n)
{
// code here
int l=0,m=0,h=n-1;
while(m!=h){
int temp;
if(a[m]==0){
temp = a[l];
a[l] = a[m];
a[m] = temp;
l=l+1;
m=m+1;
}
if(a[m]==2){
temp = a[h];
a[h] = a[m];
a[m] = temp;
h = h-1;
}
if(a[m]==1){
m=m+1;
}
}
}
}
>Solution :
The main problem in your second version is that you don’t mimic the switch instruction and allow multiple if blocks to be executed within a single iteration of the loop, and that means the while condition is not guaranteed to hold before evaluating and entering an if block.
As a knock-on effect of this bug, the while condition is not as resilient as the one in the first version, so that there is even a risk that the loop will continue with m > h leading to errors.
Alternative solution
A more simple approach to this problem is to just count the number of occurrences of the three possible values: how many zeroes, how many ones, how many twos.
Then iterate the array again and re-populate it based on those counters.
class Solution {
public static void sort012(int[] a, int n) {
int[] counter = {0, 0, 0};
for (var value : a) {
counter[value]++;
}
for (int i = 0, value = 0; i < a.length; i++) {
while (counter[value]-- == 0) {
value++;
}
a[i] = value;
}
}
}