Maximum Element After Decreasing and Rearranging (LeetCode)

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 rearranging arr so it becomes [1,2,2,2,1]. The largest element in arr 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. Rearrange arr 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. Now arr = [1,2,3], which satisfies the conditions. The largest element in arr 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 <= 105
• 1 <= arr[i] <= 109

Solution

public int MaximumElementAfterDecrementingAndRearranging(int[] arr) {
        Array.Sort(arr);
        var output = new int[arr.Length];
        // find the first element i.e. 1
        var max = 1;
        for (int i = 0; i < arr.Length; i++) {
            if (i == 0) {
                output[i] = 1;
            } else {
                // Check if next item satisfies the difference condition (abs(arr[i] - arr[i - 1]) <= 1)
                // if yes then save it. Else decrease the next item
                if (arr[i] - output[i - 1] <= 1) {
                    output[i] = arr[i];
                    max = arr[i];
                } else {
                    // decrease to next value
                    output[i] = output[i-1] + 1;
                    max = output[i-1] + 1;
                }
            }
        }
        return max;
    }