Katkat
Back

Compute days until plants stop dying

Walmart LabsSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

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, 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.