Maximum Element After Decreasing and Rearranging - Video Solutions
Maximum Element After Decreasing and Rearranging - Leetcode 1846 - Python
Maximum Element After Decreasing and Rearranging - Video Solution
Watch 10 video solutions for Maximum Element After Decreasing and Rearranging, a medium level problem involving Array, Greedy, Sorting. This walkthrough by NeetCodeIO has 8,353 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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
arrmust be1. - 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]) <= 1for eachiwhere1 <= i < arr.length(0-indexed).abs(x)is the absolute value ofx.
There are 2 types of operations that you can perform any number of times:
- Decrease the value of any element of
arrto a smaller positive integer. - Rearrange the elements of
arrto 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 rearrangingarrso it becomes[1,2,2,2,1]. The largest element inarris 2.
Example 2:
Input: arr = [100,1,1000] Output: 3 Explanation: One possible way to satisfy the conditions is by doing the following: 1. Rearrangearrso 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. Nowarr = [1,2,3], whichsatisfies the conditions. The largest element inarr 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 <= 1051 <= 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.
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. |