Day 11: Stacks | Poisonous Plants

I am attempting the 30 days of coding challenge in python and in this article I will be figuring out the number of days after which no plant dies.

Of course tulips are not poisonous, but I had to gloat with this amazing photo I took last year.

Tulips from Keukenhof

Prerequisite Recap:

Stacks

A stack is a data structure in computer science that follows the Last-In-First-Out (LIFO) principle. This means that the last element added to the stack is the first one to be removed. It is similar to a real-life stack of items, like a stack of plates, where you can only access the topmost plate, and to access the ones below, you need to remove the plates on top.

In Python, stacks can be easily implemented using lists, with the append() method to add elements to the top of the stack and the pop() method to remove the top element.

Here's an example of a simple stack in Python:

stack = []

# Push elements onto the stack
stack.append(1)
stack.append(2)
stack.append(3)

# Top element of the stack
top_element = stack[-1]

# Pop elements from the stack
popped_element = stack.pop()  # removes and returns the top element (3)

Stacks are useful in various programming scenarios, such as:

1. Evaluating expressions in programming languages (e.g., arithmetic expressions or function calls).
2. Traversing tree or graph structures using depth-first search algorithms.
3. Implementing backtracking algorithms, where you need to return to the previous step after exploring a path.
4. Managing function calls and their respective return addresses in a program’s call stack.

The primary operations performed on a stack are push (adding an element to the top of the stack) and pop (removing the top element). These operations are usually performed in constant time, making stacks efficient for problems where you need to maintain a specific order and access the most recent elements quickly.

More details on the DFS algorithm:

https://medium.com/@tudorache.a.bogdan/day-10-adjacent-list-roads-and-libraries-1422c8742ac5

The Problem:

Poisonous Plants | HackerRank

The Solution:

def poisonousPlants(plants):
    days = 0
    stack = []

    for plant in plants:
        days_to_die = 1
        
        # Check if the current plant has more pesticide than the plant on its left
        while stack and plant <= stack[-1][0]:
            _, prev_days_to_die = stack.pop()
            days_to_die = max(days_to_die, prev_days_to_die + 1)

        # If the stack is not empty, it means the current plant dies at some point
        if stack:
            days = max(days, days_to_die)
        else:
            days_to_die = 0

        stack.append((plant, days_to_die))

    return days

The Explanation:

1. Initialize the days variable to store the maximum number of days until plants no longer die. Set it to 0 initially.
2. Create an empty stack to store pairs (plant_pesticide, days_to_die) for each plant.
3. Iterate through the list of plants.
4. Set the initial days_to_die value to 1 for the current plant. This will be updated later based on the comparison with the plants on its left.
5. Check if the current plant has more pesticide than the plant on its left using a while loop. The top of the stack represents the plant on the left of the current plant. If the current plant’s pesticide level is less than or equal to the plant on its left, we pop the left plant from the stack and update the days_to_die value for the current plant.
6. If the stack is not empty after the while loop, it means the current plant will die at some point, and we update the days variable to store the maximum number of days between the previous maximum and the days_to_die value for the current plant.
7. If the stack is empty after the while loop, it means the current plant will not die as it has a lower or equal pesticide level compared to all the plants on its left. So, we set days_to_die to 0 for the current plant.
8. Push the current plant (with its pesticide level and days_to_die value) onto the stack.
9. After the loop is done iterating through all the plants, return the days variable as the final answer.

The provided solution works by keeping track of the remaining plants and their days to die using a stack. It ensures that we only iterate through the list of plants once, and all stack operations are performed in constant time, making the solution efficient and optimal for solving the poisonous plants problem.

Conclusion:

The provided solution for the poisonous plants problem is efficient because it has a linear time complexity, O(n), where n is the number of plants. This is achieved through the use of a stack data structure and a single loop that iterates through the list of plants.

The efficiency of this solution stems from the following reasons:

1. Single pass through the list of plants: The algorithm iterates through the list of plants just once. At each step, it processes the current plant and updates the stack accordingly, ensuring that the entire array is scanned in a single pass.
2. Constant-time stack operations: The push and pop operations on the stack have constant time complexity, O(1), which allows the algorithm to efficiently process the plants and update their days to die.
3. Smart stack usage: The stack stores pairs of (plant_pesticide, days_to_die), which helps keep track of the remaining plants and their days to die. This allows the algorithm to quickly determine if a plant will die and update the days accordingly without the need for an additional data structure or more complex logic.
4. No additional data structures: The algorithm doesn’t require any other data structures apart from the stack. This reduces memory overhead and contributes to the overall efficiency of the solution.
5. No nested loops: The inner while loop runs only when the current plant's pesticide level is less than or equal to the plant on its left (which is the top of the stack). In this case, the inner loop pops elements from the stack until a suitable position for the current plant is found. Since each plant is added to the stack at most once, and each plant is popped from the stack at most once, the total number of operations in the inner loop is O(n) across all iterations of the outer loop.

These factors combined make this solution an efficient and optimal approach to solving the poisonous plants problem.

Bogdan Tudorache | Founder @ berrynews.org

If you like the article and would like to support me, make sure to:

👏 Clap for the story (50 Claps) to help this article be featured

🔔 Follow me Bogdan Tudorache

📰 Read more coding content on Coding Challenge

🔔 Connect w/ me: LinkedIn | Reddit