Why the if-else based solution is inefficient in Dutch National Flag problem(Sort an array of 0's, 1's and 2's ) on geeksforgeeks platform

Question

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;
            }
           
        }
        
    }
}

Answer 1

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;
        }
    }
}