MediumNo. 1509
Minimum Difference Between Largest and Smallest Value in Three Moves — LeetCode 1509 Python Solution
- Pattern
- Greedy
- Topics
- Greedy, Array, Sorting
- Reading time
- 2 min
- Source
- leetcode.com
The problem
You are given an integer array nums. In one move, you can choose one element of nums and change it to any value.
Example
- Input
- nums = [5,3,2,4]
- Output
- 0
- Explanation
- We can make at most 3 moves.
Python solution
class Solution:
def minDifference(self, nums: List[int]) -> int:
n = len(nums)
if n < 5:
return 0
nums.sort()
ans = inf
for l in range(4):
r = 3 - l
ans = min(ans, nums[n - 1 - r] - nums[l])
return ansComplexity
- Time
- O(n log n)
- Space · auxiliary
- O(1) to O(n)
Pattern: Greedy
Take the locally best option every time — when you can prove that never costs you later. LeetCode 1509. Minimum Difference Between Largest and Smallest Value in Three Moves 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 |
|---|---|---|
| 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 |
| 0561 | Array Partition | Easy |
Frequently asked questions
- How hard is LeetCode 1509. Minimum Difference Between Largest and Smallest Value in Three Moves?
LeetCode 1509. Minimum Difference Between Largest and Smallest Value in Three Moves is rated Medium on LeetCode.
- What topics does LeetCode 1509. Minimum Difference Between Largest and Smallest Value in Three Moves cover?
LeetCode 1509. Minimum Difference Between Largest and Smallest Value in Three Moves is tagged Greedy, Array and Sorting on LeetCode.