Maximum Element After Decreasing and Rearranging

Medium
1445.

Maximum Element After Decreasing and Rearranging

Maximum Element After Decreasing and Rearranging is a medium coding problem on arrays, sorting and greedy, asked in Amazon and Google interviews.

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^5
  • 1 <= arr[i] <= 10^9
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} arr
 * @return {number}
 */
var maximumElementAfterDecrementingAndRearranging = function(arr) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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^5
  • 1 <= arr[i] <= 10^9

Hints for Maximum Element After Decreasing and Rearranging

  1. Hint 1

    Since elements can only go down, put them in ascending order — a larger value is never wasted early.

  2. Hint 2

    In sorted order, each element can be at most one more than the element before it.

  3. Hint 3

    Walk the sorted array setting arr[i] = min(arr[i], arr[i - 1] + 1) with arr[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

  1. Sort arr ascending.
  2. Set prev = 0. For each value v in order, set prev = min(v, prev + 1).
  3. 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 over min(v, n) gives an O(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 prev

Java

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