I just love this idea:
But when you have an input such as [42,1,2,3,4,5,6]
you just get
[42]
instead of [1,2,3,4,5,6]
. You can get a better result if you use divide and conquer. And that is something Stalin would do, don’t you think? So I implemented a recursive solution in Java. It tries all possible results, which is not a single pass and therefore defeats the purpose of having a fast O(n)
algorithm. And my implementation isn’t even in-place. A new data structure has to be created. That’s why I also added an implementation using a linked list, which is what Mathew describes.
The code is on pastebin: https://pastebin.com/rEmvZSiA