# Poisonous Plants

# Poisonous Plants

w00tles + 12 comments it can be done with a list of stacks*

let's say we start with

`6 5 8 7 4 7 3 1 1 10`

we'll represent it as a list of stacks like this:

**monday**`6>5, 8>7>4, 7>3>1>1, 10`

each stack is a maximal non-increasing chain

now, to let one day pass:

- pop the top element from every stack (excluding the unique leftmost stack). these are the plants that die on this day.

**tuesday**`6>5, 7>4, 3>1>1, -`

- now check to see if any adjacent stacks can be merged. here we see that
`7>4`

and`3>1>1`

can be merged to form a longer chain. stacks can be merged in O(1)

**tuesday**`6>5, 7>4>3>1>1`

- one day has now passed. repeat the process.

**wednesday**`6>5, 4>3>1>1`

**wednesday**`6>5>4>3>1>1`

- now that just one stack remains in our list, we know we are done.

*NB these stacks are linked-list-based and maintain a pointer to their base element. This allows for O(1) merge operations, and O(1) checking of the top and bottom values.*t_tahasin + 0 comments Nice and different way to approach the problem. I followed your algorithm to solve the problem using Java LinkedList and list iterator which works perfect. Thank you. :)

yousuf_1991 + 0 comments This should be the editorial

dnll2000 + 0 comments nice explanation! I had a similar implimentation with two lists: the original plants are in the first list; the "stack heads" are in the second list; each day I iterate over the head list, erasing he plants from the plant list.

ketkigarg + 0 comments Great logic. But since N can go upto 100000, in worst-case(i.e all elements in ascending order) it requires 100000 creation of stack objects.

f20140006 + 0 comments thank you for sharing your approach, it indeed is a very good approach, the number of stacks might be a problem but it still works for almost all the cases but getting this kind of idea is cool.

akashpratik999 + 0 comments give the code please. @w00tles

ACanSolak + 0 comments Thanks for the very nice approach. Few implementation notes:

-Check for no-plants-die case.

-For each day first pop the top elements and then check for merging instead check for merging in the beginning of the day.

rishabh0_9 + 0 comments Can you show the code please ?

devinludwig + 0 comments Here's my Ruby implementation:

def poisonousPlants(p) i=0 while p[i] p[i] = [p[i]] if p[i-1] and p[i-1][-1] >= p[i][0] p[i-1] += p[i]; p.delete_at i else i+=1 end end i, days = 1, 0 while p[i] p[i].shift if p[i].empty? p.delete_at i elsif p[i-1] and p[i-1][-1] >= p[i][0] p[i-1] += p[i] p.delete_at i else i += 1 end i = 1 and days += 1 unless p[i] end days end

Draj89 + 0 comments Thank you for the algorithm. what is the order of complexity of this algorithm?

yanikjay1 + 0 comments Sorry, but could someone please explain the runtime associated with this and why? Thanks!

hryash10 + 0 comments How do you understand when to merge? What is the condition for merging ?

purnawirman + 5 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.

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

Hope this help!

love1024 + 0 comments How to use killer array to find max days.I am not getting it.Can you please help?

shuhua_gao + 2 comments Just to supplement purnawirman's algorithm explanation. http://algorithmsandme.in/2014/02/stacks-stock-span-problem/ This page gives an excellent illustration of the "stock span problem". This problem is similar to the stock span problem, but more complicated. The following is my C++ code, which passed all the test cases. Just for reference.

`struct Node { int plantID; // we label plants from 0 to N - 1 int daysToDie; // the days a plant needs to die, -1 means it will not die }; int main() { std::vector<int> pesticides; int N; std::cin >> N; for (int i = 0; i < N; i++) { int pesiticide; std::cin >> pesiticide; pesticides.push_back(pesiticide); } std::stack<Node> s; s.push({ 0, -1 }); int maxDaysToDie = -1; // the max days needed to die among all the plants for (int i = 1; i < N; i++) { // we only care about the plants whose pesticide is smaller (potential killer) int daysToDie = 1; while (!s.empty()) { if (pesticides[s.top().plantID] >= pesticides[i]) { // need to wait the front plants to die, like "1 5 4", 4 will die only after 5 died daysToDie = std::max(daysToDie, s.top().daysToDie + 1); s.pop(); } else // find the killer { break; } } if (s.empty()) // this means no preceding plants have less pesticide than ith plant { daysToDie = -1; } maxDaysToDie = std::max(maxDaysToDie, daysToDie); s.push({ i, daysToDie }); } std::cout << (maxDaysToDie < 0 ? 0 : maxDaysToDie) << std::endl; return 0; }`

