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.

Examples

Example 1:

1
2
3
4
5
6
7

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:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

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:

1
2
3
4
5

Input:
arr = [1,2,3,4,5]
Output:
 5
Explanation: The array already satisfies the conditions, and the largest element is 5.

Solution

Method 1 – Greedy with Sorting

Intuition

The main idea is to sort the array and then greedily assign the smallest possible value to each position, starting from 1. This ensures the first element is 1 and the difference between adjacent elements is at most 1, maximizing the largest possible value in the array.

Approach

  1. Sort the array in non-decreasing order.
  2. Set the first element to 1 (since it must be 1).
  3. For each subsequent element, set it to the minimum of its current value and the previous element plus 1.
  4. The answer is the last element in the modified array.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
public:
    int maximumElementAfterDecrementingAndRearranging(vector<int>& arr) {
        sort(arr.begin(), arr.end());
        arr[0] = 1;
        for (int i = 1; i < arr.size(); ++i) {
            arr[i] = min(arr[i], arr[i-1] + 1);
        }
        return arr.back();
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

func maximumElementAfterDecrementingAndRearranging(arr []int) int {
    sort.Ints(arr)
    arr[0] = 1
    for i := 1; i < len(arr); i++ {
        if arr[i] > arr[i-1]+1 {
            arr[i] = arr[i-1] + 1
        }
    }
    return arr[len(arr)-1]
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
    public int maximumElementAfterDecrementingAndRearranging(int[] arr) {
        Arrays.sort(arr);
        arr[0] = 1;
        for (int i = 1; i < arr.length; i++) {
            arr[i] = Math.min(arr[i], arr[i-1] + 1);
        }
        return arr[arr.length - 1];
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
    fun maximumElementAfterDecrementingAndRearranging(arr: IntArray): Int {
        arr.sort()
        arr[0] = 1
        for (i in 1 until arr.size) {
            arr[i] = minOf(arr[i], arr[i-1] + 1)
        }
        return arr.last()
    }
}
1
2
3
4
5
6
7

class Solution:
    def maximumElementAfterDecrementingAndRearranging(self, arr: list[int]) -> int:
        arr.sort()
        arr[0] = 1
        for i in range(1, len(arr)):
            arr[i] = min(arr[i], arr[i-1] + 1)
        return arr[-1]
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

impl Solution {
    pub fn maximum_element_after_decrementing_and_rearranging(mut arr: Vec<i32>) -> i32 {
        arr.sort();
        arr[0] = 1;
        for i in 1..arr.len() {
            arr[i] = arr[i].min(arr[i-1] + 1);
        }
        *arr.last().unwrap()
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
    maximumElementAfterDecrementingAndRearranging(arr: number[]): number {
        arr.sort((a, b) => a - b);
        arr[0] = 1;
        for (let i = 1; i < arr.length; i++) {
            arr[i] = Math.min(arr[i], arr[i-1] + 1);
        }
        return arr[arr.length - 1];
    }
}

Complexity

  • ⏰ Time complexity: O(n log n), due to sorting the array.
  • 🧺 Space complexity: O(1), if sorting in-place, otherwise O(n) if not in-place.