We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
I passed all the test cases and am interested to share the general algorithm I used. A very good starting point is to read on "the stock span problem", understanding the solution to this problem gives >80% of the solution I have here.
A lot of discussions mentioned about finding the potential killer of each plant by using stack, scanning from right to left. I am not sure how they do this, because my scan is left to right.
Okay, with the stock span problem understanding, now we can discuss the step in the algorithm. The explanation here is developed from step by step insights that I get while working on the problem.
read in the data as an array/list (I used java)
Here is the hardest part, use the stock span problem algorithm to find the "killer" array. For a plant that will survive to the end, mark the killer as -1. Let me give an example, an array plant of [1, 4, 7, 6, 2]. The array that represent the killer would be [-1, 0, 1, 1, 0]. Note the killer[0] = -1, since the first element will always survive, killer[1] = 0, since the second element 4 will be killed by the first element 1, killer[3] = 1, since the fourth element 6 will be killed by second element 1.
The key here is to use the stack, as shown in stock span problem. The stack keep the indices of latest killers (well, technically, all indices will be pushed to the stack once, but it will be popped soon after it is pushed, again, please read the stock span problem first and understand it well).
After you obtained the killer array, you will realize that you can infer the days needed for the killer to kill all the victims. For example, a killer array of [-1, 0, 0, 1, 1, 0], where all plants are killed by either the first or second element. Since there are 3 zeros here, it mean plant[0] need at least 3 days to kill them.
Here comes another tricky part, the kill count in part 4 only tell us the lower bound. But what we need is the exact days, and sometimes some plant has to wait for another plant to die before being killed itself. Any plant that is going to be killed by index i always need to wait until all the plants killed by index j>i done their jobs. For example, a killer array of [-1, 0, 1, 1, 0], plant[1] need 2 days to kill its victim. Only after 2 days, then the last element can be killed by plant 0. Thus you should get 3 days instead 2 in the solution!
Now what's left is to implement insight in part 5. To do it in O(n) time, we can augment the stack of indices with max day needed. I kind of hack this through, by noticing that I should track the max day whenever I pop an element from a stack, or whenever I add a maxday for every kill happen. This is easier than other parts.
Poisonous Plants
You are viewing a single comment's thread. Return to all comments →
I passed all the test cases and am interested to share the general algorithm I used. A very good starting point is to read on "the stock span problem", understanding the solution to this problem gives >80% of the solution I have here.
A lot of discussions mentioned about finding the potential killer of each plant by using stack, scanning from right to left. I am not sure how they do this, because my scan is left to right.
Okay, with the stock span problem understanding, now we can discuss the step in the algorithm. The explanation here is developed from step by step insights that I get while working on the problem.
Hope this help!