Maximum Element After Decreasing and Rearranging: Sort and Greedy

You are given an array of positive integers arr. You can decrease any element or rearrange the elements in any order. After your operations, the array must satisfy two conditions: the first element must be 1, and the absolute difference between any two adjacent elements must be <= 1. Return the maximum possible value of any element in the resulting array.

This is LeetCode 1846: Maximum Element After Decreasing and Rearranging, a medium problem that rewards clear thinking about sorting and greedy construction.

Why this problem matters

This problem is a clean example of how sorting transforms a messy arrangement problem into a simple linear scan. Without sorting, you would need to consider every possible rearrangement. With sorting, the problem reduces to a single pass where you greedily build the largest valid sequence.

The pattern of "sort first, then greedily assign values" appears in many problems. Once you recognize it, problems like assigning tasks, scheduling intervals, and distributing resources become much easier to reason about.

The key insight

Since you can rearrange freely and only decrease values, the optimal strategy is to sort the array and then walk left to right. After sorting, you know the smallest values are on the left. You start with 1 (forced by the constraint), and at each position you either keep the sorted value or cap it at prev + 1, whichever is smaller. This greedy approach works because sorting guarantees that later elements are at least as large as earlier ones, so you never need to waste potential by placing a large value early.

The core operation at each index i is: arr[i] = min(arr[i], arr[i-1] + 1). You are capping each value so it does not jump by more than 1 from its predecessor. The last element after this pass is your answer.

The solution

def maxElement(arr):
    arr.sort()
    arr[0] = 1
    for i in range(1, len(arr)):
        arr[i] = min(arr[i], arr[i - 1] + 1)
    return arr[-1]

After sorting, set the first element to 1. Then walk through the array, capping each element at one more than its predecessor. The final element is the answer.

You can also write this without modifying the array, using a single variable:

def maxElement(arr):
    arr.sort()
    prev = 1
    for i in range(1, len(arr)):
        prev = min(arr[i], prev + 1)
    return prev

Both versions do the same thing. The second avoids mutating the input, which is sometimes preferred in interviews.

Visual walkthrough

Complexity analysis

Sorting dominates the time complexity at O(n log n). The greedy pass is O(n). Space is O(1) if you sort in place (or O(n) depending on your language's sort implementation). Since you must inspect every element at least once, and sorting is the tightest bottleneck, this is optimal for this approach.

The building blocks

1. Sort to simplify arrangement

When a problem allows rearranging elements freely, sorting is almost always the right first move. It removes the combinatorial explosion of possible orderings and lets you reason about elements in a predictable order. Here, sorting ensures that each element is at least as large as the one before it, which means you never have to increase a value, only cap it.

2. Greedy forward scan with a running bound

After sorting, the greedy step is a single left-to-right pass where each position depends only on the previous one. You maintain a running maximum that can grow by at most 1 per step. This is the same pattern you see in problems like assigning sequential IDs or building the longest increasing subsequence with a gap constraint.

Edge cases

• Already valid: [1, 2, 3] is already sorted and satisfies all constraints. The answer is 3 with no changes.
• All ones: [1, 1, 1, 1]. After sorting and greedy adjustment, the result stays [1, 1, 1, 1]. The answer is 1.
• Single element: [5]. The first element must be 1, so the answer is 1.
• Large gaps: [1, 1000000000]. Sorted: [1, 1000000000]. After adjustment: [1, 2]. The answer is 2 regardless of how large the second value is.
• Descending input: [5, 4, 3, 2, 1]. Sorted: [1, 2, 3, 4, 5]. Already valid after sorting. The answer is 5.
• All same values: [3, 3, 3]. Sorted: [3, 3, 3]. Adjusted: [1, 2, 3]. Each element gets capped incrementally. The answer is 3.

From understanding to recall

You have read the sort-and-greedily-cap solution and it clicks. Sort the array, set the first element to 1, walk forward capping each value at prev + 1. Simple enough. But will you remember the details when you see this problem in an interview?

The specifics matter: remembering to force arr[0] = 1, using min(arr[i], arr[i-1] + 1) rather than just incrementing, and recognizing that the last element after the pass gives you the answer. These are small details that are easy to mix up under pressure if you have only read the solution once.

Spaced repetition locks it in. You write the sort-and-cap loop from scratch at increasing intervals until it becomes automatic. After a few rounds, the pattern is muscle memory. You see "maximize under adjacent-difference constraints" and the code flows out without hesitation.

Related posts

• Candy - Another greedy problem with adjacent element constraints
• Jump Game II - Greedy forward-scan to reach the end with minimum jumps
• Gas Station - Greedy circular scan to find a valid starting point

CodeBricks breaks the maximum element after decreasing and rearranging problem into its sort-to-simplify and greedy-forward-scan building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a sort-and-greedy question shows up in your interview, you do not think about it. You just write it.