Community

Start a Thread
Filters
By Category
Notifications
Subscribe You’re not receiving notifications from this thread.

Dutch National Flag Problem (Main Thread)

Here is the interview question prompt, presented for reference.

This problem is named the "Dutch national flag problem" because the flag of the Netherlands is comprised of the colors red, white, and blue in separate parts. Although we won't be using colors, the premise of the challenge is to develop a sorting algorithm that performs some form of separations of three kinds of elements.

To simplify things, we'll use 0s, 1s, and 2s.

Given an array consisting of only 0s, 1s, and 2s, sort the elements in linear time and constant space.

const arr = [2, 0, 1, 0, 2]
dutchNatFlag(arr)
// [0, 0, 1, 2, 2]

Constraints

  • Length of the array <= 100000

You can see the full challenge with visuals at this link.

Challenges • Asked about 7 years ago by Jake from AlgoDaily

Jake from AlgoDaily Commented on Nov 30, 2017:

This is the main discussion thread generated for Dutch National Flag Problem.

Dmitry Pavlov Commented on Jan 19, 2021:

Hi, Jake!

Tests for java are broken in this tutorial. Seems like it checks link equality not content equality of arrays

SNIPPET
╷
├─ JUnit Jupiter ✔
└─ JUnit Vintage ✔
   └─ MainTest ✔
      ├─ thirdTest ✘ expected:<[I@769f71a9> but was:<[0, 0, 0, 1, 1, 2, 2, 2]>
      ├─ firstTest ✘ expected:<[I@17046283> but was:<[0, 1, 2]>
      └─ secondTest ✘ expected:<[I@5bd03f44> but was:<[0, 0, 1, 2, 2]>

Also tests required second parameter in method call :)

public void firstTest() {
assertEquals(this.dutchNationalFlag(new int[] {0, 1, 2}, 2), "[0, 1, 2]");
}

aman Commented on May 01, 2023:

I didnt understand why mid is not incremented when the current element is 2. Or rather why mid is incremented when current element is 0? please help!