aptsensdet
BAN USERDo a linear scan and count how many items < key.
Place the key in the right index in the array (maybe use a separate output array).
Maintain 3 pointers - 1 at the 1st position of the array that's less than the key (unless key is the 1st), another index next position after the key and 3rd index on the key.
Do another linear scan and if element is < place at the position of 1st index & increment that index. Same if element > key, use 2nd index. If element equal, place it before or right after the 3rd index.
This will be O(n).
we can't use extra storage, so how about this:
public class Node
{
Node levelFirst; //1st node of every level
Node next; //sibling of every node
Node parent;
int value;
}
Now just do a level order traversal. Lots of edge cases - how do you detect that the level is done. Keep track of 1st node of every level, as you'll need to come back to it, once every level is done, to start the next level.
@Dumbo - beautiful solution. It'd be cool if you can post an implementation :).
- aptsensdet June 29, 2013
@smffap - what abt numbers like 10 or 100?
Here's a compiled/executed (non-recursive) solution that should handle all special cases
- aptsensdet July 06, 2013