1846. Maximum Element After Decreasing and Rearranging Medium

1/**
2 * [1846] Maximum Element After Decreasing and Rearranging
3 *
4 * You are given an array of positive integers arr. Perform some operations (possibly none) on arr so that it satisfies these conditions:
5 * 
6 * 	The value of the first element in arr must be 1.
7 * 	The absolute difference between any 2 adjacent elements must be less than or equal to 1. In other words, abs(arr[i] - arr[i - 1]) <= 1 for each i where 1 <= i < arr.length (0-indexed). abs(x) is the absolute value of x.
8 * 
9 * There are 2 types of operations that you can perform any number of times:
10 * 
11 * 	Decrease the value of any element of arr to a smaller positive integer.
12 * 	Rearrange the elements of arr to be in any order.
13 * 
14 * Return the maximum possible value of an element in arr after performing the operations to satisfy the conditions.
15 *  
16 * Example 1:
17 * 
18 * Input: arr = [2,2,1,2,1]
19 * Output: 2
20 * Explanation: 
21 * We can satisfy the conditions by rearranging arr so it becomes [1,2,2,2,1].
22 * The largest element in arr is 2.
23 * 
24 * Example 2:
25 * 
26 * Input: arr = [100,1,1000]
27 * Output: 3
28 * Explanation: 
29 * One possible way to satisfy the conditions is by doing the following:
30 * 1. Rearrange arr so it becomes [1,100,1000].
31 * 2. Decrease the value of the second element to 2.
32 * 3. Decrease the value of the third element to 3.
33 * Now arr = [1,2,3], which satisfies the conditions.
34 * The largest element in arr is 3.
35 * 
36 * Example 3:
37 * 
38 * Input: arr = [1,2,3,4,5]
39 * Output: 5
40 * Explanation: The array already satisfies the conditions, and the largest element is 5.
41 * 
42 *  
43 * Constraints:
44 * 
45 * 	1 <= arr.length <= 10^5
46 * 	1 <= arr[i] <= 10^9
47 * 
48 */
49pub struct Solution {}
50
51// problem: https://leetcode.com/problems/maximum-element-after-decreasing-and-rearranging/
52// discuss: https://leetcode.com/problems/maximum-element-after-decreasing-and-rearranging/discuss/?currentPage=1&orderBy=most_votes&query=
53
54// submission codes start here
55
56impl Solution {
57    pub fn maximum_element_after_decrementing_and_rearranging(arr: Vec<i32>) -> i32 {
58        0
59    }
60}
61
62// submission codes end
63
64#[cfg(test)]
65mod tests {
66    use super::*;
67
68    #[test]
69    fn test_1846() {
70    }
71}
72