Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Two rains on the same lake require a dry day strictly between them. When the second rain arrives, assign the earliest unused dry day after the previous rain. This satisfies the current deadline while preserving later dry days, which can serve lakes whose earlier rain occurred more recently.

Approach

Track each lake's latest rainy day and keep unused dry-day indices in an ordered collection. Mark rainy output positions -1. On a repeated lake, find the earliest unused dry day after its last rain; if none exists, return an empty array. Otherwise assign that day to the lake and remove it from the collection. Update the lake's last rain after handling it. Unassigned dry days retain the harmless default choice of lake one. Return the constructed schedule if every repeated rain can be matched.

class Solution:
    def avoidFlood(self, rains: List[int]) -> List[int]:
        n = len(rains)
        res = [1] * n
        map = {}
        sl = SortedList()

        for i, x in enumerate(rains):
            if x == 0:
                sl.add(i)
            else:
                res[i] = -1
                if x in map:
                    bs = sl.bisect_left(map[x])
                    if bs == len(sl):
                        return []
                    res[sl[bs]] = x
                    sl.discard(sl[bs])
                map[x] = i

        return res

Complexity analysis

Let n = rains.length. JavaScript's AVL tree guarantees O(log n) worst-case insertion, lower-bound lookup and deletion; with expected constant-time Map operations, total time is O(n log n). Python uses sortedcontainers.SortedList, whose operation costs are documented as approximately logarithmic, giving the usual practical O(n log n) model rather than a strict worst-case guarantee. Its block shifts, splits/merges and positional-index rebuilding can cost more; O(n^2) is a conservative worst-case upper bound for the whole Python scan, not a claim of typical behavior. Both implementations use O(n) auxiliary storage and O(n) output storage.