Skip to content

← leetcode

Avoid Flood in The City

· Medium

LeetCode problem 1488

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;
    }
};

complexity

  • Time: O(n log(n)) where n is the number of elements inside of rains
  • Space: O(n)

time taken

  • 21 minutes and 8 seconds