How do you solve Poisonous Plants using the Brute Force — Day-by-Day Simulation approach?

When to use it: State it to lock down the rules (strict >, simultaneous deaths), then reject it on the O(n²) cost for n = 10⁵. Simulate the literal process. Hold the current list of (pesticide) values. Each day: 1. **Mark** every index `i ≥ 1` with `p[i] > p[i-1]`, reading from the *start-of-day* list so that deaths are simultaneous (a plant that will die can't shield the one to its right within the same day's evaluation, but it *was* there in the morning, so use the morning values). 2. **Compact** the list by keeping only unmarked plants. 3. If anything was marked, increment the day count and repeat; otherwise stop. **Why it's correct.** It mirrors the rules exactly, including simultaneity (mark first, delete after). **Why it's too slow.** Adversarial inputs (e.g. a long increasing run) kill only one or a few plants per day, so the number of days is O(n), and each day rescans the whole surviving list. The product is O(n²). The fix is to stop re-scanning and instead compute each plant's death day directly — which the monotonic stack does in one pass. Time complexity: O(n²) worst case. Space complexity: O(n).

Loading…

hardStack QueueFrequently asked

Poisonous Plants

Q: How do you solve Poisonous Plants using the Monotonic Stack of Death Days (Optimal) approach?

When to use it: The answer they want. Phrase it as 'compute each plant's death day in one pass with a non-increasing stack; the answer is the max'. Compute each plant's **death day** directly. **The recurrence.** Consider plant `i`. The plants immediately to its left with pesticide `≥ p[i]` are 'shields' — `i` cannot die while any of them is alive directly to its left, because it only dies against a *smaller* left neighbour. Once all those shields have died, `i`'s left neighbour becomes some smaller plant, and `i` dies the very next day. So `day[i] = 1 + max(day[shield])` over the contiguous run of `≥`-pesticide shields — **unless** there is no smaller plant beyond them (the run extends to the left end), in which case `i` is a permanent survivor with `day[i] = 0`. **Why a non-increasing stack captures the shields.** Walk left to right pushing indices. Before pushing `i`, pop every stack entry whose pesticide is `≥ p[i]`: those are exactly `i`'s shields (the chain of larger-or-equal plants directly preceding it). While popping, accumulate the maximum of their `day` values. After popping: - If the stack is **empty**, every plant to the left was `≥ p[i]`, so `i` becomes the new minimum and never dies → `day[i] = 0`. - Otherwise the stack top is a strictly smaller plant that survives long enough to expose `i`, so `day[i] = maxPoppedDay + 1`. Push `i` (with its `day`) and update the global answer. **Why it's correct and O(n).** The stack stays non-increasing, so each index is pushed and popped at most once — linear total work. The death-day recurrence exactly models the simultaneous-elimination dynamics: a plant's demise is gated by the latest-dying shield in front of it, plus one day. The maximum death day is the number of days with at least one death. Time complexity: O(n). Space complexity: O(n).

Stack & Queue · 17 of 17 · 11 min

There are n plants in a row, each treated with some amount of pesticide. After each day, any plant with more pesticide than the plant immediately to its left dies (these deaths all happen at the end of the day, simultaneously). When plants die, the remaining plants shift together so each plant's left neighbour may change for the next day.

Given the initial pesticide levels p, determine the number of days after which no plant dies (i.e., the number of days on which at least one plant dies).

In plain English

A plant dies the first day it finds itself immediately to the right of a strictly smaller alive plant. Initially that left neighbour is the original predecessor, but as plants die, a plant's left neighbour walks leftward to the nearest plant that outlived the ones in between. So a plant's death day is governed by the chain of larger-or-equal plants shielding it on the left: it can only die once all those shields have themselves died, and then one day later — provided some smaller plant remains further left. A monotonic stack tracks exactly that shielding chain, letting us compute every plant's death day in a single pass.

Examples

Example 1

Input: p = [6, 5, 8, 4, 7, 10, 9]
Output: 2
Note: Day 1: 8 (>5), 7 (>4), 10 (>7) die → [6,5,4,9]. Day 2: 9 (>4) dies → [6,5,4]. Day 3: no deaths. Two days saw deaths.

Example 2

