"""
Key intuition:
We partition the array into four regions: 0s on the left, 1s in the middle,
unknown elements to be processed, and 2s on the right.

Approach:
Traverse the array once using three pointers. When a 0 is found, swap it to
the left region; when a 2 is found, swap it to the right region; when a 1 is
found, simply move forward. The middle pointer is not advanced after swapping
a 2 because the incoming element is still unclassified.

Important insight:
When swapping with the left pointer, the element coming into the middle
position must be a 1 or 0, so it is safe to advance
the middle pointer. However, when swapping with the right pointer, the incoming
element can be 0, 1, or 2, so the middle pointer must stay to reprocess it.
"""


class Solution:
    def sort012(self, arr):
        i=0
        j=0
        k=len(arr)-1
        while j<=k:
            if arr[j]==0:
                arr[i],arr[j]=arr[j],arr[i]
                i+=1
                j+=1 #here we are increasing j because left element is already processed and after swapping j with i will be having 1 because if K would have been there, it would have been gone to right side and if 0 it would have gone on the left side
            elif arr[j]==2:
                arr[j],arr[k]=arr[k],arr[j]
                k-=1
            else:
                j+=1
        return arr