Sort Colors LeetCode Challenge June Day 11

Quoestion: ClickHere

Approach:

They have mentioned that you are not suppose to use the library's sort function for this problem.

There is an another approach for this problem which is called two pointer technique.we take two pointers, leftpointer pointing to first element of array and rightpointer pointing to last element of array.

first we arrange 0's and 2's then automatically 1's will be in correct position.Intialize left ,right pointers and current which is pointing to first element.

check if current ==0 if yes swap current and left and increase left,current by 1.if current ==2 then swap current and right then decrease right pointer by 1.Repeat above process until current <=right pointer.

Let's Apply this to example.

Step1:Intialize current,left,right

current,left					right
1	0	2	1	2	0

Step2: current not equal to 0 or 2 so current+=1

left	current				right
1	0	2	1	2	0

Step3:since current = 0 we swap left and current

	left	current			right
0	1	2	1	2	0

Step4: since current = 2 swap right and current

	left	current		right
0	1	0	1	2	2

Step5:since current = 0 swap left and current

		left,current		right
0	0	1	1	2	2

Step6:current not equal to 0 or 2 so current+=1

		left	current	right
0	0	1	1	2	2

Step7:current not equal to 0 or 2 so current+=1

		left		right,current
0	0	1	1	2	2

Step8:current ==2 swap right and current

		left	right	current
0	0	1	1	2	2

Step9: current is greater than right so we break the loop and the array is sorted

Python Code:

#Do Follow For More Problems