Problem statement

https://leetcode.com/problems/avoid-flood-in-the-city/

Solution

Actually quite difficult problem, I think level should be hard. The idea is to use greedy strategy, but we need to be careful. Denote by

  1. res is the array where we keep our result.
  2. free is days where we allowed to empty some lake.
  3. filled is dictionary, where for every lake we keep the day it was filled.

We need to traverse our day, lake and we have the following logic:

  1. if lake, that is if it is not dry day and this lake is not filled yet, we update filled[lake] = day.
  2. if lake, that is if it is not dry day and this lake is already filled, then we need to dry it before. For this we need to find the smallest candidate among free days when we can feel it, such that it is bigger than filled[lake], that is we need to dry our lake in interval [filled[lake], day] - in fact second condition always holds true.. Why we want to choose the smallest one in this interval? Because if we choose some other day, set of free days will be strictly bigger (in sence of a1 <= b1, ..., an <= bn and we have at least one <) and on each step we have restriction > filld[lake] and we will have more candidates if we choose smallest free_day.
  3. If it happens that biggest free_day is smaller than filled[lake], it means that we can not save our city and we return [].
  4. Finally, if we have free day, we update free.

Notice, that we need to keep sorted list here, because we want to insert and delete from list quickly.

Complexity

Time complexity is O(n log n), space complexity is O(n).

Code

from sortedcontainers import SortedList

class Solution:
    def avoidFlood(self, rains):
        res, free, filled = [-1]*len(rains), SortedList([-1]), {}
        
        for day, lake in enumerate(rains):
            if lake: 
                if lake not in filled:
                    filled[lake] = day
                else:
                    if free[-1] > filled[lake]:
                        dry_day = free.bisect_left(filled[lake])
                        res[free.pop(dry_day)] = lake
                        filled[lake] = day
                    else:
                        return []
            else:
                res[day] = 1
                free.add(day)

        return res