Maximum Element After Decreasing and Rearranging

Med

#1686Time: O(N log N) The dominant operation is sorting the array, which typically takes O(N log N) time. The subsequent pass through the array takes O(N) time.Space: O(log N) or O(N) This depends on the implementation of the sorting algorithm. In Java, `Arrays.sort` for primitive types has a space complexity of O(log N) for the recursion stack of quicksort. If a copy of the array is needed, it would be O(N).

Patterns

Greedy

Algorithms

Sorting

Data structures

Array

Prompt

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:

arr

Example 2:

arr

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 <= 10⁵
1 <= arr[i] <= 10⁹

Approaches

2 approaches with complexity analysis and trade-offs.

The core idea is that to maximize the final element, we should make the array a non-decreasing sequence. By sorting the input array, we can process the elements in increasing order. This allows us to greedily construct the target array by ensuring each element satisfies the condition arr[i] <= arr[i-1] + 1 while being as large as possible.

Algorithm

Sort the input array arr in non-decreasing order.
Set the first element arr[0] to 1 to satisfy the first condition.
Iterate through the array from the second element (i = 1 to n-1).
For each element arr[i], if it violates the condition arr[i] - arr[i-1] <= 1 (i.e., arr[i] > arr[i-1] + 1), decrease its value to arr[i-1] + 1. This is the minimal change to satisfy the condition while keeping the value as large as possible.
After the loop, the array is valid, and its maximum element is the last one, arr[n-1]. Return this value.

Walkthrough

This approach leverages the power of rearranging by sorting the array first. Sorting is a key step because it allows us to build the resulting array greedily and optimally.

Sort the array: We sort arr in non-decreasing order. For a non-decreasing array, the condition abs(arr[i] - arr[i-1]) <= 1 simplifies to arr[i] <= arr[i-1] + 1.
Set the first element: The first condition requires arr[0] to be 1. We enforce this by setting arr[0] = 1. Since the problem states all elements are positive, the original arr[0] (after sorting) is at least 1, so we only ever decrease it if it's larger than 1.
Greedily adjust subsequent elements: We iterate from the second element (i = 1). For each arr[i], we must ensure it's no more than arr[i-1] + 1. If arr[i] is already within this bound, we leave it, as we want to keep values high. If arr[i] > arr[i-1] + 1, we must decrease it. To maximize the final result, we perform the minimal decrease, setting arr[i] = arr[i-1] + 1.
Return the maximum: After this process, the array satisfies all conditions, and since it's non-decreasing, the maximum element is the last one, arr[arr.length - 1].

1import java.util.Arrays;2 3class Solution {4    public int maximumElementAfterDecrementingAndRearranging(int[] arr) {5        Arrays.sort(arr);6        arr[0] = 1;7        for (int i = 1; i < arr.length; i++) {8            if (arr[i] > arr[i - 1] + 1) {9                arr[i] = arr[i - 1] + 1;10            }11        }12        return arr[arr.length - 1];13    }14}

Complexity

Time

O(N log N) The dominant operation is sorting the array, which typically takes O(N log N) time. The subsequent pass through the array takes O(N) time.

Space

O(log N) or O(N) This depends on the implementation of the sorting algorithm. In Java, `Arrays.sort` for primitive types has a space complexity of O(log N) for the recursion stack of quicksort. If a copy of the array is needed, it would be O(N).

Trade-offs

Pros

The logic is intuitive and relatively easy to implement.
If modifying the input array is allowed, the space complexity is very low (O(log N) for sort recursion stack).

Cons

The time complexity is dominated by the sorting step, making it less efficient than a linear-time solution.

This approach improves upon the sorting-based method by avoiding the O(N log N) sort. We observe that the exact values of numbers larger than the array's length n don't matter, as the maximum possible result is n. We can use a counting array to store the frequency of each number (capping large numbers at n). Then, we can iterate through the counts to greedily determine the longest possible sequence 1, 2, 3, ... which gives us the maximum element.

Algorithm

Let n be the length of the array. Create a frequency array counts of size n + 1.
Iterate through the input array arr. For each number num, increment counts[min(num, n)]. This treats any number larger than n as n.
Initialize a variable ans = 0, which will track the maximum element of the sequence 1, 2, ... we can form.
Iterate with a variable v from 1 to n.
In each iteration, update ans using the formula: ans = min(v, ans + counts[v]). This calculates the new length of our constructible sequence by adding the available numbers of value v, capped by the value v itself.
After the loop, ans holds the maximum possible element value. Return ans.

