Skip to main content
Expanded answer
Source Link
Kenneth Kho
  • 765
  • 3
  • 17

Here's how to do itThere is no solution for $false$both stable:, but I provide the solution for the original book problem.

Let$false$ stable: let $i = 0$, go through every element from left to right, and each time we see a $false$ element, swap it to index $i$, and increment $i$. The time complexity is $O(n)$ and the auxiliary space is $O(1)$.

It is similar for $true$ stable: let $i = n - 1$, but impossible for both stablego through every element from right to left, and each time we see a $true$ element, swap it to index $i$, and decrement $i$.

Here's how to do it for $false$ stable:

Let $i = 0$, go through every element from left to right, and each time we see a $false$ element, swap it to index $i$, and increment $i$. The time complexity is $O(n)$ and the auxiliary space is $O(1)$.

It is similar for $true$ stable, but impossible for both stable.

There is no solution for both stable, but I provide the solution for the original book problem.

$false$ stable: let $i = 0$, go through every element from left to right, and each time we see a $false$ element, swap it to index $i$, and increment $i$.

$true$ stable: let $i = n - 1$, go through every element from right to left, and each time we see a $true$ element, swap it to index $i$, and decrement $i$.

Source Link
Kenneth Kho
  • 765
  • 3
  • 17

Here's how to do it for $false$ stable:

Let $i = 0$, go through every element from left to right, and each time we see a $false$ element, swap it to index $i$, and increment $i$. The time complexity is $O(n)$ and the auxiliary space is $O(1)$.

It is similar for $true$ stable, but impossible for both stable.