Commit7947052

authored

Create 2971-find-polygon-with-the-largest-perimeter.kt

1 parentbf0a87e commit7947052Copy full SHA for 7947052

File tree

+55

-0

lines changed

+55

-0

lines changed

Lines changed: 55 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,55 @@`
	`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`	`+}`

Comments

(0)