# Maximum Element After Decreasing and Rearranging
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/maximum-element-after-decreasing-and-rearranging)
Canonical: https://scaleengineer.com/dsa/problems/maximum-element-after-decreasing-and-rearranging
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
---
## 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`

# Approaches
## Greedy Approach with Sorting
The core idea is that to maximize the final element, we should make the array a non-decreasing sequence. By sorting the input array, we can process the elements in increasing order. This allows us to greedily construct the target array by ensuring each element satisfies the condition `arr[i] <= arr[i-1] + 1` while being as large as possible.
**Time:** O(N log N)
The dominant operation is sorting the array, which typically takes O(N log N) time. The subsequent pass through the array takes O(N) time. · **Space:** O(log N) or O(N)
This depends on the implementation of the sorting algorithm. In Java, `Arrays.sort` for primitive types has a space complexity of O(log N) for the recursion stack of quicksort. If a copy of the array is needed, it would be O(N).
**Pros:** The logic is intuitive and relatively easy to implement.; If modifying the input array is allowed, the space complexity is very low (O(log N) for sort recursion stack).
**Cons:** The time complexity is dominated by the sorting step, making it less efficient than a linear-time solution.
### Explanation
This approach leverages the power of rearranging by sorting the array first. Sorting is a key step because it allows us to build the resulting array greedily and optimally.

1.  **Sort the array:** We sort `arr` in non-decreasing order. For a non-decreasing array, the condition `abs(arr[i] - arr[i-1]) <= 1` simplifies to `arr[i] <= arr[i-1] + 1`.

2.  **Set the first element:** The first condition requires `arr[0]` to be `1`. We enforce this by setting `arr[0] = 1`. Since the problem states all elements are positive, the original `arr[0]` (after sorting) is at least 1, so we only ever decrease it if it's larger than 1.

3.  **Greedily adjust subsequent elements:** We iterate from the second element (`i = 1`). For each `arr[i]`, we must ensure it's no more than `arr[i-1] + 1`. If `arr[i]` is already within this bound, we leave it, as we want to keep values high. If `arr[i] > arr[i-1] + 1`, we must decrease it. To maximize the final result, we perform the minimal decrease, setting `arr[i] = arr[i-1] + 1`.

4.  **Return the maximum:** After this process, the array satisfies all conditions, and since it's non-decreasing, the maximum element is the last one, `arr[arr.length - 1]`.

```java
import java.util.Arrays;

class Solution {
    public int maximumElementAfterDecrementingAndRearranging(int[] arr) {
        Arrays.sort(arr);
        arr[0] = 1;
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > arr[i - 1] + 1) {
                arr[i] = arr[i - 1] + 1;
            }
        }
        return arr[arr.length - 1];
    }
}
```
### Algorithm
- Sort the input array `arr` in non-decreasing order.
- Set the first element `arr[0]` to `1` to satisfy the first condition.
- Iterate through the array from the second element (`i = 1` to `n-1`).
- For each element `arr[i]`, if it violates the condition `arr[i] - arr[i-1] <= 1` (i.e., `arr[i] > arr[i-1] + 1`), decrease its value to `arr[i-1] + 1`. This is the minimal change to satisfy the condition while keeping the value as large as possible.
- After the loop, the array is valid, and its maximum element is the last one, `arr[n-1]`. Return this value.

## Linear Time Approach with Counting
This approach improves upon the sorting-based method by avoiding the O(N log N) sort. We observe that the exact values of numbers larger than the array's length `n` don't matter, as the maximum possible result is `n`. We can use a counting array to store the frequency of each number (capping large numbers at `n`). Then, we can iterate through the counts to greedily determine the longest possible sequence `1, 2, 3, ...` which gives us the maximum element.
**Time:** O(N)
The algorithm involves two main passes. The first pass populates the `counts` array, taking O(N) time. The second pass iterates from 1 to `n`, taking O(N) time. The total time complexity is O(N). · **Space:** O(N)
We need an auxiliary array `counts` of size `n + 1` to store the frequencies of the numbers, where `n` is the length of the input array.
**Pros:** Achieves optimal O(N) time complexity.; The logic is a clever way to bypass sorting by focusing on element counts.
**Cons:** Requires extra space proportional to the size of the input array, which could be a concern for very large N if memory is highly constrained.
### Explanation
This method achieves linear time complexity by avoiding a full sort and instead using counting.

