Leetcode 1488: Avoid Flood in The City

In this Leetcode problem, we need to find a way to prevent flood given some specific rules:

Problem statement

Solution

A few ideas to solve that problem:

1. We want to keep track of last time it rained for each city in fullLakes, a Map<Integer, Integer>.
2. One idea is that each time it rains to a city where it rained before, we want to find a dry day in between the 2 rain days so that we can dry the lake.
3. The optimal way to do it is to choose the smallest such available dry day.
4. To do that we store all available dry day in a TreeSet<Integer> noRain.
5. Once we find the dry day we update the int[] res.
6. At the end we fill the remaining dry days with 1s.

class Solution {
    public int[] avoidFlood(int[] rains) {
        // Keep track of full lakes and the last rain date for them.
        Map<Integer, Integer> fullLakes = new HashMap<>();
        // Keep track of days with no rain that we didn't use yet.
        TreeSet<Integer> noRain = new TreeSet<>();
        int n = rains.length;
        // Hold result to return
        int[] res = new int[n];
        for (int i = 0; i < n; i++) {
            int rain = rains[i];
            if (rain == 0) {
                noRain.add(i);
            } else {…