Hacker Rank - Poisonous Plants

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

LinkedListNode lastNode = lstPlants.Last;
LinkedListNode 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

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

StackExchange Code Review Q#104544, answer score: 8