5.1. Dutch National Flag - Variant 4

#1

Array of n objects with Boolean keys
Reorder so that objects with False keys appear first - solved
Relative order of Object with True keys should not change – ??

I tried few approaches and now wonder if it is even possible in O(1) space, and O(n) time

Is this a trick question

Authors - Any hints ?

0 Likes
#2

For an array (here: list) A I would initialize a writeIndex variable to the index of its last element (A.size() - 1). I would iterate the list downwards. If I encounter any ibject with key true I would swap it with the element at writeIndex position and decrement the writeIndex variable.

0 Likes