LeetCode Entry

1846. Maximum Element After Decreasing and Rearranging

15.11.2023 medium 2023 kotlin

Max number from converting array to non decreasing

1846. Maximum Element After Decreasing and Rearranging medium blog post substack image.png

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: image.png