Optimizing Dutch Flag Partitioning for Unsorted Arrays

Sort Colors

Been a while since my last entry, been busy with life and trying to practice cracking algorithms, whiteboard, read some algorithm-based book... Its been wild. Anyways, this question was taken from a leetcode medium level exercise, and though it gave me some trouble trying to implement the needed code given, it was kinda worth it at the end.
Also, why medium level?
That is because I'm still covering arrays, and not gonna go crazy blazing through the whole algorithm materials I'm studying. My goal's to understand most of the algorithms with useful use-case in the real world (like this one), not some algo-junkie...
Anyways, let's get down to business.

The Question

See leetcode question 75

Naive/Brute-force Approach

This approach - I like to call it the Caveman Approach - will have us loop through the array with each successful sort. More in the section below (will be using this approach in future posts)

Explanation/Thought Process

• a variable to represent the pivot is defined
• a list is iterated from left to right
  • with each iteration, elements smaller than the pivot are sorted to the left of the array via swaps
  • the loop is exited
• iterate through the list again, but in reverse
  • with each iteration, elements larger than the pivot are moved to the right side of the array
  • elements less than the pivot are not sorted (exit the loop if that is the case)
  • the loop is exited

The code below looks like some medium-level problem alright:

dutch_flag.py

def dutch_flag_partition(pivot_idx, arr):
    pivot = arr[pivot_idx]

    # First pass: group elements smaller than the pivot, loop restarts with each sort
    for i in range(len(arr)):
        for j in range(i + 1, len(arr)):
            if arr[j] < pivot:
                arr[i], arr[j] = arr[j], arr[i]
                break

    # Second pas: group elements larger than the pivot, same as above loop
    for i in reversed(range(len(arr))):
        if arr[i] < pivot:
            break
        for j in reversed(range(i)):
            if arr[i] > pivot:
                arr[i], arr[j] = arr[j], arr[i]
                break

result:

[1, 0, 1, 0, 0, 2, 2]

Problem With This Solution

The Space complexity is O(1), but the time complexity is O(n^2). This is because in the first pass, while searching for elements to swap, the array starts sorting from the beginning after each successful swap.

Better Approach

There is another way to approach this problem that saves us time. This approach will have us continue searching for elements to swap after one has been done by resuming operations from the next index after a swap is carried out.

Explanation/Thought Process

• two variables are initialized to represent the first and last index of the array and act as pointers
• a variable is initialized to represent the pivot
• the list is iterated from left to right
  • from the loop, we check if the elements are less than the pivot element. If so, the element found is swapped with the pointer that represents the first index of the array, and the pointer is incremented. This goes on until all elements are swapped appropriately.
  • loop exited, process moves to the next one
• the list is iterated again, but in reverse
  • if elements found are less than the pivot, the loop is broken out of
  • else if elements found are greater than the pivot, the same process carried out on the first loop is repeated, but the elements found are swapped with the pointer that represents the last index of the array, and that is decremented instead.
  • loop exited, you have your sorted list/array.

Problem With The Solution

None actually, except maybe white-boarding this might give newbies a headache for days, especially if you got the case of OCD or it's your first time, and still got OCD...
Anyways, Space complexity is O(1) like above, no additional memory created, only swaps, but Time complexity is O(n), because we are sorting the array elements in one iteration through the loop compared to the Brute-force approach.

Code below:
dutch_flag_On_improved.py

def dutch_flag_partitioning(pivot_idx, arr):
    pivot = arr[pivot_idx]
    smaller = 0
    # First pass: groups elements smaller than the pivot
    for i in range(len(arr)):
        if arr[i] < pivot:
            # swap the elements between each other
            arr[i], arr[smaller] = arr[smaller], arr[i]
            # increment smaller variable/ptr
            smaller += 1

    # Second pass: groups elements larger than the pivot
    larger = len(arr) - 1
    for i in reversed(range(len(arr))):
        if arr[i] < pivot:
            break
        elif arr[i] > pivot:
            arr[i], arr[larger] = arr[larger], arr[i]
        larger -= 1

Result:

[0, 2, 1, 0, 1, 0, 2]

Optimal Solution

This one looks like how a Dutch Flag Partitioning should look like, given the pseudocode seen on Wikipedia when Dutch Flag Partition is looked up.

Explanation/Thought Process

• Three variables (we will call them smaller, equal, and larger) are created to represent the first and last indexes of the array, with two out of the three variables initialized to the beginning of the array/list. These will be the pointers
• a loop is created, which executes if the equal pointer is less than the larger pointer
  • if the array element is equal to zero, the smaller and equal pointers elements are swapped, and the smaller and equal pointer is incremented by one.
  • else if the array element is equal to two, the equal and larger elements represented by their respective pointers are swapped, and the pointers are incremented by one.
  • else, we increment the equal pointer.

Problem With The Solution

None.

Code below:
dutch_flag_On_improved2.py

def dutch_flag_partitioning2(pivot_idx, arr):
    # pivot = arr[pivot_idx]

    smaller, equal, larger = 0, 0, len(arr) - 1

    while equal < larger:
        if arr[equal] == 0:
            arr[smaller], arr[equal] = arr[equal], arr[smaller]
            smaller, equal = smaller + 1, equal + 1
        elif arr[equal] == 2:
            arr[equal], arr[larger] = arr[larger], arr[equal]
            larger -= 1
        else:
            equal += 1

Looks pretty basic for a medium-level problem, but I assure you it is not basic, especially if you are white-boarding.

My Solution

Here's my own solution. Implementing the larger part was a pain. Code below:

mine.py

class Solution:
    def sortColors(self, nums: list[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        smaller, larger = 0, len(nums) - 1

        """Iterate through the array"""
        for i in range(len(nums)):
            """If the element in the array is on the smaller side based
            on the Dutch flag algorithm, swap and increment the smaller ptr"""
            if nums[i] == 0:
                nums[i], nums[smaller] = nums[smaller], nums[i]
                smaller += 1
                """Else if the element is on the larger side, decrement if
                it is on the larger side and also if the current array element
                is less than the larger element"""
                """Also check again for elements on the smaller side and
                move accordingly"""
            elif nums[i] == 2:
                while i < larger and nums[larger] == 2:
                    larger -= 1
                nums[i], nums[larger] = nums[larger], nums[i]
                if nums[i] == 0:
                    nums[i], nums[smaller] = nums[smaller], nums[i]
                    smaller += 1

result:
An ordered list of 0's, 1's, and 2's.