satk123 + 0 comments isn't it a dp solution?

153J1A0592 + 0 comments HIII

nickdu + 1 comment I'm a bit confused over your explanation of the killer array. With pesticide values of [1, 4, 7, 6, 2] you get:

after day 1:

[1, 6, 2] -> 4 was killed by 1 and 7 was killed by 4. (mentioning values not indexes)

after day 2:

[1, 2] -> 6 was killed by 1.

after day 3:

[1] -> 2 was killed by 1.

Yet you say 6 was killed by 4 (the second element)

Oh_Dear_God + 0 comments I have same confusion.

h1290645535 + 0 comments I use this method and find some problems, but I've got them fixed :). Here is my C++ solution, which has passed all the test cases.

int n; cin >> n; int *p = new int [n]; for(int i=0;i<n;i++) cin >> p[i]; stack<int> st; int *killer = new int [n];//which killed i int *daycount = new int [n];//how long i can exist int *killcount = new int [n];//how many i killed for(int i=0;i<n;i++) { daycount[i] = 0; killcount[i] = 0; } for(int i=0;i<n;i++) { while(!st.empty() && p[i]<=p[st.top()]) st.pop(); if(st.empty()) { killer[i] = -1; daycount[i] = -1; } else { killer[i] = st.top(); killcount[killer[i]]++; daycount[i] += killcount[killer[i]]; daycount[st.top()]--; if(killer[st.top()]>=0 && daycount[st.top()]<=0) st.pop(); } st.push(i); } int max = -1; for(int i=0;i<n;i++) if(max<killcount[i]) max = killcount[i]; cout << max << endl; return 0;

Oh_Dear_God + 0 comments [deleted]

phillm6 + 2 comments Thanks to all the people who posted. Getting pointed toward the stock span algorithm was very helpful (thanks purnawirman).

I would, though, like to offer my own explination, partly to give help without giving out a solution (so people can have the satisfaction of at least partially solving it themselves).

My first algorithm was brute force working on a linked list. Obviously this took worst case O(n*k) where k was the number of days (it only timed out on 5 cases) because linked list removal is O(1).

The root intuition behind my final (successful) algorithm was that each 'flower' only has to know the number of days it will take the longest lived flower to die between him and his killer.

Take [1, 5, 4]: 1 will never die (call that day 0), so 5 sees that 1 will kill him and knows he'll die on day 1, so 5 says, I die on day one. Then 4 looks at five and says you won't kill me, what day do you die on? 4 learns that 5 dies on day 1 so he knows he'll die on day 2 at the earliest. 5 no longer has useful information for anyone, so he can go enjoy his twilight hours. 4 looks at one and says, ah, you'll kill me, so I die on day 2.If a number doesn't find a killer, he obviously doesn't die. So he jumps on the (now empty) stack with his 0.

Careful though about equal numbers. Also, my final algorithm (just the primary function) was only 13 lines, so if you're doing a lot of fancy stuff it might be confusing you more than helping.

Also, the algorithm has to look at every number at least once, and, though there is a stack and while loop that could remove many elements on any single run (a couple hints there too), each element will be pushed exactly once and popped at most once [each being O(1)]. Therefore, the final algorithm is O(n).

Rakesh902 + 0 comments please can you post the code for this explanation

vipulvikram3499 + 0 comments Thanks. Nice Appoach..

sanket1549 + 6 comments Below code works perfectly

`int main() { int n; cin>>n; int* p = new int[n]; for(int i=0;i<n;i++) cin>>p[i]; int* days = new int[n](); int min = p[0]; int max = 0; stack<int> s; s.push(0); for(int i=1;i<n;i++) { if(p[i] > p[i-1]) days[i] = 1; min = min < p[i]?min:p[i]; while(!s.empty() && p[s.top()] >= p[i]) { if(p[i] > min) days[i] = days[i] > days[s.top()] + 1?days[i]:days[s.top()] + 1; s.pop(); } max = max>days[i]?max:days[i]; s.push(i); } cout<<max<<endl;`

}

