[Java] TreeSet with HashMap solution
First, we create a HashMap to store the day to lake mapping rains[i] -> i, which means at day i, lake rains[i] is filled.\n\nThen, we maintain a sorted set of t
First, we create a HashMap to store the day to lake mapping `rains[i] -> i`, which means at day i, lake rains[i] is filled.\n\nThen, we maintain a sorted set of the dry days at which we could possibly dry lakes. \n\nThe rest works as greedy, or lazy load. If a lake is filled again at `day j`, we would search for the first day after its previous filling date `day i`, which is stored in the map.\n\nThe time complexity is O(n * log n), space complexity is O(n). TreeSet does the binary search for us so we can save some efforts.\n\n```\nclass Solution {\n    public int[] avoidFlood(int[] rains) {\n        int n = rains.length;\n        int[] ans = new int[n];\n        Map<Integer, Integer> map = new HashMap<>();\n        TreeSet<Integer> dryDays = new TreeSet<>();\n        for (int i = 0; i < n; i++) {\n            if (rains[i] == 0) {\n                dryDays.add(i);\n            } else {\n                ans[i] = -1;\n                if (map.containsKey(rains[i])) {\n                    Integer index = dryDays.higher(map.get(rains[i]));\n                    if (index == null) {\n                        return new int[0];\n                    }\n                    ans[index] = rains[i];\n                    dryDays.remove(index);\n                }\n                map.put(rains[i], i);\n            }\n        }\n        for (int day : dryDays) {\n            ans[day] = 1;\n        }\n        return ans;\n    }\n}\n```
[]