Minimize the Maximum Difference of Pairs — LeetCode 2616 Python Solution
MediumGreedyArrayBinary SearchDynamic ProgrammingSorting
- Problem
- #2616
- Pattern
- Monotonic Stack
- Reading time
- 3 min
- Source
- leetcode.com
The problem
You are given a 0-indexed integer array nums and an integer p. Find p pairs of indices of nums such that the maximum difference amongst all the pairs is minimized.
Example
- Input
- nums = [10,1,2,7,1,3], p = 2
- Output
- 1
- Explanation
- The first pair is formed from the indices 1 and 4, and the second pair is formed from the indices 2 and 5.
Python solution
Python
class Solution:
def minimizeMax(self, nums: List[int], p: int) -> int:
def check(diff: int) -> bool:
cnt = i = 0
while i < len(nums) - 1:
if nums[i + 1] - nums[i] <= diff:
cnt += 1
i += 2
else:
i += 1
return cnt >= p
nums.sort()
return bisect_left(range(nums[-1] - nums[0] + 1), True, key=check)Complexity
| Measure | Complexity |
|---|---|
| Time | O(n \times (\log n + \log m)), where n is the length of \textit{nums} and m is the difference between the maximum and minimum values in \textit{nums} |
| Space | O(1) auxiliary |
Pattern: Monotonic Stack
Answer "what is the next greater element" for every position in one pass. LeetCode 2616. Minimize the Maximum Difference of Pairs is filed here because the reference solution below belongs to the algorithm family this hub collects, even though its LeetCode tags point elsewhere.
The monotonic stack guide has the Python template for the pattern and the 225 LeetCode problems that use it.
Related problems
Frequently asked questions
- How hard is LeetCode 2616. Minimize the Maximum Difference of Pairs?
- LeetCode 2616. Minimize the Maximum Difference of Pairs is rated Medium on LeetCode.
- What is the time complexity of LeetCode 2616. Minimize the Maximum Difference of Pairs?
- The Python solution on this page runs in O(n \times (\log n + \log m)), where n is the length of \textit{nums} and m is the difference between the maximum and minimum values in \textit{nums}.
- What is the space complexity of LeetCode 2616. Minimize the Maximum Difference of Pairs?
- The Python solution on this page uses O(1) auxiliary space.
- What topics does LeetCode 2616. Minimize the Maximum Difference of Pairs cover?
- LeetCode 2616. Minimize the Maximum Difference of Pairs is tagged Greedy, Array, Binary Search, Dynamic Programming and Sorting on LeetCode.