Grokking 75: Top Coding Interview Questions
Vote

0% completed

​

Dutch National Flag Problem (medium)

Problem Statement

Try it yourself

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 colors: red, white and blue; and since our input array also consists of three different numbers that is 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 ]

Constraints:

  • n == arr.length
  • 1 <= n <= 300
  • arr[i] is either 0, 1, or 2.

Try it yourself

Try solving this question here:

Python3
Python3
. . . .
A

Anonymous

· 2 years ago

class Solution:
  def sort(self, arr):
    b, m, e = 0, 0, len(arr) - 1
    while m <= e:
        if arr[e] == 2:
            e -= 1
        elif arr[b] == 0:
            # here is the tricky part if the middle pointer at same position as the position as the beginning pointer 
            # and the beginning pointer = 0 it meas we are done with that part of the array so we can safely 
            # move the middle pointer too together with the beginning pointer
            if m == b: 
                m += 1
            b += 1
        elif arr[m] == 1:
            m += 1
        elif arr[e] < arr[m]:
            # swap 
            arr[e], arr[m] = arr[m], arr[e]
        elif arr[m] < arr[b]:
            # swap
            arr[m], arr[b] = arr[b], arr[m]
    return arr
A

Anonymous

· 3 years ago

I found the below solution on youtube. In my opinion, this is the easiest one to understand and honestly much more elegant than what is given here.

public static void sortColors_3Pointers(int[] nums) {

    int start = 0;
    int mid = 0;
    int end = nums.length - 1;

    while (mid <= end) {

        switch (nums[mid]) {
            case 0:
                // Swap with start index
                swap(nums, start, mid);
                mid++;
                start++;
                break;

            case 1:
                mid++;// do nothing
                break;

            case 2:
                // Swap with end index
                swap(nums, mid, end);
                end--;
                break;
        }
    }

}
Show 1 reply
A

Anonymous

· 3 years ago

solution seems to be using 3 pointers but does it one pass(which is optimal) ie. O(n)

Another, O(n) would be to use 2 pointers but do 2 passes - place 0s in 1st pass and 1s in 2nd pass.

A

Anonymous

· 4 years ago

Lack of visual explanation for these problems continues to be a point of contention imo.

For those wondering why we aren't advancing the i value on swaps for '2' we have no idea what number took the place of the '2'. So if we don't advance the pointer it covers the edge case where the swap brings in a 0 that needs to be addressed.

Show 2 replies
A

Anonymous

· 4 years ago

it would help if the solution is explained visually

A

Anonymous

· 4 years ago

this solution doesn't work on leetcode. error is it cannot find the symbol for the swap() method form this tutorial.

A

Anonymous

· 5 years ago

Could I not push each element to a hashmap and then just concat it?

{ 0: [0,0], 1: [1,1], 2: [2] } then I just concat those 3 arrays (still treating each of the numbers as an object. This will also be O(n) for time and space O(n)

Show 2 replies

Reading Progress

0%

Vote for new content

On This Page

Problem Statement

Try it yourself