Compute days until plants stop dying
Company: Walmart Labs
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are given a row of plants, each with an integer pesticide level.
## Rules
- On each day, any plant with a **strictly greater** pesticide level than the plant **immediately to its left** dies.
- All plants that die on a given day are removed **simultaneously**.
- The leftmost plant never dies (it has no left neighbor).
- The process repeats until a day occurs when **no plants die**.
## Task
Given an array `plant[]` of pesticide levels from left to right, return the number of days until plants stop dying.
## Input/Output
- **Input:** `plant` (array of integers)
- **Output:** integer number of days until stable
## Example
- Input: `plant = [6, 5, 8, 4, 7, 10, 9]`
- Output: `2`
## Assumptions / Constraints (if not otherwise specified)
- `1 <= n <= 1e5`
- `0 <= plant[i] <= 1e9`
- Aim for better than O(n²) time for large `n`.
Quick Answer: This question evaluates a candidate's ability to reason about array-based state transitions and algorithmic complexity, testing competency in analyzing iterative dependencies among elements and handling large input sizes.
You are given a row of plants, where each plant has an integer pesticide level. On each day, any plant with a strictly greater pesticide level than the plant immediately to its left dies. All deaths on the same day happen simultaneously, and the surviving plants close ranks before the next day begins. The leftmost plant never dies because it has no left neighbor.
Return the number of days until the plants reach a stable state where no plant dies anymore.
Example:
If plant = [6, 5, 8, 4, 7, 10, 9], then the answer is 2.
- Day 1: plants with levels 8 and 10 die, leaving [6, 5, 4, 7, 9]
- Day 2: plants with levels 7 and 9 die, leaving [6, 5, 4]
- Day 3: no plants die, so the process stops after 2 days
Constraints
- 1 <= len(plant) <= 100000
- 0 <= plant[i] <= 1000000000
Examples
Input: ([6, 5, 8, 4, 7, 10, 9],)
Expected Output: 2
Explanation: After day 1, plants 8 and 10 die. After day 2, plants 7 and 9 die. Then the row is stable.
Input: ([4],)
Expected Output: 0
Explanation: A single plant has no left neighbor, so it never dies.
Hints
- A day-by-day simulation can become O(n^2) in the worst case. Try to determine when each plant dies during a single left-to-right scan.
- A monotonic stack can help you find the nearest plant to the left that can keep a plant alive, while also tracking how many days removed plants survived.