Scala O(n lg n)
\nimport scala.collection.mutable\n\nobject Solution {\n  def avoidFlood(rains: Array[Int]): Array[Int] = {\n    // lakeToDayToNextDay(lake)(day) = the next day
```\nimport scala.collection.mutable\n\nobject Solution {\n  def avoidFlood(rains: Array[Int]): Array[Int] = {\n    // lakeToDayToNextDay(lake)(day) = the next day on which it rains on lake\n    val lakeToDayToNextDay = rains\n      .zipWithIndex\n      .filter(_._1 > 0)\n      .groupMap(_._1)(_._2)\n      .view\n      .mapValues(days => days.zip(days.tail).toMap)\n      .toMap\n    // (lake, nextDay) ordered by increasing nextDay\n    val lakeAndDayPairs = mutable.PriorityQueue()(Ordering.by[(Int, Int), Int](_._2).reverse)\n    // The set of lakes that are currently full.\n    val fullLakes = mutable.Set[Int]()\n    // The plan for drying the lakes.\n    val plan = Array.fill(rains.length)(-1)\n    for (day <- rains.indices) {\n      rains(day) match {\n        // All lakes are dry.  Any lake is acceptable.\n        case 0 if fullLakes.isEmpty =>\n          plan(day) = 1\n        // Dry the full lake that will flood the soonest.\n        case 0 =>\n          val lake = lakeAndDayPairs.dequeue._1\n          fullLakes -= lake\n          plan(day) = lake\n        // Impossible to prevent flooding.\n        case lake if fullLakes.contains(lake) =>\n          return Array[Int]()\n        // Denote the lake as full, and mark the soonest day it will flood.\n        case lake =>\n          for (nextDay <- lakeToDayToNextDay(lake).get(day)) lakeAndDayPairs.enqueue(lake -> nextDay)\n          fullLakes += lake\n      }\n    }\n    plan\n  }\n}\n```
[]