Skip to content

1846. Maximum Element After Decreasing and Rearranging 👍

  • Time: $O(n\log n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution {
 public:
  int maximumElementAfterDecrementingAndRearranging(vector<int>& arr) {
    sort(begin(arr), end(arr));
    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
11
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
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]