|
| 1 | +classSolution { |
| 2 | +funlargestPerimeter(nums:IntArray):Long { |
| 3 | + nums.sort() |
| 4 | +var total=0L |
| 5 | +var res=-1L |
| 6 | + |
| 7 | +for (nin nums) { |
| 8 | +if (total> n) |
| 9 | + res= total+ n |
| 10 | + total+= n |
| 11 | + } |
| 12 | + |
| 13 | +return res |
| 14 | + } |
| 15 | +} |
| 16 | + |
| 17 | +// Same logic but a top down approach instead of bottom up as the solution above |
| 18 | +classSolution { |
| 19 | +funlargestPerimeter(nums:IntArray):Long { |
| 20 | + nums.sortDescending() |
| 21 | + |
| 22 | +var sum=0L |
| 23 | +for (nin nums) |
| 24 | + sum+= n |
| 25 | + |
| 26 | +for (nin nums) { |
| 27 | +val rest= sum- n |
| 28 | +if (rest> n)return sum |
| 29 | + sum-= n |
| 30 | + } |
| 31 | + |
| 32 | +return-1L |
| 33 | + } |
| 34 | +} |
| 35 | + |
| 36 | +/* |
| 37 | + * Same intuition as above but use a maxheap instead of sorting. In Kotlin and Java the time complexity is O(nlogn) |
| 38 | + * but using heapify in Python or priority_queue in C++ this will have a time complexity of O(logn + n) ~ O(n) |
| 39 | +*/ |
| 40 | +classSolution { |
| 41 | +funlargestPerimeter(nums:IntArray):Long { |
| 42 | +val max=PriorityQueue<Int> { a, b-> b- a } |
| 43 | +var sum=0L |
| 44 | + |
| 45 | +for (nin nums) { |
| 46 | + sum+= n |
| 47 | + max.add(n) |
| 48 | + } |
| 49 | + |
| 50 | +while (max.isNotEmpty()&& sum<= max.peek()*2) |
| 51 | + sum-= max.poll() |
| 52 | + |
| 53 | +returnif (max.size>=2&& sum>0L) sumelse-1L |
| 54 | + } |
| 55 | +} |