Poisonous Plants | Solution | Explanation | C++

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.

Solution

The solution uses a stack to track plants and determine the maximum number of days until no more plants die. Here's how it works:

Setup: A stack stores pairs of (index, span), where span is the number of days a plant will take to die. ans tracks the maximum days.
Iteration: For each plant v[i]:
- Start with cnt = 1 (minimum days require for current plant to die).
- While the stack isn’t empty and the top plant’s pesticide level is ≥ v[i], pop it and update cnt to reflect the chain of deaths (adding 1 to the popped plant’s span). The plant on the left will die first.
- If the stack empties, set cnt = 0 (no left neighbor).
- Update ans with the maximum cnt and push the current plant onto the stack.
Sample Walkthrough: For [6, 5, 8, 4, 7, 10, 9]:
- Day 1: Plants 8, 7, and 10 die, leaving [6, 5, 4, 9].
- Day 2: Plant 9 dies, leaving [6, 5, 4].
- The stack computes this as a chain, yielding ans = 2.
Complexity: O(n) time and space, as each plant is pushed/popped once.

int solve(vector<int> v)
{

  stack<pair<int, int>> st;
  int ans = 0;
  vi span(v.size(), -1);

  for (int i = 0; i < v.size(); i++)
  {
    int cnt = 1;
    while (!st.empty() && v[st.top().first] >= v[i])
    {
      cnt = max(cnt, st.top().second + 1);
      st.pop();
    }
    if (st.empty())
      cnt = 0;
    ans = max(ans, cnt);
    st.push({i, cnt});
  }

  return ans;
}


#include <bits/stdc++.h>

using namespace std;

#define int long long int
#define F first
#define S second
#define pb push_back
#define si set<int>
#define vi vector<int>
#define pii pair<int, int>
#define vpi vector<pii>
#define vpp vector<pair<int, pii>>
#define mii map<int, int>
#define mpi map<pii, int>
#define spi set<pii>
#define endl "\n"
#define sz(x) ((int)x.size())
#define all(p) p.begin(), p.end()
#define double long double
#define que_max priority_queue<int>
#define que_min priority_queue<int, vi, greater<int>>
#define bug(...) __f(#__VA_ARGS__, __VA_ARGS__)
#define print(a)      \
  for (auto x : a)    \
    cout << x << " "; \
  cout << endl
#define print1(a)  \
  for (auto x : a) \
  cout << x.F << " " << x.S << endl
#define print2(a, x, y)       \
  for (int i = x; i < y; i++) \
    cout << a[i] << " ";      \
  cout << endl
#define scanit(a, n)                           \
  for (ll indexaa = 0; indexaa < n; indexaa++) \
    cin >> a[indexaa];

inline int power(int a, int b)
{
  int x = 1;
  while (b)
  {
    if (b & 1)
      x *= a;
    a *= a;
    b >>= 1;
  }
  return x;
}

template <typename Arg1>
void __f(const char *name, Arg1 &&arg1) { cout << name << " : " << arg1 << endl; }
template <typename Arg1, typename... Args>
void __f(const char *names, Arg1 &&arg1, Args &&...args)
{
  const char *comma = strchr(names + 1, ',');
  cout.write(names, comma - names) << " : " << arg1 << " | ";
  __f(comma + 1, args...);
}

const int N = 200005;

int solve(vector<int> v)
{

  stack<pair<int, int>> st;
  int ans = 0;
  vi span(v.size(), -1);

  for (int i = 0; i < v.size(); i++)
  {
    int cnt = 1;
    while (!st.empty() && v[st.top().first] >= v[i])
    {
      cnt = max(cnt, st.top().second + 1);
      st.pop();
    }
    if (st.empty())
      cnt = 0;
    ans = max(ans, cnt);
    st.push({i, cnt});
  }

  return ans;
}

int32_t main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);

  clock_t z = clock();

  int t = 1;
  cin >> t;
  vector<int> p(t);
  for (int i = 0; i < t; i++)
    cin >> p[i];
  cout << solve(p);

  return 0;
}

Solution

Raunit Verma

CodingKaro