1846. Maximum Element After Decreasing and Rearranging Solution

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

The 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 <= 10⁵
1 <= arr[i] <= 10⁹

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.

Python

def maxElementAfterDecreasingAndRearranging(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]

arr = [100, 1, 1000]
print(maxElementAfterDecreasingAndRearranging(arr))

Java

import java.util.Arrays;

public class Solution {
    public static int maxElementAfterDecreasingAndRearranging(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];
    }

    public static void main(String[] args) {
        int[] arr = {100, 1, 1000};
        System.out.println(maxElementAfterDecreasingAndRearranging(arr));
    }
}

C++

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int maxElementAfterDecreasingAndRearranging(vector<int>& arr) {
    sort(arr.begin(), arr.end());
    arr[0] = 1;
    for (size_t i = 1; i < arr.size(); i++) {
        arr[i] = min(arr[i], arr[i-1] + 1);
    }
    return arr.back();
}

int main() {
    vector<int> arr = {100, 1, 1000};
    cout << maxElementAfterDecreasingAndRearranging(arr);
    return 0;
}

JavaScript

function maxElementAfterDecreasingAndRearranging(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];
}

console.log(maxElementAfterDecreasingAndRearranging([100, 1, 1000]));

#include <stdio.h>
#include <stdlib.h>

// Comparator function for qsort
int cmp(const void* a, const void* b) {
    return (*(int*)a - *(int*)b);
}

int maxElementAfterDecreasingAndRearranging(int* arr, int arrSize) {
    qsort(arr, arrSize, sizeof(int), cmp);
    arr[0] = 1;
    for (int i = 1; i < arrSize; i++) {
        arr[i] = arr[i] < arr[i-1] + 1 ? arr[i] : arr[i-1] + 1;
    }
    return arr[arrSize - 1];
}

int main() {
    int arr[] = {100, 1, 1000};
    int length = sizeof(arr) / sizeof(arr[0]);
    int result = maxElementAfterDecreasingAndRearranging(arr, length);
    printf("%d", result);
    return 0;
}

using System;

class Solution {
    public static int MaxElementAfterDecreasingAndRearranging(int[] arr) {
        Array.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];
    }

    static void Main() {
        int[] arr = {100, 1, 1000};
        Console.WriteLine(MaxElementAfterDecreasingAndRearranging(arr));
    }
}

Python provides a straightforward implementation using the sort method, which organizes the array in non-decreasing order. From there, we iterate and use min to adjust values to fit the requirements.

Complexity

Time Complexity: O(n log n) because the array is sorted initially.
Space Complexity: O(1) since we're adjusting 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.

Python

def maxElementAfterDecreasingAndRearranging(arr):
    n = len(arr)
    count = [0] * (n + 1)
    for num in arr:
        count[min(num, n)] += 1

    max_elem = 0
    for i in range(1, n + 1):
        max_elem += count[i]
        if max_elem < i:
            max_elem = i

    return max_elem

arr = [100, 1, 1000]
print(maxElementAfterDecreasingAndRearranging(arr))

Java

import java.util.Arrays;

public class Solution {
    public static int maxElementAfterDecreasingAndRearranging(int[] arr) {
        int n = arr.length;
        int[] count = new int[n + 1];
        Arrays.fill(count, 0);
        for (int num : arr) {
            if (num <= n) count[num]++;
            else count[n]++;
        }
        int maxElem = 0;
        for (int i = 1; i <= n; i++) {
            maxElem += count[i];
            if (maxElem < i) {
                maxElem = i;
            }
        }
        return maxElem;
    }

    public static void main(String[] args) {
        int[] arr = {100, 1, 1000};
        System.out.println(maxElementAfterDecreasingAndRearranging(arr));
    }
}

C++

#include <iostream>
#include <vector>
using namespace std;

int maxElementAfterDecreasingAndRearranging(vector<int>& arr) {
    int n = arr.size();
    vector<int> count(n + 1, 0);
    for (int num : arr) 
        count[min(num, n)]++;
    int maxElem = 0;
    for (int i = 1; i <= n; i++) {
        maxElem += count[i];
        if (maxElem < i) maxElem = i;
    }
    return maxElem;
}

