Problem statement

https://binarysearch.com/problems/List-Partitioning/

Solution

Equal to Leetcode 75. Sort Colors.

Complexity

It is O(n) for time and O(1) for space.

Code

class Solution:
    def solve(self, strs):
        beg, mid, end = 0, 0, len(strs) - 1
        
        while mid <= end:
            if strs[mid] == "red":
                strs[beg], strs[mid] = strs[mid], strs[beg]
                mid += 1
                beg += 1
            elif strs[mid] == "blue":
                strs[mid], strs[end] = strs[end], strs[mid]
                end -= 1
            else:
                mid += 1

        return strs