Java, Well explained, O(n^2)
This is not the most optimised solution that once can have. The reason I am writing this is to explain people the concept of the greedy approach that we use to 
This is not the most optimised solution that once can have. The reason I am writing this is to explain people the concept of the greedy approach that we use to solve it. At the bottome I have mentioned what can be done to optimise it but for now let\'s consider the trivial approach and how to do it.\n\nBasically the idea is this: Assume you have the time machine. For each days it does not rain, you take a note of the day. You save it in a list called dryDays. Now everytime it rains, also save the day it rained and on what lake it rained in a map. \n\nNow let\'s say there is a rain today (day Z), you check if there is going to be rain on an already filled lake (say lake L) , if there is you do the following:\n1. You pull out your rain map to see when it last rained on this lake. Let\'s say it rained on day X. Z (today) > X (When it last rained here)\n2.  Now you pull out your dry day list and scroll through it to check if there was a dry day **AFTER** when there was rain on L. Let\'s say you find the first dry day that came after X and it is Y i.e min(Y) such that X < Y\n3.  You time travel and go to day Y and empty the lake so that it can rain on it again\n4.  Now you add lake L again in the rain map with day Z\n5.  Town is saved!\n\nBut what if there is no such Y such that X < Y? Well then bad news! There gonna be flood. You know it so run boy run!\n\nNow if today it is going to rain on a new lake, you just add it in you map and go to sleep peacefully knowing you saved the town once again!\n\n```\nclass Solution {\n    public int[] avoidFlood(int[] rains) {\n        // We will maintain a map of lake and when it last rained there\n        Map<Integer, Integer> full = new HashMap<>();\n        \n        // We will maintain a list of days that were dry day.\n        List<Integer> dryDays = new ArrayList<>();\n        \n        // Return value for flood\n        int[] emptyArray = new int[0];\n        \n        // Return order for no flood\n        int[] dryOrder = new int[rains.length];\n        \n        for(int i = 0; i < rains.length; i++){\n            \n            //It is a dry day aka day with no rain\n            if(rains[i] == 0){ \n                \n                // We got a dry day so just put 1 for now. It will be overwritten is actually used to empty any lake later\n                dryOrder[i] = 1; \n                if(full.size() == 0){ \n                    continue; // Since we do not have any lake filled yet these dry days are useless so don\'t add them to the dryDays list\n                }\n                \n                // When was this dry day, we can only empty lakes that were filled before this\n                dryDays.add(i); \n                \n            }else{ //It is a rainy day and it is gonna rain on some lake, let\'s see if we have emptied it before it rained\n                \n                //The lake was already full\n                if(full.containsKey(rains[i])){ \n                    \n                    // No dry days to empty the lake so flood is sure\n                    if(dryDays.size() == 0){ \n                        return emptyArray;\n                    }\n                    \n                    // When did it last rain on this lake\n                    int rainDay = full.get(rains[i]); \n                    \n                    boolean flood = true;  \n                    \n                    // Note: Optimisations can be done here to search in LogN instead of linear search\n                    for(int j = 0; j < dryDays.size(); j++){ // O(n)\n                        // Did we get a dry day after it rained here?\n                        int dryDay = dryDays.get(j);\n                        if(rainDay <= dryDay){\n                            \n                            // So we empty this lake on the first dry day that the occured after rain on this lake\n                            dryOrder[dryDay] = rains[i]; \n                            \n                            // Dry day j is used to empty lake[i] and hence can not be used again\n                            dryDays.remove(j);  // O(n)\n                            \n                            // Since it rained again on this lake, that is why we are in this loop in the first\n                            // place, but because we dried the lake before it rained again there is no flood but \n                            // this lake is full again.\n                            full.put(rains[i], i);\n                            \n                            // We had emptied this lake before so no flood\n                            flood = false;\n                            break;\n                        }\n                    }\n                    \n                    if(flood){ //If we could not find a dry day after rainDay on lake[i] flood is sure because we could not dry it\n                        return emptyArray;\n                    }\n                }else{ // If this is the first time there is rain on this lake just put it in the map\n                    full.put(rains[i], i);\n                }\n                \n                // Since it is a rain day, the dry order is bound to have -1 at this position\n                dryOrder[i] = -1; \n            }\n        }\n        \n        return dryOrder;\n    }\n}\n```\n\nThe optimisation that can be done is use a `TreeMap` instead of `ArrayList` and use its `ceiling` function to get Y. This operation is `log(n)` and removal of a node is also `log(n)`.
[]