[C++] time machine approach
The idea is, when you see a lake is going to flood, you take the time machine and go back in time to dry the lake.  If there is no sunny day previously, you let
The idea is, when you see a lake is going to flood, you take the time machine and go back in time to dry the lake.  If there is no sunny day previously, you let it flood.  If there are multiple sunny days, you choose the latest one that can dry the previous raining day of the lake.\n\n\n```\n    vector<int> avoidFlood(vector<int>& rains) {\n        const int N = rains.size();\n        vector<int> out(N, -1);\n        set<int> zeroIdx;  // time machine records which days we can go back to\n        unordered_map<int, int> fullLakes;  // lake --> the last raining day\n        \n        for (int i = 0; i < N; ++i) {\n            if (rains[i] == 0) {\n                zeroIdx.insert(i);  // time machine logs the day\n                continue;\n            }\n            \n            // i is a raining day\n            if (fullLakes.count(rains[i]) == 0) {\n                fullLakes[rains[i]] = i;  // let it be full first\n                continue;\n            }\n            \n            // the lake is already full\n            if (zeroIdx.size() == 0) return vector<int>();  // no past sunny day available\n\t\t\t\n            // find the first eligible sunny day to fix the lake before it floods\n            auto fix = zeroIdx.lower_bound(fullLakes[rains[i]]);\n            if (fix == zeroIdx.end()) return vector<int>();  // unfortunately, no eligible past sunny day\n            \n\t\t\t// yeah, it\'s fixable\n            out[*fix] = rains[i];  // go back in time, and clean the lake\n            fullLakes[rains[i]] = i;  // now go back to present time and fill the lake\n            zeroIdx.erase(fix);  // this sunny day is no longer available to rescue the world\n        }\n        \n\t\t// all the extra sunny days, just dry lake 1 as exercise\n        for (auto& idx : zeroIdx) {\n            out[idx] = 1;\n        }\n\n        return out;\n    }\n```\n\nTime: O(N logN),  I guess\nSpace: O(N), all sunny days or it rains at all different lakes.
[]