Skip to main content
Talentd

Maximum Element After Decreasing and Rearranging - Solution & Explanation

MediumArrayGreedySorting16 min readAsked at: Amazon, Microsoft, Google +1
Practice this problem

Problem Statement

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

Approach Overview

Problem Overview: You can rearrange the array in any order and decrease any element to any smaller positive value. After modification, the array must satisfy two rules: arr[0] = 1 and arr[i] - arr[i-1] ≤ 1. The goal is to maximize the final element arr[n-1]. The challenge is deciding how to reshape values so the sequence grows as much as possible without violating the constraint.

Approach 1: Greedy with Sorting (Time: O(n log n), Space: O(1) or O(log n))

This approach relies on sorting and a greedy adjustment step. First sort the array so smaller values appear earlier. Set the first element to 1. Then iterate from left to right and restrict each value to at most previous + 1. If the current value is larger, decrease it to prev + 1. If it's already smaller, keep it as is because decreasing further would only reduce the final maximum. Sorting guarantees the smallest feasible sequence growth, while the greedy rule ensures the array increases by at most one each step. The final value of the last element becomes the maximum achievable element. This solution is straightforward and works well for most interview scenarios involving sorting and greedy constraints.

Approach 2: Counting Sort-Based Greedy (Time: O(n), Space: O(n))

The values only matter up to n, because the maximum valid sequence length cannot exceed the array size. Instead of sorting, build a frequency array where values greater than n are capped at n. Then simulate constructing the sequence from 1 upward. Track how many numbers are available to extend the sequence. At each step, if at least one unused number exists, increase the current maximum by one. Extra numbers become carry-over that help fill future positions. This effectively simulates the greedy growth of the sequence without explicitly sorting the array. The result is a linear-time solution using counting logic, which is common in optimized array problems.

Recommended for interviews: The greedy sorting approach is the expected solution in most interviews because it is easy to reason about and implement correctly in a few lines. The counting approach demonstrates deeper optimization by removing the O(n log n) sort and replacing it with linear frequency tracking. Showing the sorted greedy first proves you understand the constraint transformation, while the counting variant shows strong algorithmic awareness.

Approach 1: Greedy Approach with Sorting

This approach involves sorting the array first. After sorting, we iterate over the array from the first element onwards, setting each element to be the minimum between its current value and the value of the previous element plus 1. This ensures the conditions are met, i.e., the first element is 1 and the difference between adjacent elements is <= 1.

We first sort the array using qsort. Then, starting from the first index (0), we set it to 1 as the condition requires. For every subsequent element, we ensure that it is either its current value or the previous element + 1, whichever is smaller. This ensures the absolute difference between adjacent elements is at most 1.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1) as we modify the array in place.

Try this approach in the editor →

Approach 2: Counting Sort-Based Approach

This approach leverages the counting sort technique which avoids sorting the entire array directly. Instead, it uses a frequency array to count occurrences of each element. Then, reconstruct the final array by checking counts and adjusting values accordingly to ensure the maximum element is achieved while meeting the constraints.

In C, we use calloc to create a count array which logs the frequency of each element. The counting concludes, and array values are adjusted using the count data structure to maximize the array while meeting the constraints.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), due to the pass over the array to count elements.
Space Complexity: O(n), primarily due to the count array.

Try this approach in the editor →

Approach 3: Sorting + Greedy Algorithm

First, we sort the array and then set the first element of the array to 1.

Next, we start traversing the array from the second element. If the difference between the current element and the previous one is more than 1, we greedily reduce the current element to the previous element plus 1.

Finally, we return the maximum element in the array.

The time complexity is O(n times log n), and the space complexity is O(log n). Where n is the length of the array.

Code

PythonJavaC++GoTypeScriptC#

Python

Java

C++

Go

TypeScript

C#

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Greedy Approach with Sorting

Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1) as we modify the array in place.

Counting Sort-Based Approach

Time Complexity: O(n), due to the pass over the array to count elements.
Space Complexity: O(n), primarily due to the count array.

Sorting + Greedy Algorithm—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Greedy with SortingO(n log n)O(1) or O(log n)General solution. Easy to implement and explain in interviews.
Counting Sort-Based GreedyO(n)O(n)When optimizing away sorting or when input size is large.

Video Solution

Maximum Element After Decreasing and Rearranging - Leetcode 1846 - Python • NeetCodeIO • 8,353 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Maximum Element After Decreasing and Rearranging easy or hard?
The problem is rated Medium because the constraint transformation is not immediately obvious. Once you recognize that the array should grow step-by-step starting from 1, the greedy rule becomes clear. Implementation is simple, but identifying the correct greedy invariant requires practice.
Maximum Element After Decreasing and Rearranging Python/Java solution
Both Python and Java implementations typically follow the same greedy pattern: sort the array, set the first element to 1, and iterate while updating each element to min(current, previous + 1). The final element in the array becomes the answer. The implementation is short and runs in O(n log n) time.
How to solve Maximum Element After Decreasing and Rearranging in O(n)?
Use a counting technique instead of sorting. Count the frequency of each value while capping values greater than n to n. Then iterate from 1 to n while tracking how many numbers are available to extend the sequence. Increase the current maximum whenever possible. This simulates the greedy construction in linear time.
What is the best approach for Maximum Element After Decreasing and Rearranging?
The standard approach sorts the array and then greedily enforces the rule that each element can increase by at most one from the previous value. After sorting, set the first element to 1 and update each element to min(arr[i], arr[i-1] + 1). This greedy rule guarantees the largest possible final value. The time complexity is O(n log n) due to sorting.
Is Maximum Element After Decreasing and Rearranging asked at Google/Amazon/Meta?
Problems combining greedy constraints and array manipulation appear frequently in interviews at companies like Amazon, Google, and Meta. Variants that require rearranging arrays under incremental constraints are common because they test sorting intuition and greedy reasoning.
What data structure is used in Maximum Element After Decreasing and Rearranging?
The primary structure is an array. The greedy solution uses sorting followed by a linear pass. The optimized variant uses a counting array (frequency table) to simulate sorting and construct the valid sequence.
What is the time complexity of Maximum Element After Decreasing and Rearranging?
The common greedy solution runs in O(n log n) time because it sorts the array before applying the constraint adjustments. A more optimized counting-based approach can achieve O(n) time by using a frequency array and simulating the sequence growth. Space complexity ranges from O(1) for in-place sorting to O(n) for the counting method.

Ready to solve this problem?

Practice Maximum Element After Decreasing and Rearranging with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays