Grokking 75: Top Coding Interview Questions

0% completed

​
Solution: Dutch National Flag Problem

Problem Statement

Examples

Example 2

Solution

Step-by-Step Algorithm

Algorithm Walkthrough

Code

Complexity Analysis

Time Complexity

Space Complexity

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.

Examples

Example 1

  • Input: arr = [1, 0, 2, 1, 0]
  • Output: [0, 0, 1, 1, 2]
  • Explanation:
    • All 0s are moved to the front, 1s in the middle, and 2s at the end.
    • The relative order within each group doesn't matter.

Example 2

  • Input: arr= [2, 2, 0, 1, 2, 0]
  • Output: [0, 0, 1, 2, 2, 2]
  • Explanation:
    • All 0s come first, followed by the 1, and then all 2s at the end.
    • Sorting is done in-place without using extra space or counting.

Constraints:

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

Solution

The brute force solution will be to use an in-place sorting algorithm like Heapsort which will take O(N*logN). Can we do better than this? Is it possible to sort the array in one iteration?

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. In the end, all 0s are on the left, all 1s are in the middle, and all 2s are on the right.

Step-by-Step Algorithm

  1. We start by initializing three variables: low to 0, high to the last index of the array, and i also to 0. Low is meant to keep track of the latest position where a 0 should be placed, high is meant to keep track of the latest position where a 2 should be placed, and i is used to iterate through the array.

  2. We then start a loop that continues as long as i is less than or equal to high. In each iteration of the loop, we check the value of the array at the index i.

  3. If the value is 0, we swap the values at the indices i and low. We then increment both i and low, since we know that the new element at low is 0 (sorted in its correct place) and we can move to the next index.

  4. If the value is 1, we do nothing other than increment i. This is because we want 1s to be in the middle of the array.

  5. If the value is 2, we swap the values at i and high. However, after the swap, we only decrement high without incrementing i. This is because the new value at index i (after the swap) could be 0, 1 or 2, and we need to check this value again in the next iteration.

  6. The swap function simply switches the values at two given indices in the array.

  7. The process continues until i is greater than high, at which point every element in the array has been checked and placed in its correct position. Hence, the array is now sorted.

Algorithm Walkthrough

Image

Initial State:

  • Array: [1, 0, 2, 1, 0]
  • low = 0, high = 4
  • i = 0

Step-by-Step Walkthrough:

  1. First Iteration (i = 0):

    • arr[i] = 1
    • Since it's 1, just increment i.
    • State after iteration:
      • Array: [1, 0, 2, 1, 0]
      • low = 0, high = 4
      • i = 1

  2. Second Iteration (i = 1):

    • arr[i] = 0
    • Swap arr[i] with arr[low] (Swap positions 1 and 0).
    • Increment low and i.
    • State after iteration:
      • Array: [0, 1, 2, 1, 0]
      • low = 1, high = 4
      • i = 2

  3. Third Iteration (i = 2):

    • arr[i] = 2
    • Swap arr[i] with arr[high] (Swap positions 2 and 4).
    • Decrement high.
    • i remains the same to check the swapped element.
    • State after iteration:
      • Array: [0, 1, 0, 1, 2]
      • low = 1, high = 3
      • i = 2

  4. Fourth Iteration (i = 2):

    • arr[i] = 0
    • Swap arr[i] with arr[low] (Swap positions 2 and 1).
    • Increment low and i.
    • State after iteration:
      • Array: [0, 0, 1, 1, 2]
      • low = 2, high = 3
      • i = 3

  5. Fifth Iteration (i = 3):

    • arr[i] = 1
    • Since it's 1, just increment i.
    • State after iteration:
      • Array: [0, 0, 1, 1, 2]
      • low = 2, high = 3
      • i = 4

Final State:

  • Array: [0, 0, 1, 1, 2]
  • All 0s are at the beginning, followed by all 1s, and all 2s at the end.

Code

Here is what our algorithm will look like:

Python3
Python3
. . . .

Complexity Analysis

Time Complexity

  • Single pass through the array: The algorithm uses a single for loop that iterates through the array once. The pointer i moves from the start to the end of the array, and at each iteration, it processes the current element.
  • Swaps: Each swap operation occurs in constant time O(1). Since each element is either swapped or incremented only once, the number of swaps and comparisons is proportional to the length of the array.

Overall time complexity: Since the algorithm processes each element of the array exactly once, the time complexity is O(N), where N is the number of elements in the array.

Space Complexity

  • In-place modification: The algorithm sorts the array in place, meaning that it doesn't require any additional space that scales with the size of the input array.
  • Auxiliary space: The only extra space used is for a few integer variables (low, high, and i), which require constant space, O(1).

Overall space complexity: Since the algorithm does not use any additional data structures, the space complexity is O(1).

Mark as Completed

On This Page

Problem Statement

Examples

Example 2

Solution

Step-by-Step Algorithm

Algorithm Walkthrough

Code

Complexity Analysis

Time Complexity

Space Complexity