{"id":6959,"date":"2020-06-20T23:18:33","date_gmt":"2020-06-21T06:18:33","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=6959"},"modified":"2020-06-20T23:20:16","modified_gmt":"2020-06-21T06:20:16","slug":"leetcode-1488-avoid-flood-in-the-city","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/algorithms\/binary-search\/leetcode-1488-avoid-flood-in-the-city\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1488. Avoid Flood in The City"},"content":{"rendered":"\n<p>Your country has an infinite number of lakes. Initially, all the lakes are empty, but when it rains over the&nbsp;<code>nth<\/code>&nbsp;lake, the&nbsp;<code>nth<\/code>&nbsp;lake becomes full of water. If it rains over a lake which is&nbsp;<strong>full of water<\/strong>, there will be a&nbsp;<strong>flood<\/strong>. Your goal is to avoid the flood in any lake.<\/p>\n\n\n\n<p>Given an integer array&nbsp;<code>rains<\/code>&nbsp;where:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>rains[i] &gt; 0<\/code>&nbsp;means there will be rains over the&nbsp;<code>rains[i]<\/code>&nbsp;lake.<\/li><li><code>rains[i] == 0<\/code>&nbsp;means there are no rains this day and you can choose&nbsp;<strong>one lake<\/strong>&nbsp;this day and&nbsp;<strong>dry it<\/strong>.<\/li><\/ul>\n\n\n\n<p>Return&nbsp;<em>an array&nbsp;<code>ans<\/code><\/em>&nbsp;where:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>ans.length == rains.length<\/code><\/li><li><code>ans[i] == -1<\/code>&nbsp;if&nbsp;<code>rains[i] &gt; 0<\/code>.<\/li><li><code>ans[i]<\/code>&nbsp;is the lake you choose to dry in the&nbsp;<code>ith<\/code>&nbsp;day&nbsp;if&nbsp;<code>rains[i] == 0<\/code>.<\/li><\/ul>\n\n\n\n<p>If there are multiple valid answers return&nbsp;<strong>any<\/strong>&nbsp;of them. If it is impossible to avoid flood return&nbsp;<strong>an empty array<\/strong>.<\/p>\n\n\n\n<p>Notice that if you chose to dry a full lake, it becomes empty, but if you chose to dry an empty lake, nothing changes. (see example 4)<\/p>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> rains = [1,2,3,4]\n<strong>Output:<\/strong> [-1,-1,-1,-1]\n<strong>Explanation:<\/strong> After the first day full lakes are [1]\nAfter the second day full lakes are [1,2]\nAfter the third day full lakes are [1,2,3]\nAfter the fourth day full lakes are [1,2,3,4]\nThere's no day to dry any lake and there is no flood in any lake.\n<\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> rains = [1,2,0,0,2,1]\n<strong>Output:<\/strong> [-1,-1,2,1,-1,-1]\n<strong>Explanation:<\/strong> After the first day full lakes are [1]\nAfter the second day full lakes are [1,2]\nAfter the third day, we dry lake 2. Full lakes are [1]\nAfter the fourth day, we dry lake 1. There is no full lakes.\nAfter the fifth day, full lakes are [2].\nAfter the sixth day, full lakes are [1,2].\nIt is easy that this scenario is flood-free. [-1,-1,1,2,-1,-1] is another acceptable scenario.\n<\/pre>\n\n\n\n<p><strong>Example 3:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> rains = [1,2,0,1,2]\n<strong>Output:<\/strong> []\n<strong>Explanation:<\/strong> After the second day, full lakes are  [1,2]. We have to dry one lake in the third day.\nAfter that, it will rain over lakes [1,2]. It's easy to prove that no matter which lake you choose to dry in the 3rd day, the other one will flood.\n<\/pre>\n\n\n\n<p><strong>Example 4:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> rains = [69,0,0,0,69]\n<strong>Output:<\/strong> [-1,69,1,1,-1]\n<strong>Explanation:<\/strong> Any solution on one of the forms [-1,69,x,y,-1], [-1,x,69,y,-1] or [-1,x,y,69,-1] is acceptable where 1 &lt;= x,y &lt;= 10^9\n<\/pre>\n\n\n\n<p><strong>Example 5:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> rains = [10,20,20]\n<strong>Output:<\/strong> []\n<strong>Explanation:<\/strong> It will rain over lake 20 two consecutive days. There is no chance to dry any lake.\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>1 &lt;= rains.length &lt;= 10^5<\/code><\/li><li><code>0 &lt;= rains[i] &lt;= 10^9<\/code><\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: Binary Search<\/strong><\/h2>\n\n\n\n<p>Store the days we can dry a lake in a treeset.<br>Store the last day when a lake becomes full in a hashtable.<br>Whenever we encounter a full lake, try to find the first available day that we can dry it. If no such day, return no answer.<\/p>\n\n\n\n<p>Time complexity: O(nlogn)<br>Space complexity: O(n)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"C++\">\n\/\/ Author: Huahua\nclass Solution {\npublic:\n  vector<int> avoidFlood(vector<int>& rains) {   \n    const int n = rains.size();\n    vector<int> ans(n, -1);\n    unordered_map<int, int> full; \/\/ lake -> day\n    set<int> dry; \/\/ days we can dry lakes.\n    for (int i = 0; i < n; ++i) {\n      const int lake = rains[i];\n      if (lake > 0) {\n        if (full.count(lake)) {\n          \/\/ Find the first day we can dry it.\n          auto it = dry.upper_bound(full[lake]);\n          if (it == end(dry)) return {};\n          ans[*it] = lake;\n          dry.erase(it);\n        }\n        full[lake] = i;\n      } else {\n        dry.insert(i);\n        ans[i] = 1;\n      }\n    }\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>Your country has an infinite number of lakes. Initially, all the lakes are empty, but when it rains over the&nbsp;nth&nbsp;lake, the&nbsp;nth&nbsp;lake becomes full of water.&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[149],"tags":[52,82,73,177],"class_list":["post-6959","post","type-post","status-publish","format-standard","hentry","category-binary-search","tag-binary-search","tag-hashtable","tag-heap","tag-medium","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6959","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=6959"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6959\/revisions"}],"predecessor-version":[{"id":6961,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6959\/revisions\/6961"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=6959"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=6959"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=6959"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}