Hacker Rank - Poisonous Plants

Question

I have the solution for the problem, but it is taking me 7 seconds to run on a large dataset. I am trying figure out a better way of doing this. It has to run in under 3 seconds.

Problem Statement:

There are N plants in a garden. Each of these plants has been added with some amount of pesticide. After each day, if any plant has more pesticide than the plant at its left, being weaker than the left one, it dies. You are given the initial values of the pesticide in each plant. Print the number of days after which no plant dies, i.e. the time after which there are no plants with more pesticide content than the plant to their left.

Explanation:

Initially all plants are alive.

• Plants = \$\{(6,1), (5,2), (8,3), (4,4), (7,5), (10,6), (9,7)\}\$
• Plant = \$(i,j)\$ \$\Rightarrow\$ \$j\$th plant has pesticide amount \$i\$.
• After the 1st day, 4 plants remain as plants 3, 5, and 6 die.
• Plants = \$\{(6,1), (5,2), (4,4), (9,7)\}\$
• After the 2nd day, 3 plants survive as plant 7 dies.
• Plants = \$\{(6,1), (5,2), (4,4)\}\$
• After the 3rd day, 3 plants survive and no more plants die.
• Plants = \$\{(6,1), (5,2), (4,4)\}\$

I added the test case to this Pastebin.

static void Main(string[] args)
{
    Stopwatch timer = new Stopwatch();
    timer.Start();
    string data = "";// Console.ReadLine(); //"6 5 8 4 7 10 9";

    foreach (var line in File.ReadLines(@"FilePath"))
    {
        data = line;
    }

    bool happyState = false;
    bool plantDied = false;
    int numberOfDays = 0;

    LinkedList<int> lstPlants = new LinkedList<int>(data.Split(new char[] { ' ', '\t' }).Select(s => int.Parse(s)).ToList());

    LinkedListNode<int> lastNode = lstPlants.Last;
    LinkedListNode<int> currentNode = lstPlants.First;
    int cValue = currentNode.Value;

    while (!happyState)
    {
        numberOfDays++;
        plantDied = false;
        happyState = false;
        lastNode = lstPlants.Last;
        currentNode = lstPlants.First;
        cValue = currentNode.Value; //bug fix
        while (currentNode != lstPlants.Last)
        {
            if (currentNode.Next.Value > cValue)
            {
                plantDied = true;

                cValue = currentNode.Next.Value;
                lstPlants.Remove(currentNode.Next);
                //currentNode = currentNode.Next;
            }
            else
            {
                currentNode = currentNode.Next;
                cValue = currentNode.Value;
            }
        }

        if (!plantDied)
        {
            numberOfDays--;
            happyState = true;
        }

    }
    timer.Stop();
    Console.WriteLine("Time taken to calculate is {0} seconds and the answer is {1}.", timer.Elapsed.TotalSeconds, numberOfDays);
    Console.ReadLine();
}

Answer 1

Let's start by analysing the current algorithm.

Each day that plants are dying, we iterate through all living plants. So the worst case would be if only one plant dies each day. In this case, we can see that the algorithm will take \$O(N^2)\$ time.

For example, the input sequence \$ 1, 2, 2, 2, 2, \ldots, 2\$ will exhibit this quadratic behaviour.

From the problem statement, \$1 \leq N \leq 10^5\$, so we will have to do better than \$O(N^2)\$.

---

We start with the easy case, when the current plant has more pesticide in it than the one to its immediate left. Then we know that the current plant dies after one day.

Otherwise, we look for the right-most plant to the left of us that has less pesticide than the current plant.

If there is no such plant then we know that the current plant will never die.

So suppose there is such a plant, and let's say it's at index \$i\$. I claim that the current plant (at index \$k\$) will die on day $$\max \left\{ d[j] \,\middle|\, i < j < k \right\} + 1,$$ where \$d[j]\$ is the day on which plant \$j\$ dies.

What this means is that for plant \$k\$ to die, I have to wait for all the plants between plant \$i\$ and plant \$k\$ to die, at which point \$i\$ will be to the immediate left of \$k\$, and then I have to wait one more day.

So far, we still have an \$O(N^2)\$ algorithm. If we think about the input \$ 1, 2, 2, 2, 2, \ldots, 2\$, for every plant we have to iterate all the way back to the start to find the plant with less pesticide in it.

---

Let's think about the following input:

$$ 2, 5, 1, 10, 3, 11 $$

The first plant will never die, and the second plant will die on day one.

For the third plant, we look at the previous two values and see that they both have more pesticide than the third, so the third plant will never die. The key here is that we can now forget that the first and second plants ever existed.

Why? Because any plant waiting for the first or second plant to die will have to wait for the third plant to die first.

The fourth plant dies on day one.

For the fifth plant, we look at the previous two values, 1 and 10. The fifth plant will die a day after the 10, and again we can forget the 10 ever existed, because any plant waiting for the 10 to die will have to wait for the 3 to die first.

---

Spoilers

How would this look in code? Suppose we have a stack containing pairs of the amount of pesticide in the plant and the day on which the plant dies.

If we are in the interesting case, where the plant doesn't die on day one, then we keep popping elements off the stack while they have at least as much pesticide as the current plant. While we're popping elements, we keep track of the maximum number of days it takes for these plants to die.

