Dutch National Flag problem

Problem Statement

Given an array containing 0s, 1s and 2s, sort the array in place. You should treat numbers of the array as objects, hence, we can’t count 0s, 1s, and 2s to recreate the array.

The flag of the Netherlands consists of three colours: red, white and blue; and since our input array also consists of three different numbers that are why it is called Dutch National Flag problem.

Example 1:

Input: [1, 0, 2, 1, 0]
Output: [0, 0, 1, 1, 2]

Example 2:

Input: [2, 2, 0, 1, 2, 0]
Output: [0, 0, 1, 2, 2, 2,]

So what is the plan?

So the idea is to solve, We can use a Two Pointers approach while iterating through the array. Let’s say the two pointers are called low and high which are pointing to the first and the last element of the array respectively. So while iterating, we will move all 0s before low and all 2s after high so that in the end, all 1s will be between low and high.

Let's code, shall we!

def dutch_flag(lst):
    lower_pointer = 0
    high_pointer = len(lst) - 1
    iteration_pointer = 0

    while iteration_pointer <= high_pointer:
        if lst[iteration_pointer] == 1:
            iteration_pointer += 1
        elif lst[iteration_pointer] == 0:
            lst[lower_pointer], lst[iteration_pointer] = lst[iteration_pointer], lst[lower_pointer]
            lower_pointer += 1
            iteration_pointer += 1
        elif lst[iteration_pointer] == 2:
            lst[high_pointer], lst[iteration_pointer] = lst[iteration_pointer], lst[high_pointer]
            high_pointer -= 1
    return lst


def main():
    arr = [1, 0, 2, 1, 0]
    dutch_flag(arr)
    print(arr)

    arr = [2, 2, 0, 1, 2, 0]
    dutch_flag(arr)
    print(arr)

The final out put is

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

Two

Dutch National Flag problem

Comments

Coding Interviews

More from this blog

How to find the number of islands in a matrix

How to enable Multi-Factor Authentication (MFA) for S3 buckets?

How to Deploy the static website to S3 using GitHub actions.

How to find the length of the longest substring in it with no more than K distinct characters ?

Problem Statement

So what is the plan?

Let's code, shall we!

Command Palette

Comments

Coding Interviews

More from this blog

Problem Statement

So what is the plan?

Let's code, shall we!