✅ Beat 100% | ✨ O(N) | 🏆 Most Efficient Solution | 💯 Greedy and Path Compression
Intuition\n Describe your first thoughts on how to solve this problem. \n  * Whenever we see the same lake appears again, we need to find an dry day between the
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n  * Whenever we see the same lake appears *again*, we need to find an **dry day** between them to dry it.\n  * For example if lake `30` appeared at day `4` and later at day `8`, we need find an **dry day** between `4` and `8` to dry this lake.\n  * We can do this greedily by using **the first dry day after `4`**.\n  * In the code it is the `next_dry_day[4]`, which means the next available dry day after day `4`.\n\n### Next Dry Day Search\n  * If we simply go through the array to find the next dry day, it would take $\\Theta(N)$ each time.\n  * If we use a sorted data structure like tree map (`std::set`), we can do this search in $\\Theta(\\log N)$ each time.\n  * But we can do better by using the **path compression** tech in `UnionFind`. The armotized time cost for each `next_dry_day` search would then be constant.\n> Note we do not actually need to use the `UnionFind` data structure, just the path compression part.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nWe do a one-pass on the input array and record the last index of each lake as we go.\nWhenever we saw a lake again we find a dry day for it before updating the index.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$\\Theta(N)$\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$\\Theta(N)$\n\n# Code\n```\nint FindNext(vector<int>& next_dry_day, int index) {\n  if (next_dry_day[index] != index) {\n    next_dry_day[index] = FindNext(next_dry_day, next_dry_day[index]);\n  }\n  return next_dry_day[index];\n}\n\nclass Solution {\npublic:\n  vector<int> avoidFlood(vector<int>& rains) {\n    const int N = rains.size();\n    unordered_map<int, int> lake_to_days;\n    vector<int> next_dry_day(N + 1);\n    std::iota(next_dry_day.begin(), next_dry_day.end(), 0);\n    // Magic lake not mentioned in the problem decription.\n    vector<int> answer(N, 1);\n\n    for (int i = 0; i < N; ++i) {\n      const int lake = rains[i];\n      if (lake == 0) {\n        continue;\n      }\n      answer[i] = -1;\n      next_dry_day[i] = i + 1;\n      auto [it, first_time] = lake_to_days.insert({lake, i});\n      if (!first_time) {\n        int dry_day = FindNext(next_dry_day, it->second);\n        if (dry_day >= i) {\n          return {};\n        }\n        answer[dry_day] = lake;\n        next_dry_day[dry_day] = dry_day + 1;\n        it->second = i;\n      }\n    }\n    return answer;\n  }\n};\n```
['Greedy', 'C++']