I wasn't to sure about what the "naive brute force" is. My current solution should always run at 2n where n is the number of integers in the array, this assumes the combine method just iterates the two arrays together.
I'm 100% sure there is a 1n approach, where you iterate over the array only 1 time, but I personally hate working on arrays I'm iterating over.
edit I didn't see this was tagged as a Java problem, and the above is JavaScript, so it is what it is haha.
This is my "code-golf-esque" solution.
I wasn't to sure about what the "naive brute force" is. My current solution should always run at
2n
wheren
is the number of integers in the array, this assumes thecombine
method just iterates the two arrays together.I'm 100% sure there is a
1n
approach, where you iterate over the array only 1 time, but I personally hate working on arrays I'm iterating over.edit I didn't see this was tagged as a Java problem, and the above is JavaScript, so it is what it is haha.
oh Sorry... I should make it language independent..
I think it can be done in single array iteration and having two pointer for swapping