adityaknegi + 0 comments can you explain logic ??? Thanks

AkashRaghav + 0 comments Hi, your code does work but can you please explain your method / algorithm.?

nminhtu94 + 0 comments What he's trying to do is that: everytime we update the min, those min(s) are the plans that survive. All the plants between the min(s) will eventually die (so he only updates those p[i] > min). The first "if" statements is obvious. For those plans that between 2 min(s) segment:

- In order for p[i] to be killed, all the plans p[j] >= p[i] before i must be killed first. So p[i] must wait until the last p[j] is killed. The stack is used to keep track of those that are larger than p[i] before it :).

enss + 3 comments python version:

N = int(input()) p = list(map(int, input().split(' '))) days = [0] * N s = [0] mi = p[0] ma = 0 for i in range(1, N): if p[i] > p[i - 1]: days[i] = 1 mi = min(mi, p[i]) while s and p[s[-1]] >= p[i]: if p[i] > mi: days[i] = max(days[i], days[s[-1]] + 1) s.pop() ma = max(ma, days[i]) s += [i] print(ma)

Sentinal_prime + 0 comments i am new in programing ,can you please explain logic behind this.

avsingh999 + 0 comments can you explain your algorithm ????

muneebaadil + 5 comments My code is giving wrong answer on test cases 12, 20, 21, 23. I don't know what exception I am missing in my logic building, but since the test case is very large, I cannot possibly trace my code on that test case. Can someone please find a bug in my code?

int main(){

`unsigned long int totalplants; cin>>totalplants; unsigned long long int* plants; plants = new unsigned long long int [totalplants]; for (int i = 0; i < totalplants; i += 1) { cin>>plants [i]; } stack <unsigned long long int> plantsdata; unsigned long int maxdays = 0; for (int i = totalplants - 1; i >= 0; i -= 1) { if (plantsdata.empty() or plants[i] >= plantsdata.top()) plantsdata.push(plants[i]); else { unsigned long int currentdays = 0; while (not plantsdata.empty() and plants[i] < plantsdata.top()) { currentdays += 1; plantsdata.pop(); } if (currentdays > maxdays) maxdays = currentdays; plantsdata.push(plants[i]); } } cout<<maxdays; return 0;`

}

minorblend + 1 comment have you found the bug? I've got "wrong answer" on the same test cases. :(

shilay + 2 comments 1 3 5 2 7 6 4 2 1 have you tried this test case

coder_17 + 0 comments thanks it really helped :)

himanshurawlani + 1 comment The answer to it is 4, right?

thebick + 0 comments - 1<3, 3<5, 2<7; leaving 1 2 6 4 2 1
- 1<2, 2<6; leaving 1 4 2 1
- 1<4; leaving 1 2 1
- 1<2; leaving 1 1 and nothing more happens

vegichan + 0 comments same issue here....

IGonza + 3 comments Try

34

403 1048 15780 14489 15889 18627 13629 13706 16849 13202 10192 17323 4904 6951 16954 5568 4185 7929 8860 14945 3764 4972 13476 14330 1174 18952 10087 10863 9543 12802 1607 9354 13127 920 Answer should be 10

thebick + 0 comments [deleted]ShubhamV06 + 0 comments why is it 10? Please explain

DarkSun27 + 0 comments Done!

Tuxdude + 3 comments Try this case, it will fail for your algorithm:

8 6 5 8 4 7 10 9 5

You're using the wrong algorithm of just scanning from Right to Left, which has apparently been mentioned by someone incorrectly in the discussion here. Apparently this broken algorithm does pass most of the test cases except the 4 pointed. :)

Instead try iterating from left to right over each plant, and calculate when each plant will die. To calculate when a plant will die, find the plant which can potentially kill it. This requires only the past information, by scanning towards the left. Using a stack here will help you with the leftwards scan.

IGonza + 1 comment It does not sound like O(n).

Tuxdude + 0 comments It is

`O(n)`

because you look at each element at most twice, once while pushing it on the stack (L to R) and once when popping from the stack (for scanning R to L). Once elements are popped off the stack, they're not inspected any more.

akshaymuley + 1 comment 8 6 5 8 4 7 10 9 5

