1846. Maximum Element After Decreasing and Rearranging LeetCode Solution
In this guide, you will get 1846. Maximum Element After Decreasing and Rearranging LeetCode Solution with the best time and space complexity. The solution to Maximum Element After Decreasing and Rearranging problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Maximum Element After Decreasing and Rearranging
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 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.
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.
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
Complexity Analysis
Time Complexity: O(\texttt{sort})
Space Complexity: O(\texttt{sort})
1846. Maximum Element After Decreasing and Rearranging LeetCode Solution in C++
class Solution {
public:
int maximumElementAfterDecrementingAndRearranging(vector<int>& arr) {
ranges::sort(arr);
arr[0] = 1;
for (int i = 1; i < arr.size(); ++i)
arr[i] = min(arr[i], arr[i - 1] + 1);
return arr.back();
}
}; /* code provided by PROGIEZ */
1846. Maximum Element After Decreasing and Rearranging LeetCode Solution in Java
class Solution {
public int maximumElementAfterDecrementingAndRearranging(int[] arr) {
Arrays.sort(arr);
arr[0] = 1;
for (int i = 1; i < arr.length; ++i)
arr[i] = Math.min(arr[i], arr[i - 1] + 1);
return arr[arr.length - 1];
}
} // code provided by PROGIEZ
1846. Maximum Element After Decreasing and Rearranging LeetCode Solution in Python
class Solution:
def maximumElementAfterDecrementingAndRearranging(
self, arr: list[int],
) -> int:
arr.sort()
arr[0] = 1
for i in range(1, len(arr)):
arr[i] = min(arr[i], arr[i - 1] + 1)
return arr[-1] # code by PROGIEZ
