1488: Avoid-Flood-in-The-City
Medium

code
- complexity
- time taken

Let us assume that we traverse lake i n times, where n >= 2, in rains, with the last two times occurring at indices t^i_{n-1} and t^i_{n}.

Then, there are two cases:

if there are no dry spells between t^i_{n-1} and t^i_{n}, then that implies that lake i will flood
if there are dry spells between t^i_{n-1} and t^i_{n}, then we should greedily allocate the earliest possible dry spell to lake i
- this gives us the maximum freedom, leaving later dry spells for other lakes that might need it more

code

class Solution {
public:
    vector<int> avoidFlood(vector<int>& rains) {
        unordered_map<int, int> full;
        set<int> dry;
        vector<int> ans (rains.size(), 1);

        for (int i = 0; i < rains.size(); ++i) {
            if (rains[i]) {
                int lake = rains[i];
                if (full.count(lake)) {
                    auto it = dry.lower_bound(full[lake]);
                    if (it == dry.end()) return {};
                    ans[*it] = lake;
                    dry.erase(it);
                }
                full[lake] = i;
                ans[i] = -1;
            } else {
                dry.insert(i);
            }
        }

        return ans;
    }
};

1488: Avoid-Flood-in-The-City Medium

table of contents

code

complexity

time taken

1488: Avoid-Flood-in-The-City
Medium