# LeetCode 1846. Maximum Element After Decreasing and Rearranging

## Intuition

- Set the first element
`arr[0]`

to 1. - Limit the difference of two adjacent elements to 1 or less than 1, which means
`arr[i+1]`

is the same as`arr[i]`

or equal to`arr[i] + 1`

. - Return the maximum possible value in
`arr`

.

## Approach

Set

`arr[0]`

to 1 (that’s the rule of this challenge).Set

`max`

to 1, which represents the maximum possible value in arr is 1.Sort

`arr`

in ascending order.Iterate over

`arr`

from the second element`arr[1]`

(because`arr[0]`

has already been set to 1):- Set
`arr[i]`

to`max`

if it’s the same as or higher than`max`

, then increase`max`

by 1. - Do nothing if
`arr[i]`

is smaller than`max`

(which couldn’t happen because`arr`

has already been sorted in ascending order).

- Set
Return

`max`

.

Pseudocode of `maximumElementAfterDecrementingAndRearranging`

:

1 | maximumElementAfterDecrementingAndRearranging(arr): |

## Complexity

Time complexity: $O(nlogn)$.

- Sorting
`arr`

in ascending order is $O(nlogn)$. - Iterate over
`arr`

to update`arr`

and`max`

is $O(n)$. - Overall complexity is $O(nlogn)$.
- $n$ is the total size of
`arr`

.

- Sorting
Space complexity: $O(1)$.

## Code

1 | class Solution { |