⚡Flashcard Drill➔
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

  1. Rearranging is free, so the only useful order is ascending: sorting lets the largest values sit at the end where they can survive.
  2. The first element is forced to 1, so the best achievable value at position i is bounded by 1 + i.
  3. Sweep left to right applying arr[i] = min(arr[i], arr[i-1] + 1) after forcing arr[0] = 1.
  4. 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.
🎯 Drill This Card Now➔

🧩 Related Greedy Problems