C++ | Binary Search + Hash Table | Explained
Approach\nDo a linear scan of the input array rains.\n\n- If rains[i] == 0, then store the index in zeroes.\n- If rains[i] != 0 and rains[i] does not exist in t
# Approach\nDo a linear scan of the input array `rains`.\n\n- If `rains[i] == 0`, then store the index in `zeroes`.\n- If `rains[i] != 0` and `rains[i]` does not exist in the hashmap, then insert it (and its index) into the hashmap. The lake `rains[i]` is now full.\n- If `rains[i] != 0` and `rains[i]` exists in the hashmap, then perform binary search on `zeroes` to see if `rains[i]` can be dried before it floods.\n\n# Complexity\n- Time complexity:\n$$O(n * log(n))$$\n\n- Space complexity:\n$$O(n)$$\n\n# Code\n```\nclass Solution {\npublic:\n    vector<int> avoidFlood(vector<int>& rains) {\n        unordered_map<int, int> memo; // (rains[i], i) where rains[i] != 0\n        set<int> zeroes; // i where rains[i] == 0\n        vector<int> ans(rains.size(), -1); // answer\n\n        for (int i = 0; i < rains.size(); ++i) {\n            if (rains[i] == 0) {\n                // store index in the zeroes list\n                // or increment chain from previous zero\n                zeroes.insert(i);\n            } else if (!memo.count(rains[i])) {\n                // store "lake" index in the hashmap\n                memo.emplace(rains[i], i);\n            } else {\n                // search for zero index that can dry out the "lake"\n                auto it = zeroes.upper_bound(memo.at(rains[i]));\n                \n                // return empty list if not found\n                if (it == zeroes.end()) return vector<int>();\n\n                // update answer, hashmp and zeroes\n                ans.at(*it) = rains[i];\n                memo.at(rains[i]) = i;\n                zeroes.erase(it);\n            }\n        }\n\n        // all unused zeroes will point to "lake" 1\n        for (int i: zeroes) ans.at(i) = 1;\n\n        return ans;\n    }\n};\n```
['Hash Table', 'Binary Search', 'C++']