LeetCode 1846 - Maximum Element After Decreasing and Rearranging

LeetCode Problem 1846

Difficulty: 🟡 Medium
Topics: Array, Greedy, Sorting

Solution

Problem Understanding

The problem provides an array of positive integers and asks us to perform operations to transform it so that two conditions are satisfied: the first element must be 1, and the absolute difference between adjacent elements cannot exceed 1. We are allowed to decrease elements and rearrange the array. The ultimate goal is to maximize the largest element in the resulting array.

The input arr represents arbitrary positive integers, potentially very large (up to 10^9) and with a length up to 10^5. The output is a single integer, representing the maximum achievable element after rearranging and decreasing elements according to the rules.

Key edge cases include arrays where all elements are the same, arrays where the smallest element is not 1, and arrays with very large numbers that need significant decreases. The problem guarantees at least one element and all elements are positive, so we do not need to handle empty arrays or zeros.

Approaches

A brute-force approach would attempt to generate all permutations of the array and then try decreasing each element iteratively to satisfy the adjacency condition. While this would eventually give a correct answer, it is infeasible because the number of permutations grows factorially with array size (O(n!)), which is impossible for n up to 10^5.

The key observation for an optimal solution is that after sorting the array, each element should be at most 1 greater than the previous element to satisfy the adjacency condition. We can start from 1 and iterate through the sorted array, updating each element to be the minimum of its current value and one more than the previous element. This ensures the first element is 1, adjacent differences are ≤1, and the maximum element is as large as possible under the constraints.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n!)	O(n)	Generate all permutations and decrease elements iteratively
Optimal	O(n log n)	O(1) or O(n)	Sort array and enforce adjacency condition greedily

Algorithm Walkthrough

1. Sort the array: Sorting ensures that we can assign values sequentially while only decreasing elements if needed. It allows the smallest numbers to come first and ensures the first element is easy to set to 1.
2. Initialize the first element: Set arr[0] = 1. This satisfies the requirement that the first element must be 1.
3. Iterate through the rest of the array: For each index i from 1 to n-1, set arr[i] = min(arr[i], arr[i-1] + 1). This guarantees the absolute difference condition while maximizing each element locally.
4. Return the last element: After processing, the last element in the modified array will be the maximum possible value since each element is at most 1 greater than the previous element.

Why it works: Sorting ensures that we never need to increase any element, only decrease, which is allowed. The greedy assignment of min(current_value, previous + 1) ensures the adjacency condition is maintained while maximizing each element. The invariant is that after processing index i, all elements from 0 to i satisfy both the adjacency condition and the first-element condition.

Python Solution

from typing import List

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

The Python implementation sorts the array first. It then explicitly sets the first element to 1, and iterates through the rest of the array, ensuring each element does not exceed 1 more than the previous element. The final maximum value is the last element of the array.

Go Solution

import "sort"

func maximumElementAfterDecrementingAndRearranging(arr []int) int {
    sort.Ints(arr)
    arr[0] = 1
    for i := 1; i < len(arr); i++ {
        if arr[i] > arr[i-1]+1 {
            arr[i] = arr[i-1] + 1
        }
    }
    return arr[len(arr)-1]
}

In Go, we use sort.Ints to sort the slice. The first element is set to 1, and each subsequent element is adjusted if it exceeds one more than the previous element. This is the direct translation of the Python greedy algorithm.

Worked Examples

Example 1: arr = [2,2,1,2,1]

Sorted: [1,1,2,2,2]

Set first element: [1,1,2,2,2]

Iterate: [1,2,2,2,2]

Maximum element: 2

Example 2: arr = [100,1,1000]

Sorted: [1,100,1000]

Set first element: [1,100,1000]

Iterate: [1,2,3]

Maximum element: 3

Example 3: arr = [1,2,3,4,5]

Sorted: [1,2,3,4,5]

Set first element: [1,2,3,4,5]

Iterate: [1,2,3,4,5]

Maximum element: 5

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Sorting dominates; single pass adjustment is O(n)
Space	O(1)	In-place adjustment after sorting; or O(n) if sorting creates a copy

The time complexity is primarily due to sorting. Space is minimal since we adjust the array in place. This scales efficiently for arrays up to size 10^5.

Test Cases

# Provided examples
assert Solution().maximumElementAfterDecrementingAndRearranging([2,2,1,2,1]) == 2  # simple adjustments
assert Solution().maximumElementAfterDecrementingAndRearranging([100,1,1000]) == 3  # large decrease required
assert Solution().maximumElementAfterDecrementingAndRearranging([1,2,3,4,5]) == 5  # already valid

# Edge cases
assert Solution().maximumElementAfterDecrementingAndRearranging([1]) == 1  # single element
assert Solution().maximumElementAfterDecrementingAndRearranging([5,5,5,5]) == 4  # identical elements
assert Solution().maximumElementAfterDecrementingAndRearranging([10,1,2,3,4]) == 5  # mixed large and small

# Stress test
assert Solution().maximumElementAfterDecrementingAndRearranging(list(range(1, 100001))) == 100000  # large array, already sorted

Test	Why
[2,2,1,2,1]	Tests small adjustments and duplicates
[100,1,1000]	Tests large decreases and rearrangement
[1,2,3,4,5]	Already valid array
[1]	Single element
[5,5,5,5]	Identical elements, needs adjustment
[10,1,2,3,4]	Mixed values with one small starting element
range(1, 100001)	Stress test for large n

Edge Cases

One edge case is a single-element array. Here, the algorithm correctly sets the first element to 1, which is also the maximum.

Another edge case is when all elements are identical. After sorting, the first element becomes 1, and each subsequent element increases by 1 until the original value is reached or the sequence is complete, ensuring the adjacency rule.

A third edge case is arrays with very large values far exceeding the array length. Sorting ensures the smallest elements come first. Then greedy adjustment ensures the maximum value is bounded by the length of the array, regardless of initial large numbers, preventing overflow or invalid differences.