# 15.11.2023 [1846. Maximum Element After Decreasing and Rearranging]
Max number from converting array to non decreasing
15.11.2023
1846. Maximum Element After Decreasing and Rearranging medium
blog post
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/405
Problem TLDR
Max number from converting array to non decreasing
Intuition
First, sort the array. Now, for every missing number, 1 3 5
-> 2
we can take one of the numbers from the highest, 1 2 3
.
We can use a counter and a Priority Queue.
For example:
array: 1 5 100 100 100
counter: 1 2 3 4 5
Approach
Let’s use some Kotlin’s sugar:
with
asList
Complexity
Time complexity:
O(nlog(n))Space complexity:
O(n)
Code
fun maximumElementAfterDecrementingAndRearranging(arr: IntArray): Int =
with(PriorityQueue<Int>().apply { addAll(arr.asList()) }) {
var max = 0
while (isNotEmpty()) if (poll() > max) max++
max
}
Shorter version