NeetCode #807LC-1846MediumGreedy
← Back to All Problems#807 · #1846 · Maximum Element After Decreasing and Rearranging(减小和重新排列数组后的最大元素)
📌 Problem Statement & Constraints
You are given an array of positive integers
arr. You may rearrange the elements and decrease any element (but never increase one). The final array must satisfy two rules: its first element is exactly 1, and the absolute difference between every pair of adjacent elements is at most 1. Return the maximum possible value of the last element. Constraints: 1 <= arr.length <= 10^5, 1 <= arr[i] <= 10^9.💡 Core Algorithmic Approaches
- Rearranging is free, so the only useful order is ascending: sorting lets the largest values sit at the end where they can survive.
- The first element is forced to 1, so the best achievable value at position
iis bounded by1 + i. - Sweep left to right applying
arr[i] = min(arr[i], arr[i-1] + 1)after forcingarr[0] = 1. - The clamp is optimal because the constraint only ever limits an element from above; never lowering an element can only help the suffix, so greedily taking the maximum legal value is safe.
💻 Benchmark Python3 Implementation
class Solution:
def maximumElementAfterDecrementingAndRearranging(self, arr: List[int]) -> int:
arr.sort()
arr[0] = 1 # the first element must be exactly 1
for i in range(1, len(arr)):
arr[i] = min(arr[i], arr[i - 1] + 1) # clamp to the step-1 bound
return arr[-1]⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n log n): the sort dominates; the clamp pass is a single O(n) scan.
💾 Space Complexity
O(1) beyond the input (Python's sort uses O(n) auxiliary memory in the worst case).
⚠️ Interview Pitfalls & Follow-ups
- Clamping against the original
arr[i-1]: the bound must propagate, so the previous element has to be overwritten in place before it is read. - Trying to raise values: only decreases are allowed, so an element can never exceed its original value.
- Forgetting
arr[0] = 1: even if the smallest value is 5 the first element must become exactly 1, which then caps everything after it. - Guessing the answer as
min(arr[-1], n): this ignores that the sorted prefix may be sparse;[1, 1, 100]yields 3 while[1, 1, 1, 100]yields 4, and only the running clamp captures that.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.