Maximum Element After Decreasing And Rearranging - Leetcode Solution

Problem Description:

Given an array of positive integers arr, you should make a sequence of operations where you firstly make all elements in the array equal by decreasing the largest element in each operation according to its value, and then rearrangement the array in any order you want. Return the maximum possible element value after performing the operations.

Solution:

We can solve this problem by following a simple algorithm. First, we sort the array in ascending order. Then, we check if the first element of the sorted array is greater than 1. If it is, we decrease it to 1, since there is no point in decreasing an element to a number less than one. We continue decreasing elements in the array until we reach an element that is one less than the previous element.

After this, we can simply rearrange the array in any order we want, since all elements are now equal. The maximum element in this case would be the maximum value in the original array before sorting it.

Code:

Here is the python code for the solution:

class Solution:
    def maximumElementAfterDecrementingAndRearranging(self, arr: List[int]) -> int:
        arr.sort()
        n = len(arr)
        arr[0] = 1
        
        for i in range(1, n):
            if arr[i] - arr[i-1] > 1:
                arr[i] = arr[i-1] + 1
                
        return max(arr)

Time Complexity:

The time complexity of this solution is O(nlogn) due to the sorting of the array. However, the overall time complexity is dominated by the sorting algorithm, which is O(nlogn), so the time complexity of this solution is O(nlogn).

Space Complexity:

The space complexity of this solution is O(1) as we are not using any extra data structure in the algorithm.

1