Maximum Element After Decreasing and

lcpy gen -n 1846   # by problem number
lcpy gen -s maximum_element_after_decreasing_and_rearranging   # by problem name

​

Problem

• The value of the first element in arr must be 1.
• The absolute difference between any 2 adjacent elements must be less than or equal to 1. In other words, abs(arr[i] - arr[i - 1]) <= 1 for each i where 1 <= i < arr.length (0-indexed). abs(x) is the absolute value of x.

• Decrease the value of any element of arr to a smaller positive integer.
• Rearrange the elements of arr to be in any order.

​

Examples

Input: arr = [2,2,1,2,1]
Output: 2

Input: arr = [100,1,1000]
Output: 3

Input: arr = [1,2,3,4,5]
Output: 5

​

Constraints

• 1 <= arr.length <= 10^5
• 1 <= arr[i] <= 10^9

​

Solution

class Solution:
    # Time: O(n log n)
    # Space: O(1) extra (sorting in place)
    def maximum_element(self, arr: list[int]) -> int:
        arr.sort()
        prev = 0
        for value in arr:
            prev = min(prev + 1, value)
        return prev

​

Complexity

​

Tags