1.  **Observation and Capping:** The maximum possible value in the final array cannot exceed its length, `n`. An array like `[1, 2, 3, ..., n]` has a maximum of `n`. Any number in the original array `arr[i] > n` is at least as useful as `n`, but no more useful, because the target value at any index `j` is at most `j+1 <= n`. Therefore, we can treat any number `> n` as if it were `n`.

2.  **Frequency Counting:** We create a `counts` array of size `n + 1`. We iterate through `arr`, and for each number `num`, we increment `counts[min(num, n)]`. This takes O(N) time and O(N) space.

3.  **Greedy Construction Simulation:** We can now determine the maximum element without sorting. Let `ans` be the length of the valid prefix `1, 2, ..., ans` that we can form. Initially, `ans = 0`. We iterate through the possible values `v` from `1` to `n`. At each step `v`, we have `counts[v]` numbers from the original array with value `v`. These numbers, combined with the numbers we've already processed (which have formed a sequence up to `ans`), can be used to extend our sequence. The total number of elements available to form a sequence is `ans + counts[v]`. However, since the new numbers we are adding have a value of `v`, the maximum value in the sequence we can form is capped at `v`. Therefore, the new length of our sequence `ans` becomes `min(v, ans + counts[v])`.

4.  **Final Result:** After iterating `v` from `1` to `n`, the final value of `ans` will be the maximum element possible in the modified array.

```java
class Solution {
    public int maximumElementAfterDecrementingAndRearranging(int[] arr) {
        int n = arr.length;
        int[] counts = new int[n + 1];
        for (int num : arr) {
            counts[Math.min(num, n)]++;
        }
        
        // ans represents the length of the prefix 1, 2, ..., ans we can form.
        int ans = 0;
        for (int v = 1; v <= n; v++) {
            // We have 'ans' elements from values < v, and 'counts[v]' elements with value v.
            // Total elements available are ans + counts[v].
            // These can form a sequence up to length ans + counts[v].
            // However, since the values are capped by v, the max element can't exceed v.
            ans = Math.min(v, ans + counts[v]);
        }
        
        return ans;
    }
}
```
### Algorithm
- Let `n` be the length of the array. Create a frequency array `counts` of size `n + 1`.
- Iterate through the input array `arr`. For each number `num`, increment `counts[min(num, n)]`. This treats any number larger than `n` as `n`.
- Initialize a variable `ans = 0`, which will track the maximum element of the sequence `1, 2, ...` we can form.
- Iterate with a variable `v` from `1` to `n`.
- In each iteration, update `ans` using the formula: `ans = min(v, ans + counts[v])`. This calculates the new length of our constructible sequence by adding the available numbers of value `v`, capped by the value `v` itself.
- After the loop, `ans` holds the maximum possible element value. Return `ans`.

# Solutions
### CSharp

```csharp
public class Solution { public int MaximumElementAfterDecrementingAndRearranging ( int [] arr ) { Array . Sort ( arr ); int n = arr . Length ; arr [ 0 ] = 1 ; for ( int i = 1 ; i < n ; ++ i ) { arr [ i ] = Math . Min ( arr [ i ], arr [ i - 1 ] + 1 ); } return arr [ n - 1 ]; } }
```

### Java

```java
class Solution {
public
  int maximumElementAfterDecrementingAndRearranging(int[] arr) {
    Arrays.sort(arr);
    arr[0] = 1;
    int ans = 1;
    for (int i = 1; i < arr.length; ++i) {
      int d = Math.max(0, arr[i] - arr[i - 1] - 1);
      arr[i] -= d;
      ans = Math.max(ans, arr[i]);
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int maximumElementAfterDecrementingAndRearranging(vector<int> &arr) {
    sort(arr.begin(), arr.end());
    arr[0] = 1;
    int ans = 1;
    for (int i = 1; i < arr.size(); ++i) {
      int d = max(0, arr[i] - arr[i - 1] - 1);
      arr[i] -= d;
      ans = max(ans, arr[i]);
    }
    return ans;
  }
};

```

### Python

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

```