int main() {
    vector<int> arr = {100, 1, 1000};
    cout << maxElementAfterDecreasingAndRearranging(arr);
    return 0;
}

JavaScript

function maxElementAfterDecreasingAndRearranging(arr) {
    const n = arr.length;
    const count = new Array(n + 1).fill(0);
    for (let num of arr) {
        count[Math.min(num, n)]++;
    }
    let maxElem = 0;
    for (let i = 1; i <= n; i++) {
        maxElem += count[i];
        if (maxElem < i) {
            maxElem = i;
        }
    }
    return maxElem;
}

console.log(maxElementAfterDecreasingAndRearranging([100, 1, 1000]));

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int maxElementAfterDecreasingAndRearranging(int* arr, int arrSize) {
    int* count = (int*)calloc(arrSize + 1, sizeof(int));
    for (int i = 0; i < arrSize; i++) {
        if (arr[i] <= arrSize) 
            count[arr[i]]++;
        else
            count[arrSize]++;
    }
    int maxElem = 0;
    for (int i = 1; i <= arrSize; i++) {
        maxElem = i < maxElem + count[i] ? maxElem + count[i] : i;
        count[i] = maxElem;
    }
    free(count);
    return maxElem;
}

int main() {
    int arr[] = {100, 1, 1000};
    int length = sizeof(arr) / sizeof(arr[0]);
    int result = maxElementAfterDecreasingAndRearranging(arr, length);
    printf("%d", result);
    return 0;
}

using System;

class Solution {
    public static int MaxElementAfterDecreasingAndRearranging(int[] arr) {
        int n = arr.Length;
        int[] count = new int[n + 1];
        foreach (int num in arr) 
            count[Math.Min(num, n)]++;
        
        int maxElem = 0;
        for (int i = 1; i <= n; i++) {
            maxElem += count[i];
            if (maxElem < i) maxElem = i;
        }
        return maxElem;
    }

    static void Main() {
        int[] arr = {100, 1, 1000};
        Console.WriteLine(MaxElementAfterDecreasingAndRearranging(arr));
    }
}

The Python solution utilizes a list of zeros to tally occurrences. By counting the array elements and incrementing the corresponding index in the count list, we construct an array meeting the challenge's demands.

Complexity

Time Complexity: O(n), covering the single scan of the input array.
Space Complexity: O(n), due to the use of the additional 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.

TypeScript

function maximumElementAfterDecrementingAndRearranging(arr: number[]): number {
    arr.sort((a, b) => a - b);
    arr[0] = 1;
    let ans = 1;
    for (let i = 1; i < arr.length; ++i) {
        const d = Math.max(0, arr[i] - arr[i - 1] - 1);
        arr[i] -= d;
        ans = Math.max(ans, arr[i]);
    }
    return ans;
}

func maximumElementAfterDecrementingAndRearranging(arr []int) int {
	sort.Ints(arr)
	ans := 1
	arr[0] = 1
	for i := 1; i < len(arr); i++ {
		d := max(0, arr[i]-arr[i-1]-1)
		arr[i] -= d
		ans = max(ans, arr[i])
	}
	return ans
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Greedy Approach with Sorting	Time Complexity: O(n log n) because the array is sorted initially. Space Complexity: O(1) since we're adjusting in place.
Counting Sort-Based Approach	Time Complexity: O(n), covering the single scan of the input array. Space Complexity: O(n), due to the use of the additional count array.
Sorting + Greedy Algorithm	–

Complexity analysis

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

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.

Maximum Element After Decreasing and Rearranging solution and explanation

The problem

Approach overview

Approach 1: Greedy Approach with Sorting

Approach 2: Counting Sort-Based Approach

Approach 3: Sorting + Greedy Algorithm

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Maximum Element After Decreasing and Rearranging solution and explanation

The problem

Approach overview

Approach 1: Greedy Approach with Sorting

Approach 2: Counting Sort-Based Approach

Approach 3: Sorting + Greedy Algorithm

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems