2
$\begingroup$

I came across the following problem in the book "Elements of Programming Interviews in Python".

Given an array A of n objects with Boolean-valued keys, reorder the array so that objects that have the key false appear first. The relative ordering of objects with key $true$ should not change. Use $O(1)$ additional space and $O(n)$ times.

My question is, is there an algorithm with $O(1)$ additional space and $O(n)$ time to keep the relative ordering for element with $true$ AND $false$ keys? If so, what is the algorithm? If not, how can I prove it is not possible?

The algorithms I could think about were either $O(n^2)$ or used $O(n)$ additional space.

Improve this question
$\endgroup$
2
  • $\begingroup$ @greybread The block quote has the original question, and mine relates to the revised version (both stable). I included the original in the block quote before asking my question. Should I remove the original question? $\endgroup$ Commented Jan 6, 2024 at 0:53
  • $\begingroup$ No, currently I think the edit helps avoiding misinterpretation. It may be even better to change the wording though - For the related problem of stable bipartition, is there an algorithm with O(1) additional space and O(n) time, keeping the relative ordering for elements with true keys as well as those with false keys? $\endgroup$ Commented Jan 6, 2024 at 3:39

3 Answers 3

Reset to default
1
$\begingroup$

Yes, there is such an algorithm. Hint:

Scan from right to left (from the end of the array towards the front).

Improve this answer
$\endgroup$
0
0
$\begingroup$

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$.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Do you have any suggestions on how to prove that there is no solution for both stable? $\endgroup$ Commented Jan 6, 2024 at 0:47
  • $\begingroup$ @R.Javid honestly I lack experience in that arena, I can only guess that you can't preserve both information during a swap, and you lose information when you don't have auxiliary space $\endgroup$ Commented Jan 6, 2024 at 15:03
-1
$\begingroup$

Hint:

$$\color{blue}1\color{blue}2\color{red}3\color{blue}4\color{red}5\color{blue}6\color{red}7\color{red}8\color{blue}9$$

$$\color{blue}1\color{blue}2\color{red}3\color{blue}4\color{red}5\color{red}8\color{red}7\color{blue}6\color{blue}9$$

$$\color{blue}1\color{blue}2\color{red}3\color{red}7\color{red}5\color{red}8\color{blue}4\color{blue}6\color{blue}9$$

$$\cdots$$

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ The relative order of reds has changed here. $\endgroup$ Commented Sep 21, 2023 at 20:17

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.