Input: p = [3, 2, 5, 4]
Output: 2
Note: Day 1: 5 (>2) dies; 4 has left neighbour 5 (4<5) so it survives → [3,2,4]. Day 2: 4 (>2) dies → [3,2]. Day 3: no deaths. Two days saw a death.

Example 3

Input: p = [3, 2, 1]
Output: 0
Note: Strictly decreasing: every plant is ≤ its left neighbour, so no plant ever dies.

Example 4

Input: p = [1, 2, 3, 4]
Output: 1
Note: Each of 2, 3, 4 is strictly greater than its morning left neighbour, so all three die simultaneously on day 1, leaving [1]. Day 2 has no deaths → answer 1.

Constraints

1 ≤ n ≤ 10⁵
0 ≤ p[i] ≤ 10⁹ (pesticide levels; duplicates allowed)
A plant dies only if its pesticide is STRICTLY greater than its current left neighbour's
Deaths within a day are simultaneous; survivors compact before the next day
Return the number of days until a day occurs with zero deaths (0 if no plant ever dies)

Clarifying questions4First question: Does a plant die on equal pesticide, or only strictly greater?Explore questions

Q1.Does a plant die on equal pesticide, or only strictly greater?
Only strictly greater than the left neighbour. Equal pesticide does not kill — using ≥ instead of > is a classic off-by-one bug here.
Q2.Are deaths within a single day simultaneous or sequential?
Simultaneous. All plants that satisfy the kill condition against the morning's arrangement die together; you must not let one death change a neighbour mid-day.
Q3.Can a plant never die?
Yes. The first plant never dies (no left neighbour), and any plant that is ≤ every plant remaining to its left is a permanent survivor — its death day is 0.
Q4.What's returned — the last day with a death, or the first quiet day?
The number of days on which at least one plant dies, i.e. the maximum death day. If nothing ever dies, that's 0.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Each day, every plant whose pesticide level is strictly greater than the plant immediately to its left dies (all such deaths happen simultaneously); the survivors close ranks and the process repeats. Return the number of days until a day passes with no deaths. The O(n) trick is a monotonic (non-increasing) stack that, for each plant, computes the day it dies: pop all earlier plants with pesticide ≥ the current one, take the maximum death-day among them, and this plant dies one day later — unless the stack empties (no smaller plant survives to its left), in which case it never dies. The answer is the maximum death-day over all plants. O(n) time, O(n) space.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you avoid the O(n²) day-by-day simulation by recognising that each plant's death day can be derived in one pass with a monotonic stack, and whether you handle the 'strictly greater', 'simultaneous', and 'never dies' subtleties.

Where candidates slip

Simulating day by day (TLE at n = 10⁵), using ≥ instead of > for the kill condition, processing deaths sequentially within a day instead of simultaneously, or mishandling the stack-empties (never-dies) case.

How to stand out

Explain the death-day recurrence, why popping ≥-pesticide plants and taking their max death-day is correct, why an empty stack means a permanent survivor, and tie it to the nearest-smaller-element family.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Brute Force — Day-by-Day Simulation	`O(n²) worst case`	`O(n)`	State it to lock down the rules (strict >, simultaneous deaths), then reject it on the O(n²) cost for n = 10⁵.	Read
2	Monotonic Stack of Death Days (Optimal)Optimal	`O(n)`	`O(n)`	The answer they want. Phrase it as 'compute each plant's death day in one pass with a non-increasing stack; the answer is the max'.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewplant ismaller plant still to its left?No (stack empties)YesExplore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Brute Force — Day-by-Day Simulation

TimeO(n²) worst caseSpaceO(n)

State it to lock down the rules (strict >, simultaneous deaths), then reject it on the O(n²) cost for n = 10⁵.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Each day, scan the current list and mark every plant whose pesticide exceeds its immediate left neighbour — using the morning arrangement, so deaths are simultaneous.

2Hint 2Explore hint

Remove all marked plants at once to form the next day's list; increment the day counter if anything died.

3Hint 3Explore hint

Repeat until a day passes with no deaths. A long 'staircase' like [1,2,3,…,n] makes the survivor peel off slowly, giving O(n) days × O(n) work.

A · Core idea

Simulate the literal process. Hold the current list of (pesticide) values. Each day:

