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.

tttt1

ttt41

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:

 

ttt61

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).

Source

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:

chunk 3

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 🙂

 

  • epavlova

    Hello, thank you very much for your blog. It provide a lot of useful information. I would like to share some my observations on the problem above if you don’t mind.
    I borrowed from you the idea to split data into chunks and think that I could propose solution with O(n) time complexity and O(1) memory space. So first let’s do not use linked lists. We don’t need them at all. We could traverse through the array and each time there is value less than current chunk head, start new chunk as in your soluiton. Then we will start to count number of years for given chunk if chunk has more than 1 element. This is done in the following way :Initialize years count to 1. When current item is less than previous, add 1 to current years count. Meanwhile we store max years count from all chunks and this is the soluiton. For example: We have :
    {20 , 5, 6, 14 ,2 , 2 , 10 ,5} . 3 chunks are generated – chunk1 – {20}, chunk2 – {5,6,14},chunk 3-{2,2,10,5} . For chunk1 – there is 0 years count, For chunk2 – we start from 1 and this is number of years. For chunk3 – start from 1 and increment counter at 5 because 5 is less than 10 (previous) ,so we have 2 years for chunk3. The solution is max (0,1, 2) = 2 years
    I hope this solution to be correct

    • Hi, Thanks for the comment. I admire that you took so much of time to write this down. It sounds good and works for simpler cases but I think there would be few loop holes where test cases become complex.

      How would you answer if a chunk has 2, 2, 10, 8, 6, 5, 7, 4, 3

      If you can write down a code which I can run, I might be able to find test cases which may not pass for this approach.

      • epavlova

        Hello again,

        Sorry that I replied to you a little bit later but coudn’t find time till now. I worked out my approach to some generic solution. My last suggestion had flows in some direction which you kindly show up to me. It worked only for a case when there are uniqie heights in array. I fixed this solution.
        I coudn’t find a way to format my code

        Please find some contra examples to check.

        Here is my code :

        private int getSurvivalYearofChunk(int from ,int to, int[] heights,int[] counts) {

        if (from == to)

        return 0;

        int survivalYear = 0;

        int index = from;

        int curSurvYear = 0;

        do {

        if (index != from) {

        if (heights[index – 1] < heights[index]) {

        curSurvYear = Math.max(curSurvYear, counts[index]);

        }

        else {

        survivalYear += counts[index];

        }

        }

        index += counts[index];

        }

        while (index < to + 1);

        return survivalYear + curSurvYear;

        }

        public int survivalYear(int[] heights) {

        if (heights == null) {

        throw new NullPointerException();

        }

        if (heights.length =0;i–) {

        if (heights[i] == heights[i+1]) {

        counts[i] = counts[i+1]+1;

        } else {

        counts[i] = 1;

        }

        }

        int minChunk = heights[0];

        int survivalYear = 0;

        int chunkHead = 0;

        for(int index = 1; index<heights.length; index++) {

        if (heights[index] <= minChunk) {

        survivalYear = Math.max(getSurvivalYearofChunk(chunkHead ,index – 1, heights, counts), survivalYear);

        chunkHead = index;

        minChunk = heights[index];

        }

        }

        survivalYear = Math.max(getSurvivalYearofChunk(chunkHead ,heights.length – 1, heights,counts), survivalYear);

        return survivalYear;

        }

        • Just got a chance to fix the formatting of the code. Will respond back with the correctness in some time.
          Again, thanks for the effort 🙂

          • Hi Again,

            I tried and tested this code, found that it works for several test cases but fails for few.

            Here is one such test case which fails

            20 5 6 15 2 2 17 2 11 5 14 5 10 9 19 12 5

          • epavlova

            mistake,sorry

          • epavlova

            I will analyse case and send you fixed code. Thank you very much for your support.