Maximum Element After Decreasing and Rearranging

How it works

We can avoid sorting by using counting sort. Since the maximum useful value is n (the array length), we count how many elements fall into each value bucket, capping values at n. Then we simulate the greedy process: at each target value from 1 to n, we have a certain number of elements available. The running count tells us how high we can reach.

This works because having more elements at value v means more flexibility to fill positions up to that value. The final running count gives the maximum element achievable.

Steps

1. Create a count array of size n + 1.
2. For each number in the array, increment count[min(num, n)].
3. Initialize prev = 1 (the first position must be 1).
4. For each value from 2 to n:
   • Update prev = min(prev + count[value], value).
5. Return prev.

Complexity

• Time complexity: O(n)
• Space complexity: O(n)

Things to watch for

Trying to Increase Values

The problem only allows decreasing values, not increasing them. A common mistake is to think you can "fix" the array by increasing small values to meet the constraint. If a value is too small, you cannot raise it. Instead, you must accept that gap and move forward, potentially reducing subsequent values to maintain the |arr[i] - arr[i-1]| <= 1 constraint.

Forgetting the First Element Must Be 1

After rearranging and decreasing, the first element must equal exactly 1. Some solutions focus only on the adjacent difference constraint and forget this requirement. Even if you have a sorted array like [2, 3, 4, 5], you must reduce the first element to 1, resulting in [1, 2, 3, 4] at best. The greedy approach handles this by initializing prev = 0 and building from there.

Using Standard Sorting When Counting Sort Suffices

While the sorting-based solution with O(n log n) complexity is correct, it misses an optimization opportunity. Since the maximum useful value is n (the array length), values larger than n can be treated as n. This observation enables a counting sort approach that achieves O(n) time complexity. Recognize when the value range is bounded to choose the most efficient algorithm.

from typing import List

class Solution:
    def maximumElementAfterDecrementingAndRearranging(self, arr: List[int]) -> int:
        n = len(arr)
        count = [0] * (n + 1)

        for num in arr:
            count[min(num, n)] += 1

        prev = 1
        for num in range(2, n + 1):
            prev = min(prev + count[num], num)

        return prev

class Solution {
public:
    int maximumElementAfterDecrementingAndRearranging(vector<int>& arr) {
        int n = arr.size();
        vector<int> count(n + 1, 0);

        for (int num : arr) {
            count[min(num, n)]++;
        }

        int prev = 1;
        for (int num = 2; num <= n; num++) {
            prev = min(prev + count[num], num);
        }

        return prev;
    }
};