Compute days until plants stop dying

Q: Compute days until plants stop dying

This is a Coding & Algorithms interview question from Walmart Labs for Software Engineer roles. View the full question and solution on PracHub.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

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 .