Poisonous Plants| Stack
TASK(hard)
There are a number of plants in a garden. Each of the plants has been treated with some amount of pesticide. After each day, if any plant has more pesticide than the plant on its left, being weaker than the left one, it dies. You are given the initial values of the pesticide in each of the plants. Determine the number of days after which no plant dies, i.e. the time after which there is no plant with more pesticide content than the plant to its left.
Example
p=[3,6,2,7,5] // pesticide levels
Use a 1-indexed array. On day 1, plants 2 and 4 die leaving p’=[3,2,5]. On day 2, plant 3 in p’ dies leaving p”=[3,2]. There is no plant with a higher concentration of pesticide than the one to its left, so plants stop dying after day .
Function Description
Complete the function poisonousPlants in the editor below.
poisonousPlants has the following parameter(s):
- int p[n]: the pesticide levels in each plant
Returns
- int: the number of days until plants no longer die from pesticide
Input Format
The first line contains an integer , the size of the array .
The next line contains space-separated integers .
Constraints
1.1<=n<=105
2.0<=p[i]<=109
Sample Input
7
6 5 8 4 7 10 9
Sample Output
2
SOLUTION 1
def poisonousPlants(p):
mday,s = 0, []
for i in p:
if not(s) or i <= s[0][0]:
s=[[i,0]]
elif i > s[-1][0]:
s.append([i,1])
else:
d = 1
while s and i <= s[-1][0]:
d = max(d, s.pop()[1]+1)
s.append([i,d])
mday = max(mday,s[-1][1])
return mday
SOLUTION 2
def poisonousPlants(p):
# Write your code here
day=0
stack=[]
for i in range(len(p)):
if i==0: stack.append((p[i],0))
elif p[i]>stack[0][0] :
if p[i]>stack[-1][0]: stack.append((p[i],1))
else:
ld=1
while stack and p[i]<=stack[-1][0]:
ld = max(ld, stack[-1][1]+1)
stack.pop()
stack.append((p[i],ld))
else:
stack=[(p[i],0)]
day=max(day,stack[-1][1])
#print("Elements of stack are: ", stack)
return day
1. Initialize Data Structures:
- Use a stack (stack) to keep track of the plants that have not died yet.
- Use an array (days) to store the number of days each plant will survive.
2. Iterate Through Plants:
- Traverse through each plant in the array.
- For each plant:
- Check if the current plant's pesticide level is greater than the pesticide level of the plant at the top of the stack (stack[-1]).
- If it is greater, it means the current plant will die the next day (days[i] = days[stack[-1]] + 1).
- Push the current plant's index onto the stack.
3. Update Maximum Days:
- Keep track of the maximum number of days required (max_days) by comparing days[i] with max_days.
4. Output the Result:
- The maximum number of days (max_days) gives the number of days until all plants are dead due to higher pesticide levels.
