C# SortedSet O(nlogn)
.net\'s SortedSet is implemented using a red/black tree, which would have been perfect for this problem except the SortedSet was engineered in a preschool. To b
.net\'s ```SortedSet``` is implemented using a red/black tree, which would have been perfect for this problem except the ```SortedSet``` was engineered in a preschool. To be included in .net, ```SortedSet``` needed to be engineered for a very narrow application to avoid reusability. Despite offering the (```GetViewBetween```) method which could satisfy most red/black tree use cases, it was intentionally implemented against the nature of the red/black tree to make sure it performed in O(n) time instead of the more stait forward O(logn) time implementation.\n\nJust incase someone else out there also wanted to see if their algorithm would have worked efficiently had ```SortedSet``` been outsourced to a gibbon instead of implemented inhouse, lets solve the problem by fixing ```SortedSet``` by emiting some IL code at runtime:\n\n```\nusing System.Reflection;\nusing System.Linq.Expressions;\n\npublic class Solution {\n    public int[] AvoidFlood(int[] rains) {\n        var dry = new SortedSet<int>();\n        var lakes = new Dictionary<int, int>();\n        for (int i = 0; i < rains.Length; ++i) {\n            if (rains[i] == 0) \n                if (lakes.Count > dry.Count) dry.Add(i);\n                else rains[i] = 1;\n            else if (lakes.ContainsKey(rains[i])) \n                if (lakes[rains[i]] + 1 < i) {\n                    var option = dry.FindSuper(lakes[rains[i]] + 1);\n                    if (!option.HasValue) return Array.Empty<int>();\n                    dry.Remove(option.Value);\n                    rains[option.Value] = rains[i];\n                    lakes[rains[i]] = i;\n                    rains[i] = -1;\n                } else return Array.Empty<int>();\n            else (lakes[rains[i]], rains[i]) = (i, -1);\n        }\n        \n        foreach (var day in dry) rains[day] = 1;\n        return rains;\n    }\n}\n\npublic interface INode {\n\tint Value { get; }\n\tINode Left { get; }\n\tINode Right { get; }\n}\n\npublic static class Extensions {\n\tpublic static INode GetRoot(this SortedSet<int> set) => Node.Create(_root(set));\n\t\n\tpublic static int? FindSuper(this SortedSet<int> set, int value) {\n\t\tvar ansc = default(INode);\n\t\tvar node = set.GetRoot();\n\t\twhile (node != null) {\n\t\t\tif (value < node.Value) (ansc, node) = (node, node.Left);\n\t\t\telse if (value > node.Value) node = node.Right;\n\t\t\telse return node.Value;\n\t\t}\n\t\treturn ansc?.Value;\n\t}\n\n\tprivate static readonly Type __set = typeof(SortedSet<int>);\n\tprivate static readonly Type __node = __set.GetNestedType("Node", BindingFlags.NonPublic).MakeGenericType(new[] { typeof(int) });\n\tprivate static readonly Func<SortedSet<int>, object> _root;\n\t\n\tstatic Extensions() {\n\t\tvar param = Expression.Parameter(__set);\n\t\tvar root = Expression.Field(param, "root");\n\t\t_root = Expression.Lambda<Func<SortedSet<int>, object>>(root, param).Compile();\n\t}\n\t\n\tprivate class Node : INode {\n\t\tprivate readonly object _node;\n\t\tprivate Node(object node) => _node = node;\n\t\tpublic static INode Create(object node) => node == null ? null : new Node(node);\n\n\t\tpublic int Value => _value(_node);\n\t\tpublic INode Left => Node.Create(_left(_node));\n\t\tpublic INode Right => Node.Create(_right(_node));\n\n\t\tprivate static readonly Func<object, object> _left;\n\t\tprivate static readonly Func<object, object> _right;\n\t\tprivate static readonly Func<object, int> _value;\n\n\t\tstatic Node() {\n\t\t\tvar param = Expression.Parameter(typeof(object));\n\t\t\tvar cast = Expression.Convert(param, __node);\n\t\t\tvar left = Expression.Property(cast, "Left");\n\t\t\tvar right = Expression.Property(cast, "Right");\n\t\t\tvar item = Expression.Property(cast, "Item");\n\t\t\t_left = Expression.Lambda<Func<object, object>>(left, param).Compile();\n\t\t\t_right = Expression.Lambda<Func<object, object>>(right, param).Compile();\n\t\t\t_value = Expression.Lambda<Func<object, int>>(item, param).Compile();\n\t\t}\n\t}\n}\n```\n\n\n
[]