1846. Maximum Element After Decreasing and Rearranging #

Problem #

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. 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.

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.

Example 1:

Input: arr = [2,2,1,2,1]
Output: 2
Explanation:
We can satisfy the conditions by rearrangingarr so it becomes[1,2,2,2,1].
The largest element inarr is 2.

Example 2:

Input: arr = [100,1,1000]
Output: 3
Explanation:
One possible way to satisfy the conditions is by doing the following:
1. Rearrangearr so 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 <= 10^5
• 1 <= arr[i] <= 10^9

Problem Summary #

You are given a positive integer array arr . Perform some operations on arr (possibly none) so that the array satisfies the following conditions:

• The first element in arr must be 1 .
• The absolute difference between any two adjacent elements must be less than or equal to 1 . That is, for any 1 <= i < arr.length (with array indices starting from 0), abs(arr[i] - arr[i - 1]) <= 1 must hold. abs(x) is the absolute value of x .

You can perform the following 2 types of operations any number of times:

• Decrease the value of any element in arr so that it becomes a smaller positive integer .
• Rearrange the elements in arr ; you may rearrange them in any order.

Return the possible maximum value in arr after performing the above operations while satisfying the conditions described above.

Solution Approach #

• The first element of the positive integer array arr must be 1, and the absolute difference between every pair of adjacent elements must be at most 1, so the maximum value in arr is definitely no greater than n. Use a greedy strategy: first count the occurrences of all elements, and add the occurrences of elements greater than n to n. Then scan from 1 to n. When encountering a “gap” (an element with occurrence count 0), move over the nearest element with occurrence count greater than 1 to fill the “gap”. The maximum value required by the problem appears at the rightmost end of the array that remains continuous from left to right after “filling the gaps”.

Code #

package leetcode

func maximumElementAfterDecrementingAndRearranging(arr []int) int {
	n := len(arr)
	count := make([]int, n+1)
	for _, v := range arr {
		count[min(v, n)]++
	}
	miss := 0
	for _, c := range count[1:] {
		if c == 0 {
			miss++
		} else {
			miss -= min(c-1, miss)
		}
	}
	return n - miss
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}