Want Help Cracking FAANG?

(Then click this)

 ×
Back to Question Bank

1846. Maximum Element After Decreasing and Rearranging - Leetcode Solution

Code Implementation

class Solution:
    def maximumElementAfterDecrementingAndRearranging(self, arr):
        arr.sort()
        arr[0] = 1
        for i in range(1, len(arr)):
            arr[i] = min(arr[i], arr[i-1]+1)
        return arr[-1]
      
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();
    }
};
      
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];
    }
}
      
var maximumElementAfterDecrementingAndRearranging = function(arr) {
    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];
};

Problem Description

Given an array of positive integers arr, you can perform two types of operations:
  • Decrement any element in arr any number of times, but not below 1.
  • Rearrange the elements in any order.
After performing any sequence of these operations, what is the maximum possible value of any element in arr such that, after rearrangement, the absolute difference between any two consecutive elements is at most 1? In other words, for the rearranged array a, for all i from 1 to n - 1, |a[i] - a[i-1]| <= 1 and a[0] = 1 must hold.

Constraints:
  • Each element can only be used once (no duplicates beyond those in the input).
  • There is always at least one valid solution.
  • All elements are positive integers.

Thought Process

To approach this problem, start by considering the constraints: every element can be reduced (decremented) but not increased, and the order can be rearranged. The critical rule is that the difference between consecutive elements must be at most 1, and the first element must be 1. A brute-force approach would be to try all permutations and decrement operations, but that is computationally infeasible for large arrays. Instead, we look for a systematic way to ensure the constraints are met while maximizing the largest number in the final array. Think of building a "staircase" where each step can only be one higher than the previous one, starting from 1. Since we can decrease elements but not increase them, we want to use the larger numbers to fill the higher steps, but only as high as allowed by the previous step plus one. Sorting the array helps us process from smallest to largest, making it easy to apply this rule.

Solution Approach

The optimal solution uses a greedy method, ensuring we maximize the last element under the constraints. Here's how:
  1. Sort the array: Sorting helps us process elements from smallest to largest, making it easier to build the sequence step by step.
  2. Set the first element to 1: Since the first element must be 1, we explicitly set it.
  3. Iterate through the array: For each subsequent element, set it to the minimum of its current value and one more than the previous value. This ensures the difference is at most 1 and we never increase an element.
  4. Return the last element: After processing, the last element is the maximum possible under the rules.
This approach guarantees that the difference between consecutive elements is at most 1, and the sequence is as "high" as possible given the available numbers.

Example Walkthrough

Example: Suppose arr = [2, 2, 1, 2, 1]
  • Step 1: Sort the array: [1, 1, 2, 2, 2]
  • Step 2: Set the first element to 1: [1, 1, 2, 2, 2]
  • Step 3: Iterate:
    • Index 1: min(1, 1+1) = 1 → [1, 1, 2, 2, 2]
    • Index 2: min(2, 1+1) = 2 → [1, 1, 2, 2, 2]
    • Index 3: min(2, 2+1) = 2 → [1, 1, 2, 2, 2]
    • Index 4: min(2, 2+1) = 2 → [1, 1, 2, 2, 2]
  • Step 4: The maximum element is 2.
The process ensures that the array starts at 1 and each next element is at most one greater than the previous, using the largest available numbers where possible.

Time and Space Complexity

  • Brute-force approach: Trying all permutations and decrement combinations would be factorial time, O(n!), which is not feasible for large arrays.
  • Optimized approach:
    • Time Complexity: Sorting the array takes O(n log n), and the single pass through the array is O(n), so the total is O(n log n).
    • Space Complexity: If allowed to modify the input in place, extra space is O(1) (ignoring sort stack space). If not, O(n) for a copy.

Summary

The key insight is to sort the array and build the sequence from 1 upward, ensuring each step is at most one higher than the last. By always choosing the minimum between the current value and the allowed increment, we maximize the largest possible value in the array while satisfying all constraints. This greedy, linear approach is both elegant and efficient, making it ideal for this problem.