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] <= 109Problem Overview: You can rearrange the array in any order and decrease any element to any smaller positive value. After modification, the array must satisfy two rules: arr[0] = 1 and arr[i] - arr[i-1] ≤ 1. The goal is to maximize the final element arr[n-1]. The challenge is deciding how to reshape values so the sequence grows as much as possible without violating the constraint.
Approach 1: Greedy with Sorting (Time: O(n log n), Space: O(1) or O(log n))
This approach relies on sorting and a greedy adjustment step. First sort the array so smaller values appear earlier. Set the first element to 1. Then iterate from left to right and restrict each value to at most previous + 1. If the current value is larger, decrease it to prev + 1. If it's already smaller, keep it as is because decreasing further would only reduce the final maximum. Sorting guarantees the smallest feasible sequence growth, while the greedy rule ensures the array increases by at most one each step. The final value of the last element becomes the maximum achievable element. This solution is straightforward and works well for most interview scenarios involving sorting and greedy constraints.
Approach 2: Counting Sort-Based Greedy (Time: O(n), Space: O(n))
The values only matter up to n, because the maximum valid sequence length cannot exceed the array size. Instead of sorting, build a frequency array where values greater than n are capped at n. Then simulate constructing the sequence from 1 upward. Track how many numbers are available to extend the sequence. At each step, if at least one unused number exists, increase the current maximum by one. Extra numbers become carry-over that help fill future positions. This effectively simulates the greedy growth of the sequence without explicitly sorting the array. The result is a linear-time solution using counting logic, which is common in optimized array problems.
Recommended for interviews: The greedy sorting approach is the expected solution in most interviews because it is easy to reason about and implement correctly in a few lines. The counting approach demonstrates deeper optimization by removing the O(n log n) sort and replacing it with linear frequency tracking. Showing the sorted greedy first proves you understand the constraint transformation, while the counting variant shows strong algorithmic awareness.
This 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.
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.
Time Complexity: O(n), due to the pass over the array to count elements.
Space Complexity: O(n), primarily due to the count array.
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.
| 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. |
| Sorting + Greedy Algorithm | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy with Sorting | O(n log n) | O(1) or O(log n) | General solution. Easy to implement and explain in interviews. |
| Counting Sort-Based Greedy | O(n) | O(n) | When optimizing away sorting or when input size is large. |
Maximum Element After Decreasing and Rearranging - Leetcode 1846 - Python • NeetCodeIO • 7,725 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