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

  • 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;
}