You are given an array of positive integers arr. Perform some operations (possibly none) on arr so that it satisfies these conditions:
arr must be 1.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:
arr to a smaller positive integer.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 rearrangingarrso it becomes[1,2,2,2,1]. The largest element inarris 2.
Example 2:
Input: arr = [100,1,1000] Output: 3 Explanation: One possible way to satisfy the conditions is by doing the following: 1. Rearrangearrso 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. Nowarr = [1,2,3], whichsatisfies the conditions. The largest element inarr 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 <= 1051 <= arr[i] <= 109This approach involves sorting the array first. After sorting, we iterate over the array from the first element onwards, setting each element to be the minimum between its current value and the value of the previous element plus 1. This ensures the conditions are met, i.e., the first element is 1 and the difference between adjacent elements is <= 1.
We first sort the array using qsort. Then, starting from the first index (0), we set it to 1 as the condition requires. For every subsequent element, we ensure that it is either its current value or the previous element + 1, whichever is smaller. This ensures the absolute difference between adjacent elements is at most 1.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1) as we modify the array in place.
This approach leverages the counting sort technique which avoids sorting the entire array directly. Instead, it uses a frequency array to count occurrences of each element. Then, reconstruct the final array by checking counts and adjusting values accordingly to ensure the maximum element is achieved while meeting the constraints.
In C, we use calloc to create a count array which logs the frequency of each element. The counting concludes, and array values are adjusted using the count data structure to maximize the array while meeting the constraints.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), due to the pass over the array to count elements.
Space Complexity: O(n), primarily due to the count array.
| Approach | Complexity |
|---|---|
| Greedy Approach with Sorting | Time Complexity: O(n log n) due to sorting. |
| Counting Sort-Based Approach | Time Complexity: O(n), due to the pass over the array to count elements. |
Maximum Element After Decreasing and Rearranging - Leetcode 1846 - Python • NeetCodeIO • 7,309 views views
Watch 9 more video solutions →Practice Maximum Element After Decreasing and Rearranging with our built-in code editor and test cases.
Practice on FleetCode