1
Mark every index i ≥ 1 with p[i] > p[i-1], reading from the start-of-day list so that deaths are simultaneous (a plant that will die can't shield the one to its right within the same day's evaluation, but it was there in the morning, so use the morning values).
2
Compact the list by keeping only unmarked plants.
3
If anything was marked, increment the day count and repeat; otherwise stop.

Why it's correct. It mirrors the rules exactly, including simultaneity (mark first, delete after).

Why it's too slow. Adversarial inputs (e.g. a long increasing run) kill only one or a few plants per day, so the number of days is O(n), and each day rescans the whole surviving list. The product is O(n²). The fix is to stop re-scanning and instead compute each plant's death day directly — which the monotonic stack does in one pass.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

p = [6, 5, 8, 4, 7, 10, 9]

Array state

day 1

8,7,10 die

[0]

[1]

[2]

[3]

[4]

[5]

[6]

Current pointerResolved stateNot processed

Final result2

C · Code with teaching comments

Reference implementation previewpublic int poisonousPlants(int[] p) { List<Integer> cur = new ArrayList<>(); for (int x : p) cur.add(x); int days = 0; while (true) {Explore the full code

solution.javaJava

Brute Force — Day-by-Day Simulation — reference

4 teaching notes

1
public int poisonousPlants(int[] p) {
2
    List<Integer> cur = new ArrayList<>();
3
    for (int x : p) cur.add(x);
4
    int days = 0;
5
    while (true) {
6
        List<Integer> next = new ArrayList<>();
7
        boolean died = false;
8
        // The leftmost plant has no left neighbour, so it always survives.
9
        next.add(cur.get(0));                 // first plant never dies
10
        for (int i = 1; i < cur.size(); i++) {
11
            // Strict > against the morning's left neighbour — equal does not kill.
12
            if (cur.get(i) > cur.get(i - 1)) {
13
                // Mark a death; we read cur (start-of-day) so deaths are simultaneous.
14
                died = true;                   // dies (using morning values)
15
            } else {
16
                next.add(cur.get(i));
17
            }
18
        }
19
        // A day with no deaths means the arrangement is stable.
20
        if (!died) break;
21
        days++;
22
        cur = next;
23
    }
24
    return days;
25
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.25 lines

D · Why it works and complexityO(n²) worst case timeO(n) spaceOpen the invariant and proofExplore the proof

The quadratic cost comes from re-deriving the same neighbour relationships every day. Each plant's death day is actually a fixed function of the plants shielding it on the left, so it can be computed once — no repeated simulation needed.

ComplexityO(n²) worst case time, O(n) space — Each day costs O(n) to scan and rebuild. In the worst case only a few plants die per day, so up to O(n) days are needed → O(n²) total. At n = 10⁵ that's ~10¹⁰ operations — far too slow.

E · Edge cases and pitfalls3Comparing against the already-updated next list, breaking simultaneity.Explore edge cases

Pitfalls

Comparing against the already-updated next list, breaking simultaneity.
Using ≥ instead of > — kills plants that should survive.
Running it at n = 10⁵ on a near-sorted input — O(n²) times out.

03.2

Approach 2 of 2 · Optimal

Monotonic Stack of Death Days (Optimal)

TimeO(n)SpaceO(n)

The answer they want. Phrase it as 'compute each plant's death day in one pass with a non-increasing stack; the answer is the max'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

For each plant, figure out the day it dies rather than simulating. A plant dies one day after the last of the larger-or-equal plants shielding it on the left has died.

2Hint 2Explore hint

Maintain a stack of indices with non-increasing pesticide. For plant i, pop every plant with pesticide ≥ p[i], tracking the maximum death-day among them.

3Hint 3Explore hint

If the stack empties, no smaller plant survives to the left → plant i never dies (day 0). Otherwise its death day is 1 + that maximum. The answer is the largest death day.

A · Core idea

Compute each plant's death day directly.

The recurrence. Consider plant i. The plants immediately to its left with pesticide ≥ p[i] are 'shields' — i cannot die while any of them is alive directly to its left, because it only dies against a smaller left neighbour. Once all those shields have died, i's left neighbour becomes some smaller plant, and i dies the very next day. So day[i] = 1 + max(day[shield]) over the contiguous run of ≥-pesticide shields — unless there is no smaller plant beyond them (the run extends to the left end), in which case i is a permanent survivor with day[i] = 0.

Why a non-increasing stack captures the shields. Walk left to right pushing indices. Before pushing i, pop every stack entry whose pesticide is ≥ p[i]: those are exactly i's shields (the chain of larger-or-equal plants directly preceding it). While popping, accumulate the maximum of their day values. After popping:

If the stack is empty, every plant to the left was ≥ p[i], so i becomes the new minimum and never dies → day[i] = 0.
Otherwise the stack top is a strictly smaller plant that survives long enough to expose i, so day[i] = maxPoppedDay + 1.

Push i (with its day) and update the global answer.

Why it's correct and O(n). The stack stays non-increasing, so each index is pushed and popped at most once — linear total work. The death-day recurrence exactly models the simultaneous-elimination dynamics: a plant's demise is gated by the latest-dying shield in front of it, plus one day. The maximum death day is the number of days with at least one death.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

p = [6, 5, 8, 4, 7, 10, 9]

Array state

after pass

day = [0,0,1,0,1,1,2]

[0]

[1]

[2]

[3]

[4]

[5]

[6]

Current pointerResolved stateNot processed

Final result2

C · Code with teaching comments

solution.javaJava

Monotonic Stack of Death Days (Optimal) — optimal

5 teaching notes

1
public int poisonousPlants(int[] p) {
2
    int n = p.length;
3
    int[] day = new int[n];
4
    Deque<Integer> stack = new ArrayDeque<>();   // indices, non-increasing pesticide
5
    int answer = 0;
6
    for (int i = 0; i < n; i++) {
7
        int d = 0;
8
        // Pop the shields: earlier plants with pesticide ≥ the current one.
9
        while (!stack.isEmpty() && p[stack.peek()] >= p[i]) {
10
            // Track the latest day any shield dies.
11
            d = Math.max(d, day[stack.peek()]);
12
            stack.pop();
13
        }
14
        // Empty stack → permanent survivor (0); else dies one day after its last
15
        // shield.
16
        day[i] = stack.isEmpty() ? 0 : d + 1;
17
        // The answer is the maximum death day over all plants.
18
        answer = Math.max(answer, day[i]);
19
        // Push the current plant; the stack stays non-increasing.
20
        stack.push(i);
21
    }
22
    return answer;
23
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.23 lines

D · Why it works and complexityO(n) timeO(n) spaceOpen the invariant and proofExplore the proof

Reframing 'simulate days' as 'compute each element's death day' is the key move. The death day telescopes through the shielding chain — 1 + max(shield days) — which a monotonic stack evaluates in amortised O(1) per element. This is the nearest-smaller-element pattern carrying a time stamp.

ComplexityO(n) time, O(n) space — Each plant is pushed once and popped at most once, so the total stack work across the loop is O(n). Computing the per-plant death day and the running max is O(1) amortised → O(n) time, O(n) stack space.

E · Edge cases and pitfalls8p = [3, 2, 1] — Each plant ≤ its left → every push empties or sits below; all day[i]=0 → answer 0.Explore edge cases

Edge cases handled

p = [3, 2, 1]Each plant ≤ its left → every push empties or sits below; all day[i]=0 → answer 0.
p = [1, 2, 3, 4]2,3,4 each have a strictly smaller immediate left → all die on day 1 simultaneously → answer 1.
p = [1]Single plant, no neighbour → answer 0.
p with equal neighbours like [5, 5, 5]Equal does not kill (strict >) → answer 0.

Pitfalls

Popping with > instead of ≥ — equal-pesticide shields must also be popped to compute the right death day.
Forgetting the empty-stack case → assigning day 1 to permanent survivors.
Returning the last plant's day instead of the global maximum.
Pushing values instead of indices when you need day[] keyed by position (either works if you store (value, day) pairs).

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic int poisonousPlants(int[] p) { int n = p.length; int[] day = new int[n]; Deque<Integer> stack = new ArrayDeque<>(); // indices, non-increasing pesticide int answer = 0;Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Quadratic day-by-day simulation

Re-scanning the surviving list every day is O(n) per day and can require O(n) days (slow staircase inputs), giving O(n²) — too slow for n = 10⁵.

Explore the code comparison

Don't write this

while True:
    nxt, died = [cur[0]], False
    for i in range(1, len(cur)):
        if cur[i] > cur[i-1]: died = True
        else: nxt.append(cur[i])
    if not died: break
    days += 1; cur = nxt   # O(n) per day, O(n) days

Write this instead

stack, answer = [], 0
for i in range(n):
    d = 0
    while stack and p[stack[-1]] >= p[i]:
        d = max(d, day[stack[-1]]); stack.pop()
    day[i] = 0 if not stack else d + 1
    answer = max(answer, day[i]); stack.append(i)  # O(n) total

Wrong comparison operator

A plant dies only when STRICTLY greater than its left neighbour. Using ≥ kills plants with equal pesticide and inflates the day count.

Explore the code comparison

Don't write this

if (cur.get(i) >= cur.get(i - 1)) { died = true; }  // equal must NOT kill

Write this instead

if (cur.get(i) > cur.get(i - 1)) { died = true; }

Sequential deaths within a day

If you delete a plant immediately and then compare the next plant to the freshly-shifted left neighbour, you change the morning arrangement mid-day and miscount who dies.

Explore the code comparison

Don't write this

for i in range(1, len(cur)):
    if cur[i] > nxt[-1]:   # comparing to the UPDATED survivor list — wrong
        died = True
    else:
        nxt.append(cur[i])

Write this instead

for i in range(1, len(cur)):
    if cur[i] > cur[i - 1]:  # compare to the morning (start-of-day) neighbour
        died = True
    else:
        nxt.append(cur[i])

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Monotonic (non-increasing) stack tracking each element's 'death day'

Code pattern to memorize

stack holds indices with non-increasing pesticide
for each plant i:
    d = 0
    while stack nonempty and p[top] >= p[i]:
        d = max(d, day[top]); pop
    day[i] = (stack empty) ? 0 : d + 1
    answer = max(answer, day[i])
    push i

Rules to remember

1A plant dies the day its strictly greater condition holds against its CURRENT (alive) left neighbour — p[i] > p[left], equal does not kill.
2Deaths each day are simultaneous: compute the whole day's casualties from the start-of-day arrangement before compacting.
3On the stack, pop everything with pesticide ≥ p[i]; the current plant's death day is 1 + max(death-day of popped).
4If the stack empties while popping, no surviving plant to the left is smaller, so the current plant is a permanent survivor → death day 0.
5The answer is the maximum death day across all plants (0 if nothing ever dies).

Use this pattern when

Simultaneous-elimination simulations where naive day-by-day is O(n²)
Each element's fate depends on the nearest smaller/larger element to one side
You can fold many simulated rounds into a single left-to-right pass
'Number of rounds/days until stable' over a line of elements

Choose another pattern when

Eliminations are global or value-sorted, not against an adjacent neighbour → heap/sort
The structure is a tree/graph, not a line → different traversal
You need the full surviving sequence each day, not just the day count → may need explicit simulation
Comparison is non-local (depends on far elements arbitrarily) → monotonic stack may not apply

Interview takeaway

When a per-round, neighbour-based elimination would be quadratic, a monotonic stack often collapses all rounds into one pass by computing, for each element, *when* it dies in terms of the elements that shield it. The maximum of those times is the number of rounds.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternPoisonous Plants is a nearest-smaller-element problem with a time stamp: each element's 'death day' telescopes as 1 + max death day of the larger-or-equal shields immediately to its left, and an empty stack marks a permanent survivor. A single monotonic-stack pass replaces O(n²) round simulation. Same toolkit as Daily Temperatures, Largest Rectangle in Histogram, and Online Stock Span.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Daily Temperatures
Monotonic stack computing 'days until' a future event — same machinery, other direction.
Largest Rectangle in Histogram
Coming soon
Nearest-smaller-element on both sides via a monotonic stack.
Online Stock Span
Coming soon
Stack accumulating spans of consecutive ≤ elements — closely related counting.
Min Max Riddle
Nearest-smaller boundaries via monotonic stack to size each window — same toolkit.

Same pattern

←

Waiter

hardStack QueueFrequently asked

Poisonous Plants

Stack & Queue · 17 of 17 · 11 min

Given the initial pesticide levels p, determine the number of days after which no plant dies (i.e., the number of days on which at least one plant dies).

In plain English

Examples

Example 1

Input: p = [6, 5, 8, 4, 7, 10, 9]
Output: 2
Note: Day 1: 8 (>5), 7 (>4), 10 (>7) die → [6,5,4,9]. Day 2: 9 (>4) dies → [6,5,4]. Day 3: no deaths. Two days saw deaths.

Example 2

Input: p = [3, 2, 5, 4]
Output: 2
Note: Day 1: 5 (>2) dies; 4 has left neighbour 5 (4<5) so it survives → [3,2,4]. Day 2: 4 (>2) dies → [3,2]. Day 3: no deaths. Two days saw a death.

Example 3

Input: p = [3, 2, 1]
Output: 0
Note: Strictly decreasing: every plant is ≤ its left neighbour, so no plant ever dies.

Example 4

Input: p = [1, 2, 3, 4]
Output: 1
Note: Each of 2, 3, 4 is strictly greater than its morning left neighbour, so all three die simultaneously on day 1, leaving [1]. Day 2 has no deaths → answer 1.

Constraints

1 ≤ n ≤ 10⁵
0 ≤ p[i] ≤ 10⁹ (pesticide levels; duplicates allowed)
A plant dies only if its pesticide is STRICTLY greater than its current left neighbour's
Deaths within a day are simultaneous; survivors compact before the next day
Return the number of days until a day occurs with zero deaths (0 if no plant ever dies)

Clarifying questions4First question: Does a plant die on equal pesticide, or only strictly greater?Explore questions

Q1.Does a plant die on equal pesticide, or only strictly greater?
Only strictly greater than the left neighbour. Equal pesticide does not kill — using ≥ instead of > is a classic off-by-one bug here.
Q2.Are deaths within a single day simultaneous or sequential?
Simultaneous. All plants that satisfy the kill condition against the morning's arrangement die together; you must not let one death change a neighbour mid-day.
Q3.Can a plant never die?
Yes. The first plant never dies (no left neighbour), and any plant that is ≤ every plant remaining to its left is a permanent survivor — its death day is 0.
Q4.What's returned — the last day with a death, or the first quiet day?
The number of days on which at least one plant dies, i.e. the maximum death day. If nothing ever dies, that's 0.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Where candidates slip

How to stand out

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Brute Force — Day-by-Day Simulation	`O(n²) worst case`	`O(n)`	State it to lock down the rules (strict >, simultaneous deaths), then reject it on the O(n²) cost for n = 10⁵.	Read
2	Monotonic Stack of Death Days (Optimal)Optimal	`O(n)`	`O(n)`	The answer they want. Phrase it as 'compute each plant's death day in one pass with a non-increasing stack; the answer is the max'.	Read

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Brute Force — Day-by-Day Simulation

TimeO(n²) worst caseSpaceO(n)

State it to lock down the rules (strict >, simultaneous deaths), then reject it on the O(n²) cost for n = 10⁵.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Each day, scan the current list and mark every plant whose pesticide exceeds its immediate left neighbour — using the morning arrangement, so deaths are simultaneous.

2Hint 2Explore hint

Remove all marked plants at once to form the next day's list; increment the day counter if anything died.

3Hint 3Explore hint

Repeat until a day passes with no deaths. A long 'staircase' like [1,2,3,…,n] makes the survivor peel off slowly, giving O(n) days × O(n) work.

A · Core idea

Simulate the literal process. Hold the current list of (pesticide) values. Each day:

1
Mark every index i ≥ 1 with p[i] > p[i-1], reading from the start-of-day list so that deaths are simultaneous (a plant that will die can't shield the one to its right within the same day's evaluation, but it was there in the morning, so use the morning values).
2
Compact the list by keeping only unmarked plants.
3
If anything was marked, increment the day count and repeat; otherwise stop.

Why it's correct. It mirrors the rules exactly, including simultaneity (mark first, delete after).

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

p = [6, 5, 8, 4, 7, 10, 9]

Array state

day 1

8,7,10 die

[0]

[1]

[2]

[3]

[4]

[5]

[6]

Current pointerResolved stateNot processed

Final result2

C · Code with teaching comments

Reference implementation previewpublic int poisonousPlants(int[] p) { List<Integer> cur = new ArrayList<>(); for (int x : p) cur.add(x); int days = 0; while (true) {Explore the full code

solution.javaJava

Brute Force — Day-by-Day Simulation — reference

4 teaching notes

1
public int poisonousPlants(int[] p) {
2
    List<Integer> cur = new ArrayList<>();
3
    for (int x : p) cur.add(x);
4
    int days = 0;
5
    while (true) {
6
        List<Integer> next = new ArrayList<>();
7
        boolean died = false;
8
        // The leftmost plant has no left neighbour, so it always survives.
9
        next.add(cur.get(0));                 // first plant never dies
10
        for (int i = 1; i < cur.size(); i++) {
11
            // Strict > against the morning's left neighbour — equal does not kill.
12
            if (cur.get(i) > cur.get(i - 1)) {
13
                // Mark a death; we read cur (start-of-day) so deaths are simultaneous.
14
                died = true;                   // dies (using morning values)
15
            } else {
16
                next.add(cur.get(i));
17
            }
18
        }
19
        // A day with no deaths means the arrangement is stable.
20
        if (!died) break;
21
        days++;
22
        cur = next;
23
    }
24
    return days;
25
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.25 lines

D · Why it works and complexityO(n²) worst case timeO(n) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls3Comparing against the already-updated next list, breaking simultaneity.Explore edge cases

Pitfalls

Comparing against the already-updated next list, breaking simultaneity.
Using ≥ instead of > — kills plants that should survive.
Running it at n = 10⁵ on a near-sorted input — O(n²) times out.

03.2

Approach 2 of 2 · Optimal

Monotonic Stack of Death Days (Optimal)

TimeO(n)SpaceO(n)

The answer they want. Phrase it as 'compute each plant's death day in one pass with a non-increasing stack; the answer is the max'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

For each plant, figure out the day it dies rather than simulating. A plant dies one day after the last of the larger-or-equal plants shielding it on the left has died.

2Hint 2Explore hint

Maintain a stack of indices with non-increasing pesticide. For plant i, pop every plant with pesticide ≥ p[i], tracking the maximum death-day among them.

3Hint 3Explore hint

If the stack empties, no smaller plant survives to the left → plant i never dies (day 0). Otherwise its death day is 1 + that maximum. The answer is the largest death day.

A · Core idea

Compute each plant's death day directly.

If the stack is empty, every plant to the left was ≥ p[i], so i becomes the new minimum and never dies → day[i] = 0.
Otherwise the stack top is a strictly smaller plant that survives long enough to expose i, so day[i] = maxPoppedDay + 1.

Push i (with its day) and update the global answer.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

p = [6, 5, 8, 4, 7, 10, 9]

Array state

after pass

day = [0,0,1,0,1,1,2]

[0]

[1]

[2]

[3]

[4]

[5]

[6]

Current pointerResolved stateNot processed

Final result2

C · Code with teaching comments

solution.javaJava

Monotonic Stack of Death Days (Optimal) — optimal

5 teaching notes

1
public int poisonousPlants(int[] p) {
2
    int n = p.length;
3
    int[] day = new int[n];
4
    Deque<Integer> stack = new ArrayDeque<>();   // indices, non-increasing pesticide
5
    int answer = 0;
6
    for (int i = 0; i < n; i++) {
7
        int d = 0;
8
        // Pop the shields: earlier plants with pesticide ≥ the current one.
9
        while (!stack.isEmpty() && p[stack.peek()] >= p[i]) {
10
            // Track the latest day any shield dies.
11
            d = Math.max(d, day[stack.peek()]);
12
            stack.pop();
13
        }
14
        // Empty stack → permanent survivor (0); else dies one day after its last
15
        // shield.
16
        day[i] = stack.isEmpty() ? 0 : d + 1;
17
        // The answer is the maximum death day over all plants.
18
        answer = Math.max(answer, day[i]);
19
        // Push the current plant; the stack stays non-increasing.
20
        stack.push(i);
21
    }
22
    return answer;
23
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.23 lines

D · Why it works and complexityO(n) timeO(n) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls8p = [3, 2, 1] — Each plant ≤ its left → every push empties or sits below; all day[i]=0 → answer 0.Explore edge cases

Edge cases handled

p = [3, 2, 1]Each plant ≤ its left → every push empties or sits below; all day[i]=0 → answer 0.
p = [1, 2, 3, 4]2,3,4 each have a strictly smaller immediate left → all die on day 1 simultaneously → answer 1.
p = [1]Single plant, no neighbour → answer 0.
p with equal neighbours like [5, 5, 5]Equal does not kill (strict >) → answer 0.

Pitfalls

Popping with > instead of ≥ — equal-pesticide shields must also be popped to compute the right death day.
Forgetting the empty-stack case → assigning day 1 to permanent survivors.
Returning the last plant's day instead of the global maximum.
Pushing values instead of indices when you need day[] keyed by position (either works if you store (value, day) pairs).

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Quadratic day-by-day simulation

Re-scanning the surviving list every day is O(n) per day and can require O(n) days (slow staircase inputs), giving O(n²) — too slow for n = 10⁵.

Explore the code comparison

Don't write this

while True:
    nxt, died = [cur[0]], False
    for i in range(1, len(cur)):
        if cur[i] > cur[i-1]: died = True
        else: nxt.append(cur[i])
    if not died: break
    days += 1; cur = nxt   # O(n) per day, O(n) days

Write this instead

stack, answer = [], 0
for i in range(n):
    d = 0
    while stack and p[stack[-1]] >= p[i]:
        d = max(d, day[stack[-1]]); stack.pop()
    day[i] = 0 if not stack else d + 1
    answer = max(answer, day[i]); stack.append(i)  # O(n) total

Wrong comparison operator

A plant dies only when STRICTLY greater than its left neighbour. Using ≥ kills plants with equal pesticide and inflates the day count.

Explore the code comparison

Don't write this

if (cur.get(i) >= cur.get(i - 1)) { died = true; }  // equal must NOT kill

Write this instead

if (cur.get(i) > cur.get(i - 1)) { died = true; }

Sequential deaths within a day

If you delete a plant immediately and then compare the next plant to the freshly-shifted left neighbour, you change the morning arrangement mid-day and miscount who dies.

Explore the code comparison

Don't write this

for i in range(1, len(cur)):
    if cur[i] > nxt[-1]:   # comparing to the UPDATED survivor list — wrong
        died = True
    else:
        nxt.append(cur[i])

Write this instead

for i in range(1, len(cur)):
    if cur[i] > cur[i - 1]:  # compare to the morning (start-of-day) neighbour
        died = True
    else:
        nxt.append(cur[i])

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Monotonic (non-increasing) stack tracking each element's 'death day'

Code pattern to memorize

stack holds indices with non-increasing pesticide
for each plant i:
    d = 0
    while stack nonempty and p[top] >= p[i]:
        d = max(d, day[top]); pop
    day[i] = (stack empty) ? 0 : d + 1
    answer = max(answer, day[i])
    push i

Rules to remember

1A plant dies the day its strictly greater condition holds against its CURRENT (alive) left neighbour — p[i] > p[left], equal does not kill.
2Deaths each day are simultaneous: compute the whole day's casualties from the start-of-day arrangement before compacting.
3On the stack, pop everything with pesticide ≥ p[i]; the current plant's death day is 1 + max(death-day of popped).
4If the stack empties while popping, no surviving plant to the left is smaller, so the current plant is a permanent survivor → death day 0.
5The answer is the maximum death day across all plants (0 if nothing ever dies).

Use this pattern when

Simultaneous-elimination simulations where naive day-by-day is O(n²)
Each element's fate depends on the nearest smaller/larger element to one side
You can fold many simulated rounds into a single left-to-right pass
'Number of rounds/days until stable' over a line of elements

Choose another pattern when

Eliminations are global or value-sorted, not against an adjacent neighbour → heap/sort
The structure is a tree/graph, not a line → different traversal
You need the full surviving sequence each day, not just the day count → may need explicit simulation
Comparison is non-local (depends on far elements arbitrarily) → monotonic stack may not apply

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Daily Temperatures
Monotonic stack computing 'days until' a future event — same machinery, other direction.
Largest Rectangle in Histogram
Coming soon
Nearest-smaller-element on both sides via a monotonic stack.
Online Stock Span
Coming soon
Stack accumulating spans of consecutive ≤ elements — closely related counting.
Min Max Riddle
Nearest-smaller boundaries via monotonic stack to size each window — same toolkit.

Same pattern

←

Waiter