Walkthrough

This method achieves linear time complexity by avoiding a full sort and instead using counting.

Observation and Capping: The maximum possible value in the final array cannot exceed its length, n. An array like [1, 2, 3, ..., n] has a maximum of n. Any number in the original array arr[i] > n is at least as useful as n, but no more useful, because the target value at any index j is at most j+1 <= n. Therefore, we can treat any number > n as if it were n.
Frequency Counting: We create a counts array of size n + 1. We iterate through arr, and for each number num, we increment counts[min(num, n)]. This takes O(N) time and O(N) space.
Greedy Construction Simulation: We can now determine the maximum element without sorting. Let ans be the length of the valid prefix 1, 2, ..., ans that we can form. Initially, ans = 0. We iterate through the possible values v from 1 to n. At each step v, we have counts[v] numbers from the original array with value v. These numbers, combined with the numbers we've already processed (which have formed a sequence up to ans), can be used to extend our sequence. The total number of elements available to form a sequence is ans + counts[v]. However, since the new numbers we are adding have a value of v, the maximum value in the sequence we can form is capped at v. Therefore, the new length of our sequence ans becomes min(v, ans + counts[v]).
Final Result: After iterating v from 1 to n, the final value of ans will be the maximum element possible in the modified array.

1class Solution {2    public int maximumElementAfterDecrementingAndRearranging(int[] arr) {3        int n = arr.length;4        int[] counts = new int[n + 1];5        for (int num : arr) {6            counts[Math.min(num, n)]++;7        }8        9        // ans represents the length of the prefix 1, 2, ..., ans we can form.10        int ans = 0;11        for (int v = 1; v <= n; v++) {12            // We have 'ans' elements from values < v, and 'counts[v]' elements with value v.13            // Total elements available are ans + counts[v].14            // These can form a sequence up to length ans + counts[v].15            // However, since the values are capped by v, the max element can't exceed v.16            ans = Math.min(v, ans + counts[v]);17        }18        19        return ans;20    }21}

Complexity

Time

O(N) The algorithm involves two main passes. The first pass populates the `counts` array, taking O(N) time. The second pass iterates from 1 to `n`, taking O(N) time. The total time complexity is O(N).

Space

O(N) We need an auxiliary array `counts` of size `n + 1` to store the frequencies of the numbers, where `n` is the length of the input array.

Trade-offs

Pros

Achieves optimal O(N) time complexity.
The logic is a clever way to bypass sorting by focusing on element counts.

Cons

Requires extra space proportional to the size of the input array, which could be a concern for very large N if memory is highly constrained.

Solutions

Solution

1public class Solution { public int MaximumElementAfterDecrementingAndRearranging ( int [] arr ) { Array . Sort ( arr ); int n = arr . Length ; arr [ 0 ] = 1 ; for ( int i = 1 ; i < n ; ++ i ) { arr [ i ] = Math . Min ( arr [ i ], arr [ i - 1 ] + 1 ); } return arr [ n - 1 ]; } }

1class Solution {2public3  int maximumElementAfterDecrementingAndRearranging(int[] arr) {4    Arrays.sort(arr);5    arr[0] = 1;6    int ans = 1;7    for (int i = 1; i < arr.length; ++i) {8      int d = Math.max(0, arr[i] - arr[i - 1] - 1);9      arr[i] -= d;10      ans = Math.max(ans, arr[i]);11    }12    return ans;13  }14}

1class Solution {2public:3  int maximumElementAfterDecrementingAndRearranging(vector<int> &arr) {4    sort(arr.begin(), arr.end());5    arr[0] = 1;6    int ans = 1;7    for (int i = 1; i < arr.size(); ++i) {8      int d = max(0, arr[i] - arr[i - 1] - 1);9      arr[i] -= d;10      ans = max(ans, arr[i]);11    }12    return ans;13  }14};

1class Solution:2    def maximumElementAfterDecrementingAndRearranging(self, arr: List[int]) -> int: arr . sort() arr[0] = 1 for i in range(1, len(arr)): d = max(0, arr[i] - arr[i - 1] - 1) arr[i] -= d return max(arr)

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem