Hacker Rank - Poisonous Plants
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 &lt; j &lt; 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)\$.