Maximum element after decreasing and rearranging

Array Greedy Sorting

65.8% acceptance

Feb 25, 2026

1134

278

You are given an array of positive integers arr. Perform some operations (possibly none) on arr so that it satisfies these conditions: The value of the first element in arr must be 1. The absolute difference between any 2 adjacent elements must be less than or equal to 1. There are 2 types of operations that you can perform any number of times: Decrease the value of any element of arr to a smaller positive integer. Rearrange the elements of arr to be in any order. Return the maximum possible value of an element in arr after performing the operations to satisfy the conditions.

Solution

Rust

Time O(n log n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn maximum_element_after_decrementing_and_rearranging(mut arr: Vec<i32>) -> i32 {
    arr.sort_unstable();
    arr[0] = 1;
    for i in 1..arr.len() {
      arr[i] = arr[i].min(arr[i - 1] + 1);
    }
    *arr.last().unwrap()
  }
}