1846. Maximum Element After Decreasing and Rearranging

MediumView on LeetCode

Array Greedy Sorting

Time: O(n log n)

Space: O(1)

Problem Overview

You may decrease any element and reorder freely.

Intuition

You may decrease any element and reorder freely. In sorted order the constraints are arr[0] = 1 and each step increases by at most 1 — so the array is as steep as possible while staying valid. After sorting, pin the minimum to 1, then each next value is capped at previous + 1 but never increased. The last element is the maximum achievable.

Algorithm

1Sort arr ascending.
2Set arr[0] = 1.
3For i from 1 to n − 1: arr[i] = min(arr[i], arr[i − 1] + 1).
4Return arr[n − 1].

Example Walkthrough

Input: arr = [3, 9, 7, 3, 2, 5, 3, 9, 0, 1]

1.Sorted: 0,1,2,3,3,3,5,7,9,9 → force start 1, then 1,2,3,3,3,4,5,6,7.

Output: 7

Common Pitfalls

•Sort first — rearranging means you pick the order after decreases.
•Use min, not max — you only decrease values.
•arr[0] must be exactly 1, not min(arr).

1846.cs

// Approach: Sort, force arr[0] = 1, then greedily cap each element to at most previous + 1.
// This satisfies arr[i] - arr[i-1] <= 1 while keeping values as large as possible.
// Time: O(n log n) Space: O(1) excluding sort
public class Solution
{
    public int MaximumElementAfterDecrementingAndRearranging(int[] arr)
    {
        Array.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];
    }
}

Was this solution helpful?