1846. Maximum Element After Decreasing and Rearranging
Description
You are given an array of positive integers arr
. Perform some operations (possibly none) on arr
so that it satisfies these conditions:
- The value of the first element in
arr
must be1
. - 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 eachi
where1 <= i < arr.length
(0-indexed).abs(x)
is the absolute value ofx
.
There are 2 types of operations that you can perform any number of times:
- Decrease the value of any element of
arr
to a smaller positive integer. - Rearrange the elements of
arr
to be in any order.
Return the maximum possible value of an element in arr
after performing the operations to satisfy the conditions.
Example 1:
Input: arr = [2,2,1,2,1] Output: 2 Explanation: We can satisfy the conditions by rearranging arr so it becomes [1,2,2,2,1]. The largest element in arr is 2.
Example 2:
Input: arr = [100,1,1000] Output: 3 Explanation: One possible way to satisfy the conditions is by doing the following: 1. Rearrange arr so it becomes [1,100,1000]. 2. Decrease the value of the second element to 2. 3. Decrease the value of the third element to 3. Now arr = [1,2,3], which satisfies the conditions. The largest element in arr is 3.
Example 3:
Input: arr = [1,2,3,4,5] Output: 5 Explanation: The array already satisfies the conditions, and the largest element is 5.
Constraints:
1 <= arr.length <= 105
1 <= arr[i] <= 109
Solutions
Solution 1: Sorting + Greedy Algorithm
First, we sort the array and then set the first element of the array to $1$.
Next, we start traversing the array from the second element. If the difference between the current element and the previous one is more than $1$, we greedily reduce the current element to the previous element plus $1$.
Finally, we return the maximum element in the array.
The time complexity is $O(n \times \log n)$, and the space complexity is $O(\log n)$. Where $n$ is the length of the array.
1 2 3 4 5 6 7 8 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
|
1 2 3 4 5 6 7 8 9 10 11 |
|
1 2 3 4 5 6 7 8 9 10 11 |
|
1 2 3 4 5 6 7 8 9 10 11 |
|