Poisonous Plants

Question

I have solved the following problem. My code works but Hackerrank says that I can do faster:

There are 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, being weaker than the left one, it dies. You are given the initial values of the 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 . The next line consists of integers describing the array where denotes the amount of pesticide in plant .

Constraints

\$1 \leq N \leq 100000\$

\$0 \leq P[i] \leq 10^9\$

Output Format

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

Sample Input

7  
6 5 8 4 7 10 9

Sample Output

2

My code:

import java.io.*;
import java.util.*;

public class Solution {
    static Stack<Integer> aStack = new Stack<Integer>();
    static Stack<Integer> bStack = new Stack<Integer>();

    static int printDays(Stack aStack){
        int objectsRemoved=-1;
        int countLoops=0;

        while(objectsRemoved!=0) {

            objectsRemoved=0;

            int prevValue=0;
            int curValue=0;

            while(!aStack.isEmpty()) {

                curValue = (int)aStack.pop();

                   if(!aStack.isEmpty()){
                        int tempValue = (int)aStack.pop();
                        if(curValue<=tempValue){
                            bStack.push(curValue);
                        }
                        else{
                            objectsRemoved++;
                            //System.out.println("Removed " + curValue);
                        }
                        aStack.push(tempValue);
                   }
                   else{
                       bStack.push(curValue);
                   }

            }


            while(!bStack.isEmpty()) {
                aStack.push(bStack.pop());
            }

         if(objectsRemoved!=0){
             countLoops++;
         }

        }

        return countLoops;
    }

    public static void main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
        Scanner in = new Scanner(System.in);

        int t = in.nextInt();

        for(int a0 = 0; a0 < t; a0++){
            aStack.push(in.nextInt());

        }

        System.out.println(printDays(aStack));
    }
}

Any recommendations to make it faster?

Answer 1

While I suspect there is better than O(days*N) algorithm available, my idea was looking fairly complex for non-trivial inputs, probably not worth it as long as single array modification can do the brute force simulation. Although I'm not sure about Java's performance of arrays, but in C/C++ this would be flying and any more clever algorithm would have to be really $#%$#^& clever to beat 100k int array manipulation (even when we are talking 100k*100k in worst case, that's still only 10bil operations.. while the clever algo would solve it with O(100k), but that's quite special case).

So I wonder, whether you get "make it faster" because of algorithm, or because of your coding technique.

Your brute force days simulation can be written like this:

(edit: version two with slight initial search optimization)

static int simulateDays(final int[] plants){
    if (plants.length <= 1) return 0;
    int plantSize = plants.length, days = 0, i, lastDying = 1;
    while (true) {      // simulate as many days as needed
        // Search for first plant to die today
        for (i = lastDying; i < plantSize; ++i) {
            if (plants[i-1] < plants[i]) break;
        }
        if (i == plantSize) return days;  // no plant found to be dying
        lastDying = i;      // optimize the initial search next day
        int removed = 1;    // the one found (plants[i]) will die
        // Now search remaining plants for any other dying today and also remove all of them
        for (++i; i < plantSize; ++i) {
            if (plants[i-1] < plants[i]) {  // plant[i] dies, count+skip it.
                ++removed;
            } else {                        // plant[i] survives, move it to last living one
                plants[i-removed] = plants[i];
            }
        }
        plantSize -= removed;               // adjust total number of remaining plants
        ++days;                             // let's see another day
    }
}

Should be faster, as it doesn't use complex container Stack, only single int[] array, and no dynamic allocations, the whole simulation is contained in original array... but I didn't profile it, as the sample inputs I have are too small to do that.

I only tested it works for the sample case you posted, and few others I tried (to verify correctness of it).

I'm curious, if this change is enough to get better rating, let me know please. :)

edit: The worst input case for this approach is of course something like 100k of plants: 5 6 6 6 6 6 ... (so all the "6" plants will die after meeting with "5", each day only one, causing whole rest of array to move by one to left).

Answer 2

This will not affect performance because the compiler will optimize the code in the loop, essentially removing it from the actual running code, but you should still remove this unused variable

int prevValue=0;