Assume I have two arrays, both of them are sorted, for example:

A: [1, 4, 5, 8, 10, 24]

B: [3, 6, 9, 29, 50, 65]

And then I merge these two array into one array and keep original relative order of both two array

C: [1, 4, 3, 5, 6, 9, 8, 29, 10, 24, 50, 65]

Is there any way to split C into two sorted array in O(n) time?

note: not necessarily into the original A and B

CodePudding user response：

Greedily assign your integers to list 1 if they can go there. If they can't, assign them to list 2.

CodePudding user response：

Let's take your example.

[1, 4, 3, 5, 6, 9, 8, 29, 10, 24, 50, 65]

In time O(n) you can work out the minimum of the tail.

[1, 3, 3, 5, 6, 8, 8, 10, 10, 24, 50, 65]

And now the one stream is all cases where it is the minimum, and the other is the cases where it isn't.

[1,    3, 5, 6,    8,     10, 24, 50, 65]
[   4,          9,    29,               ]

This is all doable in time O(n).

We can go further and now split into 3 streams based on which values in the first stream could have gone in the last without changing it being increasing.

[      3, 5, 6,    8,     10, 24,       ]
[1,       5, 6,    8,             50, 65]
[   4,          9,    29,               ]

And now we can start enumerating the 2^6 = 64 different ways of splitting the original stream back into 2 increasing streams.