1509. Minimum Difference Between Largest and Smallest Value in Three Moves
https://leetcode.com/problems/minimum-difference-between-largest-and-smallest-value-in-three-moves
Description
Given an array nums
, you are allowed to choose one element of nums
and change it by any value in one move.
Return the minimum difference between the largest and smallest value of nums
after perfoming at most 3 moves.
Example 1:
**Input:** nums = [5,3,2,4]
**Output:** 0
**Explanation:** Change the array [5,3,2,4] to [**2**,**2**,2,**2**].
The difference between the maximum and minimum is 2-2 = 0.
Example 2:
**Input:** nums = [1,5,0,10,14]
**Output:** 1
**Explanation:** Change the array [1,5,0,10,14] to [1,**1**,0,**1**,**1**].
The difference between the maximum and minimum is 1-0 = 1.
Example 3:
**Input:** nums = [6,6,0,1,1,4,6]
**Output:** 2
Example 4:
**Input:** nums = [1,5,6,14,15]
**Output:** 1
Constraints:
1 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9
ac1: PriorityQueue
The idea is we have 4 options: in a sorted array, remove 1) 0 min, 3 max; 2) 1 min, 2 max; 3) 2 min, 1 max; 4) 3 min, 0 max. Get 4 min + 4 max via 2 PriorityQueue.
class Solution {
public int minDifference(int[] nums) {
if (nums == null || nums.length <= 4) {
return 0;
}
int[] arr = getMinMaxArray(nums);
int min = Integer.MAX_VALUE;
for (int i = 0; i < 4; i++) {
min = Math.min(min, arr[4+i] - arr[i]);
}
return min;
}
private int[] getMinMaxArray(int[] nums) {
PriorityQueue<Integer> min = new PriorityQueue<>();
PriorityQueue<Integer> max = new PriorityQueue<>(Collections.reverseOrder());
for (int n : nums) {
min.offer(n);
if (min.size() > 4) min.poll();
max.offer(n);
if (max.size() > 4) max.poll();
}
return queueToArray(min, max);
}
private int[] queueToArray(PriorityQueue<Integer> min, PriorityQueue<Integer> max) {
int[] arr = new int[8];
int i = 3;
while (!max.isEmpty()) {
arr[i--] = max.poll();
}
i = 4;
while (!min.isEmpty()) {
arr[i++] = min.poll();
}
return arr;
}
}
// O(N) time, O(1) space.
ac2: Sorting
class Solution {
public int minDifference(int[] nums) {
if (nums == null || nums.length <= 4) {
return 0;
}
Arrays.sort(nums);
int min = Integer.MAX_VALUE;
for (int i = 0; i < 4; i++) {
min = Math.min(min, nums[nums.length-4+i] - nums[i]);
}
return min;
}
}
// O(NlogN) time, O(1) space.
Last updated
Was this helpful?