|
| 1 | +// Using TreeSet and linear scan in getIntervals() method |
| 2 | +classSummaryRanges() { |
| 3 | +val ranges=TreeSet<Int>() |
| 4 | + |
| 5 | +funaddNum(value:Int) { |
| 6 | + ranges.add(value) |
| 7 | + } |
| 8 | + |
| 9 | +fungetIntervals():Array<IntArray> { |
| 10 | +val res=LinkedList<IntArray>() |
| 11 | + ranges.forEach { |
| 12 | +if (res.isNotEmpty()&& res.peekLast()[1]+1== it) |
| 13 | + res.peekLast()[1]= it |
| 14 | +else |
| 15 | + res.addLast(intArrayOf(it, it)) |
| 16 | + } |
| 17 | +return res.toTypedArray() |
| 18 | + } |
| 19 | +} |
| 20 | + |
| 21 | +// Using TreeMap and binary search scan in getIntervals() method, small optimization technically but still same time complexity as above solution |
| 22 | +classSummaryRanges() { |
| 23 | +val rgs=TreeMap<Int,IntArray>() |
| 24 | + |
| 25 | +funaddNum(v:Int) { |
| 26 | +if (rgs.containsKey(v))return |
| 27 | + |
| 28 | +val l= rgs.lowerKey(v) |
| 29 | +val h= rgs.higherKey(v) |
| 30 | + |
| 31 | +if (l!=null&& h!=null&& rgs.get(l)!![1]+1== v&& h== v+1 ) { |
| 32 | + rgs.get(l)!![1]= rgs.get(h)!![1] |
| 33 | + rgs.remove(h) |
| 34 | + }elseif (l!=null&& rgs.get(l)!![1]+1>= v) { |
| 35 | + rgs.get(l)!![1]= maxOf(v, rgs.get(l)!![1]) |
| 36 | + }elseif (h!=null&& h== v+1) { |
| 37 | + rgs.put(v, intArrayOf(v, rgs.get(h)!![1])) |
| 38 | + rgs.remove(h) |
| 39 | + }else { |
| 40 | + rgs.put(v, intArrayOf(v, v)) |
| 41 | + } |
| 42 | + } |
| 43 | + |
| 44 | +fungetIntervals()= rgs.values.toTypedArray() |
| 45 | +} |
| 46 | + |
| 47 | +// Using Union Find |
| 48 | +classSummaryRanges() { |
| 49 | +val dsu=DSU() |
| 50 | + |
| 51 | +funaddNum(v:Int) { |
| 52 | +if (dsu.exists(v))return |
| 53 | + |
| 54 | + dsu.add(v) |
| 55 | + dsu.union(v, v-1) |
| 56 | + dsu.union(v, v+1) |
| 57 | + } |
| 58 | + |
| 59 | +fungetIntervals()= dsu.getIntervals() |
| 60 | + |
| 61 | +} |
| 62 | + |
| 63 | +classDSU { |
| 64 | +val parent=HashMap<Int,Int>() |
| 65 | +val intervals=TreeMap<Int,IntArray>() |
| 66 | + |
| 67 | +fungetIntervals()= intervals.values.toTypedArray() |
| 68 | + |
| 69 | +funexists(x:Int)= xin parent |
| 70 | + |
| 71 | +funadd(x:Int) { |
| 72 | + parent[x]= x |
| 73 | + intervals[x]= intArrayOf(x, x) |
| 74 | + } |
| 75 | + |
| 76 | +funfind(x:Int):Int { |
| 77 | + parent[x]?:return-1 |
| 78 | + |
| 79 | +if (parent[x]!!!= x) |
| 80 | + parent[x]= find(parent[x]!!) |
| 81 | + |
| 82 | +return parent[x]!! |
| 83 | + } |
| 84 | + |
| 85 | +fununion(x:Int,y:Int) { |
| 86 | +val px= find(x) |
| 87 | +val py= find(y) |
| 88 | + |
| 89 | +if (px==-1|| py==-1)return |
| 90 | + |
| 91 | +val newX= minOf(intervals[py]!![0], intervals[px]!![0]) |
| 92 | +val newY= maxOf(intervals[py]!![1], intervals[px]!![1]) |
| 93 | + |
| 94 | + parent[px]= py |
| 95 | + intervals[py]= intArrayOf(newX, newY) |
| 96 | + intervals.remove(px) |
| 97 | + } |
| 98 | +} |