Simplest Py3 solution so far - 100% space percentile
After going through a lot of JAVA solutions, I was trying hard to find the equivalent of the JAVA TreeMap and it\'s ceiling function (the ceiling function yield
After going through a lot of JAVA solutions, I was trying hard to find the equivalent of the JAVA TreeMap and it\'s ceiling function (the ceiling function yields the next highest element if possible, given a TreeMap and a certain input element)\n\nHere I am using the `bisect_right` function, applicable on sorted Py lists to yield the next greatest element (given the list and an input element)\n\nThis has been a recreation of the best Java solution so far (https://leetcode.com/problems/avoid-flood-in-the-city/discuss/697701/Java-nlog(n)-find-zero-that-can-be-used-to-empty-the-fullfilled-lake)\n\nI tried my own solution during the contest earlier today, but I kept getting TLE (it passed 74 of 78 test cases) \nHere at: https://leetcode.com/submissions/detail/356415451/\n\nThe complexity run time is O(nlogn)\n\nThe approach elaborated:\nStep 1: Create a dictionary `map` and a SortedSet `z` (Many Python approaches use Heap. But it\'s not a direct approach) and a result Array `res` of size same as that of the input array `rains` with all elements zero (or anything else, we\'ll update them)\n\nStep 2: \nIterate through the input array `rains` and keep storing the location of the `zero` value (indicating available day to drain the lakes). If the input is non-zero, we have to check if this lake has been mentioned before.\nIf it has been mentioned before, find the earlier occurrence and check if there is a zero value occuring any day after the \'earlier occurrence\'. If there isn\'t such an occurrence, the `flood-unavoidable condition` has been reached. End and return solution.\nElse, if there is an available zero day, pull it out of the zero array, and use it up.\nRemember to keep populating the result array with the appropriate values.\n\n\n```\nfrom sortedcontainers import SortedList\nfrom bisect import bisect_right\nclass Solution:\n    def avoidFlood(self, rains: List[int]) -> List[int]:\n        mapping = {}\n        z = SortedList()\n        res = [0]*len(rains)\n        for i in range(len(rains)):\n            if(rains[i]==0):\n                z.add(i)\n            else:\n                if(rains[i] in mapping):\n                    kx = mapping[rains[i]]\n                    n=bisect_right(z,kx)\n                    if(n==len(z)):\n                        return([])\n                    kk=n\n                    n=z[n]\n                    res[n]=rains[i]\n                    del z[kk]\n                res[i]=-1\n                mapping[rains[i]]=i\n        while(z):\n            k = z.pop()\n            res[k]=1\n        return(res)\n```\n\nDo you have a different idea in mind, or a more efficient solution, or need some clarification?\nPlease let me know!\n\n\n\n
['Tree', 'Python3']