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.
  1. Prepare
  2. Data Structures
  3. Stacks
  4. Poisonous Plants
  5. Discussions

Poisonous Plants

Sort by

recency

|

293 Discussions

|

  • CYS1B_1720109
     + 0 comments

    Python3 Solution:

    #!/bin/python3

import math
import os
import random
import re
import sys

#
# Complete the 'poisonousPlants' function below.
#
# The function is expected to return an INTEGER.
# The function accepts INTEGER_ARRAY p as parameter.
#

def poisonousPlants(p):
    # Write your code here
    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

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    n = int(input().strip())

    p = list(map(int, input().rstrip().split()))

    result = poisonousPlants(p)

    fptr.write(str(result) + '\n')

    fptr.close()

  • vvce23cseaiml007
     + 0 comments

    Solution in C

    int poisonousPlants(int p_count, int* p) {
     int rounds=0;

    int* tstack=(int*)malloc(p_count * sizeof(int));
    int tstack_cnt=0;
    tstack[0]=p[0];

    for (;;)
    {    
        tstack_cnt=1;

        for (int i=0;i<p_count-1;i++)
            if (p[i]>=p[i+1])
                tstack[tstack_cnt++]=p[i+1];
            
        if (tstack_cnt==p_count)
            return rounds;
        rounds++;
        memcpy(p,tstack,tstack_cnt*sizeof(int));
        p_count=tstack_cnt;
    }


}

  • dehaka
     + 0 comments

    wow hard question. couldnt figure out how to do it until i learned the previous greater element algo from copilot, very straightforward modification of that algo, ask copilot for it

    O(n)

    int poisonousPlants(const vector<int>& plant) {
    int days = 0;
    vector<int> life(plant.size(), 1);
    life[0] = INT_MAX;
    stack<int> S;
    S.push(0);
    for (int i=1; i < plant.size(); i++) {
        while (life[i] > life[S.top()] or (plant[i] <= plant[S.top()] and life[S.top()] != INT_MAX)) {
            life[i] = max(life[i], life[S.top()] + 1);
            S.pop();
        }
        if (plant[i] <= plant[S.top()] and life[S.top()] == INT_MAX) life[i] = INT_MAX;
        if (life[i] != INT_MAX) days = max(days, life[i]);
        S.push(i);
    }
    return days;
}

  • dellvecchio
     + 0 comments

    My Solution in Python using Dynamic Programing

    def poisonousPlants(p):
    vet = [float('inf')]*len(p)
    ind = [-1]*len(p)
    aux = 0
    dias = 0
    for i in range(1, len(p)):
        j = i - 1
        Achou = False
        aux = 0
        while not Achou:
            if p[j] >= p[i]:
                if vet[j] == float('inf'):
                    Achou = True
                else:
                    aux = vet[j]
                    j = ind[j]
            else:
                if vet[j] > aux:
                    vet[i] = aux + 1
                    dias = max(dias, vet[i])
                    ind[i] = j
                    Achou = True
                else:
                    j = ind[j]
    return dias

  • danielali1999
     + 1 comment

    Passing all test cases but exceeding time limit (~5 sec runtime) in a few. Could someone suggest an alternative approach or improvements to my current solution (C#)?

        public static int poisonousPlants(List<int> p)
    {
        int days = 0;
        List<int> plants = p.ToList();
        bool finalDay = false;
        do
        {
            int pCount = p.Count;
            for (int i = 1; i < pCount; i++)
            {
                if (p[i - 1] < p[i]) plants.RemoveAt(i - (pCount - plants.Count));
                if (i == pCount - 1)
                {
                    if (p.SequenceEqual(plants)) finalDay = true;
                    else days++; p = plants.ToList();
                }
            }
        } while (!finalDay && p.Count > 1);
        return days;
    }