75. Sort Colors | LeetCode Medium | Python Solution | Array, Two Pointers, Sorting

Leetcode medium problem 75. Sort Colors, detailed explanation and solution in python language.

LeetCode Problem Link: https://leetcode.com/problems/sort-colors/
Solution (Python Code): https://github.com/shaheershukur/LeetCode-Python-Solutions/blob/main/Python%20Solutions/75.%20Sort%20Colors.py

#leetcode #python #solution

Problem Statement:
Given an array nums with n objects colored red, white, or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white, and blue.

We will use the integers 0, 1, and 2 to represent the color red, white, and blue, respectively.

You must solve this problem without using the library's sort function.
______________________________________________________________

LeetCode problem solving helps in improving one's problem solving and coding skills . Also, it helps in clearing technical interviews at top tech companies like Microsoft, Google, Amazon, Facebook, Walmart, Apple etc.
(FAANGM, MAANGM, Product based companies)

CC of video:
we are are given an array of integers and each number in that array can be either 0, 1 or 2.
the number 0 represents the color red.
number 1 represents the color white, and the number 2 represents the color blue.

we are asked to sort this array in-place. i.e., without using any extra space.
what we can do is, we will have 3 pointers.
the first one is a pointer to traverse through the array starting from the first element, till we finish the sorting.
the second one is a pointer for keeping track of the red elements starting from the left side, till we found out all the red elements,
and the third one is a pointer for keeping track of the blue elements starting from the right side, till we found out all the blue elements.

so lets solve this problem using these 3 pointers.
in the array, we will place the traversing pointer and red pointer on the left side.
and we will place the blue pointer on the right side.

so as we traverse through the array, if the current element is 0, then we will swap that element with the element in the red pointer.
since they both are on the same index, we will swap 0 with itself.
after swapping, we will increment both the red pointer and the traversing pointer because they both started from the same index, and the red pointer is not going to give any element not visited by the traversing pointer.

and if the current element is 2, we will swap that element with the element in the blue pointer.
here we will be swapping 2 with 2.
after swapping, we will decrement the blue pointer, but we will not be incrementing the traversing pointer, because we don't know what element will be given by the blue pointer from the right side.

so again at the current index, we are having 2.
we will swap it with the blue pointer.
after swapping 2 and 1, we will decrement the blue pointer.

now the element at current index is 1. if the current element is 1, then we need not have to do anything, because we are already moving all the red elements or zeroes to the left side and all the blue elements or twos to the right side. and therefore, automatically we will have all the white elements or ones in the middle.

so we will simply increment the traversing pointer.
here also, the current element is 1. so we will increment the traversing pointer.

now the current element is 0. so we will swap it with the red pointer.
after swapping 1 and 0, we increment both the red pointer and the traversing pointer.

at this point, we have already crossed the blue pointer, and therefore we will only find blue elements hereafter.
therefore we can terminate the traversal here, and this is the sorted colors array.

now lets code the solution.

we will store the length of the array in this variable.
initially we will set both red pointer and the traversing pointer to the leftmost index 0.
and we will set the blue pointer to the rightmost index n-1.

now lets traverse through the array till we cross the blue pointer.
during traversal, if the current element is 0, then we will swap it with the element at the red pointer.
and then we will increment the red pointer and also the traversing pointer.

if the current element is 2, then we will swap it with the element at the blue pointer.
and then we will decrement the blue pointer.

and if the current element is 1, then we need not have to do anything, and hence we will simply increment the traversing pointer.