Maximum Element After Decreasing and Rearranging — Solution
Maximum Element After Decreasing and Rearranging solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Maximum Element After Decreasing and Rearranging is a medium coding problem on arrays, sorting and greedy, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Arrays, Sorting, Greedy
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given an array arr of positive integers. You may apply these operations any number of times:
- Decrease any element to a smaller positive integer.
- Rearrange the elements in any order.
Afterwards the array must satisfy: the first element is 1, and every two adjacent elements differ by at most 1 (abs(arr[i] - arr[i - 1]) <= 1).
Return the largest possible value of the maximum element of the resulting array.
Example 1
Input: arr = [7,3,3,1]
Output: 4
Explanation: Rearrange to [1,3,3,7] and decrease to [1,2,3,4].
Example 2
Input: arr = [2,2,1,2,1]
Output: 2
Explanation: [1,2,2,2,1] already works; nothing can exceed 2.
Example 3
Input: arr = [100,1,1000]
Output: 3
Constraints
1 <= arr.length <= 10^51 <= arr[i] <= 10^9
Hints for Maximum Element After Decreasing and Rearranging
Hint 1
Since elements can only go down, put them in ascending order — a larger value is never wasted early.
Hint 2
In sorted order, each element can be at most one more than the element before it.
Hint 3
Walk the sorted array setting
arr[i] = min(arr[i], arr[i - 1] + 1)witharr[0] = 1; the last value is the answer.
How to solve Maximum Element After Decreasing and Rearranging
Sort ascending and greedily make each element as large as the rules allow: 1 for the first, then at most one more than its predecessor and never more than its own value.
Approach
- Sort
arrascending. - Set
prev = 0. For each valuevin order, setprev = min(v, prev + 1). - Return
prev.
Why it works
In any valid final array the maximum is reached by a non-decreasing staircase from 1, so we may as well arrange the values ascending — swapping a larger value into an earlier slot never increases what later slots can reach. Along the sorted order, each position is capped both by its own value (we can only decrease) and by the previous position plus one; taking the larger of the allowed values at every step keeps every later cap as high as possible.
Complexity
- Time —
O(n log n) - Space —
O(1) beyond the sort
Pitfalls
- The first element must become exactly 1, which
min(v, 0 + 1)handles since every value is at least 1. - The answer never exceeds
n, so a counting sort overmin(v, n)gives anO(n)variant. - Duplicates are fine — two equal values may stay equal.
Reference solution
Python
from typing import List
def maximumElementAfterDecrementingAndRearranging(arr: List[int]) -> int:
prev = 0
for v in sorted(arr):
prev = min(v, prev + 1)
return prevJava
public static int maximumElementAfterDecrementingAndRearranging(int[] arr) {
int[] a = arr.clone();
Arrays.sort(a);
int prev = 0;
for (int v : a) prev = Math.min(v, prev + 1);
return prev;
}C++
int maximumElementAfterDecrementingAndRearranging(vector<int>& arr) {
vector<int> a = arr;
sort(a.begin(), a.end());
int prev = 0;
for (int v : a) prev = min(v, prev + 1);
return prev;
}JavaScript
var maximumElementAfterDecrementingAndRearranging = function(arr) {
var a = arr.slice().sort(function(x, y) { return x - y; });
var prev = 0;
for (var i = 0; i < a.length; i++) prev = Math.min(a[i], prev + 1);
return prev;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Sorting Algorithms