# Cursed Trees – Interview Question

## Problem Statement

This is an awesome interview question which tests our ability to extensively use data structures.

We are given an array of trees with different heights. The trees have a curse upon them, they do not grow any more and for a given pair of trees, if a tree is taller than the one to its left then the tree will die in a year.

The task at hand is to find out, the number of years after which no trees will die.

#### Explanation

Year 1 : At the end of the first year the trees with height 6 , 14 and 10 will die. All of these trees have a smaller tree to their left and the remaining trees will look the second image.

Year 2 : At the end of second year the tree at the end of the list (the one with height 5) will die because it has a smaller tree of height 2 at the left. The remaining trees will look like below:

After the second year, no trees will die. Hence the answer to this situation is 2 years.

## Solution

#### Trivial

1. Store the tree heights in a linked list.
2. Start from the beginning of the linked list and for each pair where the right is taller than the left, remove the right from the linked list.
3. Upon reaching the end of the linked list, increment the year counter.
4. Repeat 2 and 3 until, no more trees are removed from the linked list.

This works good in most of the trivial cases, it might end up consuming more time when the heights are reverse sorted and the array of heights is huge (may be in millions).

#### Efficient Solution

We can try and approach this problem in a different way.

It is not necessary to evaluate all the trees against every other tree. We only need to consider chunks of the array. The chunks are so wisely chosen that it will have the smallest tree in the beginning of the chunk and will span till we get heights more than the first tree in the chunk.

For e.g. consider the below trees:

If we encounter a tree with smaller height that the first tree in the chunk, it is time to start a new chunk from there and this process continues till the end of the array of trees.

For each chunk we calculate the max years the chunk will  take before no more trees die. The solution to the complete problem would be the max of the solution to all the chunks.

Let us try to find the max life (in years) of each chunk.

Chunk 1: No trees will die in the first chunk so the number of years to survival is, say -1

Chunk 2: In the second chunk the first tree(height 5) will never die, the second(height 6) and the third(height 14) will die in a year , hence number of years to survival is 1.

Chunk 3: In the third chunk the tree will never die because its the smallest in the chunk. So number of years to survival is -1.

Chunk 4: In the fourth chunk the second tree (height 10) will die in a year and, the next tree (height 5) will die in 2 years. Hence, the number of years to survival is 2.

The max of all these years (-1, -1, 1 & 2) is 2. Hence the trees will not die after 2 years.

#### Algorithm

I will try to put this in an algorithm:

1. Maintain a variable called year, initialize it with zero.
2. Add the first tree in a linked list and consider its life to be say -1. This tree will never die being the first tree( also the beginning of the chunk).
3. Consider the next tree in the array, say T. Assign it a life value 1. Two situations arrive:
1. If T is smaller
• Remove a tree from the beginning of the list. Say its life was X.
• If X is -1 (the tree is the first in the chunk), then assign X as T’s life (make the current tree, the beginning of the chunk. This is like switching to a new chunk).
• If X is greater than -1 (the tree survived X years) then add X to the life of T (the current tree must survive a year more , i.e. X+1)
• Repeat this till T is smaller than the tree at the beginning of the list.
2. T is taller
• If T has the same life as the tree at the beginning of the list(both the trees survived for the same time. Remove the tree from the list.
• Repeat this till the list is empty or the life’s wont match.
4. Add T to the beginning of the list.
5. Compare the life of T to the value of year and assign the max to year.
6. Repeat steps 3 to 6 till the array ends.

#### Source

You can find both the source codes at github.

## Analysis

#### Trivial Algorithm

In the worst case when the first tree is the smallest and the rest of the array is reverse sorted. We will end up having a O(N2) running time. The space required is almost constant O(1).

#### Efficient Algorithm

The outer loop is certainly running for N times, where N is the length of the array.

The inner loop will only runs less than or equal to K times where K is of the order of number of years to survival.

This happens because the list will at max contain one tree of smaller height, and K number of trees with height between the smaller height and the height of the current tree under consideration.

Running time is of the format O(xN) where x is proportional to the size of the temporary linked list we maintain. That linked list grows at a very slow rate. Definitely x << N.

Side Note: The linked list grows at a slow rate because  in every iteration we add one node to the linked list. But in most of the iterations we end up either emptying the list or removing at least one element from it.  There is one scenario where we do not remove anything from the list and that is the case where the current tree height is bigger than the first tree in the list and the tree height in the list is larger than 1. As per one of my calculations we need around four elements correctly placed to increase the length of the linked list and the years of survival to 2. Eight elements to get the length of the linked list and years of survival to 3… I think there has to be a exponential relation between the number of elements and the length of the linked list. However this calculation is not proven. But if that’s true then the running time would be O(N logN) and space complexity would be O(logN).

You are free to do the maths and help me with the right answer.

Happy learning. Don’t forget to subscribe 🙂