What is expected O/P for above test case. Mine is giving 2, is this right?

thebick + 0 comments Day 0: 6 5 8 4 7 10 9 5 (I'm guessing the first 8 is the # of entries)

Dying on day 1: 8 > 5, 7 > 4, 10 > 7

After day 1: 6 5 4 9 5

Dying on day 2: 9 > 4

After day 2: 6 5 4 5

Dying on day 3: 5 > 4

After day 3: 6 5 4 and no more deaths

alexeyg + 0 comments Iterating from right to left works. But one needs to take care of only killing those plants that are killable (i.e. exposed to a plant with lower pesticide levels) at a given point in time (and "waiting" until the plant become killable).

xialin + 0 comments My algorithm failed the same test cases. And I found a counter case that can fail mine: 1 3 5 2 7 6 4 2 1

raviok + 1 comment You can indeed walk right to left in O(N). The logic is to find the maximum number of items that accumulate beyond day1, but can be ultimately removed. Here is the implementation:

`Scanner sc = new Scanner(System.in); int[] ar = new int[sc.nextInt()]; for (int i =0; i < ar.length; i++){ ar[i] = sc.nextInt(); } Stack<Integer> st = new Stack<Integer>(); int i = ar.length-1; boolean day1 = false; int maxsize = 0, minsize = 0, days = 0; while (i >= 0) { while (i > 0 && ar[i] > ar[i-1]){ i--; day1 = true; } // TODO Setup your maxsize and minsize while (st.size() > 0 && ar[i] < st.peek()) st.pop(); // TODO Calc days st.push(ar[i--]); } System.out.println(days + (day1 ? 1 : 0));`

abhinav_90 + 2 comments Hi ravi,

I find your solution very close to mine, can you please look into my solution and say if i made any mistake.

I will be curious to know if you got the solution for 23rd input right (Ans 80802)

import java.io.*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*; public class Solution { public static void main(String[] args) { Scanner in = new Scanner(System.in); LinkedList<Integer> list = new LinkedList<>(); LinkedList<Integer> stack = new LinkedList<>(); int plants = in.nextInt(); for(int i =0 ; i < plants; i++){ list.push(in.nextInt()); } stack.push(-1); int days =0 ;int temp; while(!list.isEmpty()){ int curr = list.pop(); temp =0; while(stack.peek() > curr){ stack.pop(); temp++; } stack.push(curr); if(temp > days) days = temp; } System.out.println(days); } }

raviok + 0 comments Two issues: 1. At each iteration, you need to eliminate the "day 1" plants from the "list" variable before you look in the "stack" 2. Your temp variable is losing history - it needs to account for how big the stack had gotten and by how much it went down (you are only doing the latter)

taruna_kukreja + 1 comment [deleted]taruna_kukreja + 0 comments [deleted]

josemontesp + 1 comment Here is a solution in Javascript and with comments: Passes all tests

credits to ydvimalrajdy for the algorithm

function processData(input) { // Input parsing input = input.split('\n'); input.shift(); //n var plants = input.shift().split(' ').map(p=>parseInt(p)); //Solution var maxDaysAlive = 0; var stack = []; // We keep in the stack the possible // killers for plants that we haven't seen yet. for (var i = 0; i < plants.length; i++){ var daysAlive = 0; // Number of days the plant[i] will survive while(stack.length > 0 && plants[i] <= stack[stack.length - 1].plant) daysAlive = Math.max(daysAlive, stack.pop().days); // The daysAlive for plant[i] is the max // days of all the plants greater than plant[i] // that are in the stack (possible killers) because // they all need to die before plant[i] dies. // Later we add 1 because it dies after the // other plants have died. // when plant[i] is the minimum seen until now. // It will never die. if (stack.length === 0) daysAlive = 0; // plant[i] will die, because it exited the while // loop and a lower plant was found else daysAlive += 1; maxDaysAlive = Math.max(maxDaysAlive, daysAlive); // plant[i] is a possible killer because there // may be plants greater than this that we have // not seen yet stack.push({ plant: plants[i], days : daysAlive }); } console.log(maxDaysAlive); }

eric2013 + 0 comments Nice, simple and fast.

My python version executes in 0.16s for the longest test case(10s allowed).

beat1Percent + 0 comments It can be solved by using stack. Let's take a look at the example below: 1,10,9,2,8,7,6,5,4,3. After 2 days, it will become 1,2,6,5,4,3. After 4 more days, it will become 1 and no more dying. One thing we can notice for a plant at idx

`i`

, if the left one at`i - k`

is smaller than`i`

, it can eliminate all the plants the`i`

can eliminate. Also, a plant can finally eliminate all the plants has more pesticide(greater value) on its right hand side. So if we know how many days a plant at idx`i`

, we can know how many days the left plants need to eliminate the plants. Below is a concise Java solution, which better explains the idea:static class Pair { int val, count; public Pair(int val, int count) { this.val = val; this.count = count; } } // Complete the poisonousPlants function below. static int poisonousPlants(int[] p) { Stack<Pair> stack = new Stack<>(); int cnt = 0; for (int i = p.length - 1; i >= 0; i--) { int temp = 0; while (!stack.empty() && p[i] < stack.peek().val) { temp++; Pair pair = stack.pop(); temp = Math.max(temp, pair.count); } cnt = Math.max(cnt, temp); stack.push(new Pair(p[i], temp)); } return cnt; }

chanchalkhemani + 2 comments My code passes all test cases except for test cases 19 and 23. It gives timeout for those 2 cases. Please suggest an optimized solution.

long n, temp; vector<long> v; cin >> n; for(long i=0; i<n; i++){ cin >> temp; v.push_back(temp); } int die_count=1, days=0; while(die_count>0){ die_count = 0; for(long i=v.size()-1; i>0; i--){ if(v[i] > v[i-1]){ v.erase(v.begin()+i); die_count++; } } if(die_count>0) days++; } cout << days << endl;

shaktigusain29 + 1 comment same here!! found any solution yet??

chanchalkhemani + 1 comment not yet :(

shaktigusain29 + 1 comment found the solution. try to start iterating where the first plant died and end where the last one died for the previous day.

chanchalkhemani + 1 comment still couldn't solve the timeout error.

shaktigusain29 + 1 comment this is the code i used to pass all cases. Its in java though.

import java.util.ArrayList; import java.util.Scanner;

public class PoisonousPlants {

`public static void main(String[] args) { // TODO Auto-generated method stub Scanner scn = new Scanner(System.in); ArrayList<Integer> list= new ArrayList(); ArrayList<Integer> stack= new ArrayList(); int n=scn.nextInt(); for(int i=0;i<n;i++){ list.add(i,scn.nextInt()); } int flag=0;int count=0;int days=0;int min=1,max=list.size()-1;int last=0;; boolean first; do{ flag=0; first=true; for(int i=min;i<=max-count&&i<list.size();i++){ if(list.get(i)>list.get(i-1)){ stack.add(i); flag=1; if(first==true) { min=i; first=false; } last=i; } } max=last+1; count=0; while(!stack.isEmpty()){ int z=stack.get(0); list.remove(z-count); stack.remove(0); count++; } days++; }while(flag!=0); System.out.println(days-1); }`

}

pooja_kanchan + 0 comments I used similar approach, but getting TLE. Btw it took me a while to understand your code, until I saw stack is actually an ArrayList ;)

amuchand47 + 0 comments same here ... any solution to 19 and 23 cases ??

vikashkumar1003 + 0 comments Hi,

I getting timout for some of the test cases(22,23). please correct where i am wrong.

public class Solution {

`public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); ArrayList<Integer> arr_plant = new ArrayList<Integer>(); for (int i = 0; i < n; i++) { arr_plant.add(sc.nextInt()); } int result = 0; int days = 0; int length = arr_plant.size() - 1; while (result ==0) { ArrayList<Integer> stack = new ArrayList<Integer>(); int j=0; stack.add(arr_plant.get(0)); result=1; for (int i = 0; i < length; i++) { if (arr_plant.get(i) > arr_plant.get(i + 1) || arr_plant.get(i) == arr_plant.get(i + 1)) { stack.add(arr_plant.get(i + 1)); j++; } else if (arr_plant.get(i) < arr_plant.get(i + 1)) result = 0; } if(result==0){ days++; } arr_plant = (ArrayList<Integer>) stack.clone(); length = j; } System.out.println(days); }`

}

Sort 147 Discussions, By:

Please Login in order to post a comment