Interview Question
Country: India
@saurabh answer will work just fine. This is just for fun :) Painter's like algorithm.
If we know MAX tree size, we can allocate an array of that size and starting from the back of the input array, fill in first elements of our working array with the index of a current tree. Number of elements to fill is the height of a current tree. Repeat the process for each tree in the input array in reverse order. The output would be unique numbers in the working array. Basically projection of all trees to a single array. For example:
Working array (result):
0011125557
Input:
7
5 7
5 7
5 7
2 5 7
12 45 7
12 45 7
12345 7
012345 7
01234567
- SK January 17, 2014