75. Sort Colors.md

75. Sort Colors (Mdeium)

[tag] two pointers

• use 3 pionters: two fixed pointers, l and r, on both side for representing 0 and 2.
• one pointer m as a floating pointer in the middle.
• while m <= r keep going, otherwise, done.

'''
- two fixed pointer on both side for 0 and 2
- one floating pointer representing numbers to be modified.

0 0 1 1 2 2
    l        
      r
      m

if m swap with l, l and m += 1.
if m swap with r, r -= 1, m saty the same.
'''
class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        l, m, r = 0, 0, len(nums) - 1
        while(m <= r):
                if nums[m] == 0:
                    nums[m], nums[l] = nums[l], nums[m]
                    l, m = l + 1, m + 1
                elif nums[m] == 2:
                    nums[m], nums[r] = nums[r], nums[m]
                    r -= 1
                else:
                    m += 1