MediumNo. 1846
Maximum Element After Decreasing and Rearranging — LeetCode 1846 Python Solution
- Pattern
- Greedy
- Topics
- Greedy, Array, Sorting
- Reading time
- 2 min
- Source
- leetcode.com
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.
Example
- 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].
Python solution
class Solution:
def maximumElementAfterDecrementingAndRearranging(self, arr: List[int]) -> int:
arr.sort()
arr[0] = 1
for i in range(1, len(arr)):
d = max(0, arr[i] - arr[i - 1] - 1)
arr[i] -= d
return max(arr)Complexity
- Time
- O(n × log n)
- Space · auxiliary
- O(log n)
Pattern: Greedy
Take the locally best option every time — when you can prove that never costs you later. LeetCode 1846. Maximum Element After Decreasing and Rearranging is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Greedy.
The greedy guide has the Python template for the pattern and the 346 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 1838 | Frequency of the Most Frequent Element | Medium |
| 0179 | Largest Number | Medium |
| 0324 | Wiggle Sort II | Medium |
| 0452 | Minimum Number of Arrows to Burst Balloons | Medium |
| 0455 | Assign Cookies | Easy |
| 0502 | IPO | Hard |
Frequently asked questions
- How hard is LeetCode 1846. Maximum Element After Decreasing and Rearranging?
LeetCode 1846. Maximum Element After Decreasing and Rearranging is rated Medium on LeetCode.
- What is the time complexity of LeetCode 1846. Maximum Element After Decreasing and Rearranging?
The Python solution on this page runs in O(n × log n).
- What is the space complexity of LeetCode 1846. Maximum Element After Decreasing and Rearranging?
The Python solution on this page uses O(log n) auxiliary space.
- What topics does LeetCode 1846. Maximum Element After Decreasing and Rearranging cover?
LeetCode 1846. Maximum Element After Decreasing and Rearranging is tagged Greedy, Array and Sorting on LeetCode.