How to lose plants and aggravate people

Question

Courtesy of a few posts around here I've discovered HackerRank. Poisonous Plants is one of their challenges.

Of course, skip the following if you'd like to try it yourself.

Challenge:

There are \$N\$ plants in a garden. Each of these plants has been added with some amount of pesticide. After each day, if any plant has more pesticide than the plant at its left, it dies.

Given the initial values of pesticide in each plant, print the number of days after which no plant dies, i.e. the time after which there are no plants with more pesticide content than the plant to their left.

Input Format:

The input consists of an integer \$N\$. The next line consists of N integers describing the array P where P[i] denotes the amount of pesticide in plant i.

Constraints:

• \$1 \le N \le 100000\$
• \$0 \le P[i] \le 10^9\$

Output Format:

Output a single value equal to the number of days after which no plants die.

Solution:

import java.util.Scanner;

public class Solution {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);

        int[] garden = new int[input.nextInt()];
        for (int i = 0; i < garden.length; i++) {
            garden[i] = input.nextInt();
        }

        int days = 0;
        while(killCommand(garden)) {
            days++;
        }

        System.out.println(days);
    }

    private static boolean killCommand(int[] garden) {
        boolean plantDied = false;
        int lastIndex = garden.length - 1;
        int last = garden[lastIndex];

        for (int i = lastIndex - 1; i >= 0; i--) {
            if (garden[i] == -1) {
                continue;
            }
            int current = garden[i];
            if (current < last) {
                plantDied = true;
                garden[lastIndex] = -1;
            }
            last = current;
            lastIndex = i;
        }

        return plantDied;
    }
}

Sample Input:

7
6 5 8 4 7 10 9

Sample Output:

2

My algorithm works and passes 21 of 23 test cases, but doesn't meet their allotted time for two. How can it be further optimized?

Answer 1

Your code is indeed correct but it is slow: for each day, you are looping over the whole array of numbers to determine if a given plant is killed in that day. You won't be able to optimize your approach further than what you already have. To validate the last 2 test inputs, you need to take another approach.

---

This problem can be tackled in O(n) complexity by only processing the input array once, from left to right, as was done in this other code review. The idea of the algorithm is to traverse it only once and calculate, for each plant, the number of days it will stay alive.

The observation that can be made is that the number of days plant i will stay alive is the number of days the right-most plant to the left of i that has less pesticide than i, incremented by 1. And if there are none, then the plant never dies. Taking an example:

 6   5   8   4   7   10   9
             |   +--------+
             |   |        |
             |   |        when will this plant die?
             +---|
             |   the day after this one dies and when will this one die?
+------------|
|            the day after this one dies and when will this one die? 
|
never
|
+------------0---1--------2

Since we reached the beginning of the array, we know that the plant with pesticide 4 never dies, hence the plant with pesticide 7 dies on day 1 and the plant with pesticide 9 dies on day 2.

We can then improve this first approach. By going from left to right, if we hit a plant i that will never die, we can actually forget all the plants before and stop checking them because any plant waiting for one of those to die will have to wait for i to die first and we know that it will never happen.

In terms of code, this can be implemented by having a stack of a Plant class that would hold its pesticide count and the number of days it stays alive. For each number, we start from the top of the stack and look the closest plant behind having less pesticide; in the mean time, we keep a running daysAlive that is simply the maximum days alive of the encoutered plants and we remove them as we go on. If we reached the end and the stack is empty, it means the plant never dies so we set its daysAlive to 0 and push it to the stack. Otherwise, it means the plant dies the day after that one and we push it to the stack.

public static void main(String[] args) {
    Scanner input = new Scanner(System.in);

    int[] garden = new int[input.nextInt()];
    for (int i = 0; i < garden.length; i++) {
        garden[i] = input.nextInt();
    }

    System.out.println(maxDaysAlive(garden));
}

private static int maxDaysAlive(int[] numbers) {
    Deque<Plant> stack = new ArrayDeque<>();
    int maxDaysAlive = 0;
    for (int pesticide : numbers) {
        int daysAlive = 0;
        while (!stack.isEmpty() && pesticide <= stack.peek().pesticide) {
            daysAlive = Math.max(daysAlive, stack.pop().days);
        }
        if (stack.isEmpty()) {
            daysAlive = 0;
        } else {
            daysAlive++;
        }
        maxDaysAlive = Math.max(maxDaysAlive, daysAlive);
        stack.push(new Plant(pesticide, daysAlive));
    }
    return maxDaysAlive;
}

private static class Plant {

    int pesticide = 0, days = 0;

    public Plant(int pesticide, int days) {
        this.pesticide = pesticide;
        this.days = days;
    }

}