Description
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
arrmust be1. - 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]) <= 1for eachiwhere1 <= i < arr.length(0-indexed).abs(x)is the absolute value ofx.
There are 2 types of operations that you can perform any number of times:
- Decrease the value of any element of
arrto a smaller positive integer. - Rearrange the elements of
arrto be in any order.
Return the maximum possible value of an element in arr after performing the operations to satisfy the conditions.
Example 1:
Input: arr = [2,2,1,2,1] Output: 2 Explanation: We can satisfy the conditions by rearrangingarrso it becomes[1,2,2,2,1]. The largest element inarris 2.
Example 2:
Input: arr = [100,1,1000] Output: 3 Explanation: One possible way to satisfy the conditions is by doing the following: 1. Rearrangearrso it becomes[1,100,1000]. 2. Decrease the value of the second element to 2. 3. Decrease the value of the third element to 3. Nowarr = [1,2,3], whichsatisfies the conditions. The largest element inarr is 3.
Example 3:
Input: arr = [1,2,3,4,5] Output: 5 Explanation: The array already satisfies the conditions, and the largest element is 5.
Constraints:
1 <= arr.length <= 1051 <= arr[i] <= 109
Solutions
Solution using linear time. Although worse than before, it would be much better with more extensive tests.
Language: javascript(2026-06-28 09:36)DONE
CPU Performance11.11%
Memory Performance11.11%
/**
* @param {number[]} arr
* @return {number}
*/
var maximumElementAfterDecrementingAndRearranging = function(arr) {
const n = arr.length;
const dp = new Array(n + 1).fill(0);
for (const num of arr) {
dp[Math.min(num, n)]++;
}
let res = n;
let cur = 0;
for (let i = n; i >= 1; i--) {
if (dp[i] > 0) {
cur += dp[i] - 1;
continue;
}
if (cur > 0) {
cur--;
} else {
res--;
}
}
return res;
};