If we have popped all elements off the stack, the current plant will never die. Otherwise, the plant will die on the maximum number of days that we've seen, plus one.

One we have calculated the number of days it takes for the plant to die, we push it onto the stack.

Since exactly \$N\$ elements are pushed onto the stack, we cannot have more than \$N\$ pops. So we can see that this algorithm is \$O(N)\$.

Answer 2

I'm not sure it would be any more efficient, but it might be. At least it's a bit easier to read. Instead of reading every line of the file like this.

        string data = "";// Console.ReadLine(); //"6 5 8 4 7 10 9";


        foreach (var line in File.ReadLines(@"FilePath"))
        {
            data = line;
        }

Use linq to "directly" get the last line. (Although, AFAIK, it still has to read the whole file into memory.)

string data = File.ReadLines(@"FilePath").Last()

This scrolls way too far off the screen.

 LinkedList<int> lstPlants = new LinkedList<int>(data.Split(new char[] { ' ', '\t' }).Select(s => int.Parse(s)).ToList());

Add a newline and use var for readability's sake.

var lstPlants = new LinkedList<int>(data.Split(new char[] { ' ', '\t' })
        .Select(s => int.Parse(s)).ToList());

I don't have any advice on how to change it, but it's pretty obvious that the nested while loops are the source of the performance issue. If you can find a way to do it in a single loop, you'll get a pretty big boost.

Answer 3

In addition to the already existing answers I thought it be wise to add some things they may indirectly affect your application's performance. What I mean is these suggestions don't necessarily help your performance but they can make it a lot easier to understand and debug your program a lot easier (both you and others). This can allow you to evaluate the performance much easier and faster.

Naming

happyState doesn't quite tell me anything about what it's purpose is other than determining if the state is 'happy'. Something like plantsDying or plantsHaveDied is much more clear in its purpose. Which you already have a variable for so why not use it and subtract the final day before you print (or even after the loop).

Hungarian Notation is quite unnecessary additionally you're only using it for two variables. lstPlants is just as clear in its use and purpose as plants (as the 's' implies a collection) your functions and classes shouldn't be so long that you need such a naming scheme.

Intuitive

Try to keep your code as intuitive as possible so that others (or you 6+ months later) can understand it quickly. These suggestions might just be me but I think at the least they can demonstrate what I mean.

The goal is to compare the plant to the one at its left. So why not start at the second and go until you've reached the end? Here is some pseudo-code to demonstrate/explain what I mean about intuitive code:

LinkedListNode<int> currentNode = lstPlants.First;
LinkedListNode<int> lastNode = lstPlants.Last;

while (!plantsDied) // Your happyState and plantsDied variables are almost identical. happyState isn't clear so let's remove it and just use plantsDied.
{       
    plantsDied = false; 
    lastNode = lstPlants.Last; // Notice you're caching the value every time but your while-loop isn't even using it. Make use of it or get rid of it to reduce clutter.

    // Process the day
    bool dayProcessed = false; // You could remove this boolean and switch the following while-loop to a do-while-loop (bottom decision loop).
    while (!dayProcessed)
    {
        // Don't stop for the day until all nodes have been evaluated.
        dayProcessed = currentNode == lastNode;
        currentNode = currentNode.Next;

        // Compare the item to the one to its left.
        if (currentNode.Value > currentNode.Previous.Value)
        {
            plantsDied = true;
            currentNode = currentNode.Next;
            lstPlants.Remove(currentNode.Previous);
        }
    }

    // Also consider intuitive naming.
    // numberOfDays -> Count
    // daysPassed -> Count - 1 which is what you want to print.
    // So to be accurate you'd need to moved daysPassed to the bottom of the loop but I think it makes more sense that way.
    // Another benefit of this is that you're not doing that if-statement every single "day" reducing the overall cost of your program, instead it solves it more intuitively by removing the issue before it becomes one.
    daysPassed++;
}

OOP

Object-Orientation when done right can help make your code quite a bit more readable and intuitive. This is effectively how I structured my code when I did the exercise myself.

Main

• Input - Retrieve the input from a file or the user.
• Garden - Create the garden and send the signal to simulate the number of days until the plants stop dying.
• Output - Write the number of days passed to the user.

Plant

• Number - Not really necessary but I used it for debugging and overriding the ToString method to display it as (P, N) as the exercise does.
• PesticideRating - Long but descriptive name.

Garden

• Plants - Your data-structure representing the garden of plants. In your case the LinkedList in my case it was two queues.
• Functions - Actions the garden can execute. e.g. ProcessDay (inner-loop) and GetDaysPassedUntilStable (outer-loop).

Sometimes it seems unnecessary when you're doing OOP in a scenario in which you could easily do it all in one function but it helps significantly when debugging, reading, or maintaining (or in this case when other's are reviewing your code :D).

Answer 4

I am assuming you are going for the LinkedList way just to be able to check if the plant to left has some min value (as implemented by currentNode.Next.Value > cValue). But for an integer linked list overhead may be more than whats worth. Just use List, and use currentNode as index, you can still test list[currentNode+1] > cValue with few additional checks for making sure your curentNode is not the last element. Even now you are creating a list and throwing it away in the LinkedList initializer.