All prompts are owned by LeetCode. To view the prompt, click the title link above.
First completed : July 03, 2024
Last updated : July 03, 2024
Related Topics : Array, Greedy, Sorting
Acceptance Rate : 59.25 %
Since we have exactly 3 moves, we only have 4 cases to worry about.
First things first. If we have an array of length 4 or less, we can just set the values to be equal and have a difference of 0.
In most cases however, we will be comparing the 4 max values and 4 min values. By setting any extrema to a value of our choosing, we can set it to the average number, negating it all together. If we have
$s1, s2, s3, s4, l4, l3, l2, l1,$ represent the smallest 4 and largest 4 values in the array, we know our result will be the min of:$min(l4-s1, l3-s2, l2-s3, l1-s4)$ .The simplest approach is to sort and check these 4 values ($O(n\log{n})$).
Alternatively, we can do a single pass of the entire array to find the max 4 and min 4 values in linear time ($O(n)$). Even though in my case I used
sort()to rearrange the values, since it's a single pass of in effect insertion sort on a array of max length 4, it remains linear.In Version 3 I did the 4-part if statements instead of using sort.
- m1509 v1 Daily Sorting.py
- m1509 v2 Daily Single Pass No Sort.py
- m1509 v3.c
- m1509 v3.cpp
- m1509 v3.java
class Solution:
def minDifference(self, nums: List[int]) -> int:
if len(nums) <= 4 :
return 0
nums.sort()
return min(nums[-1] - nums[3],
nums[-2] - nums[2],
nums[-3] - nums[1],
nums[-4] - nums[0])# .sort() for 4 values would be minimal and a constant max
# cost. This just simplified the typing process but could easily
# be changed for better efficiency. It's essentially a single
# iteration of insertion sort.
class Solution:
def minDifference(self, nums: List[int]) -> int:
if len(nums) <= 4 :
return 0
top4 = sorted(nums[:4], reverse=True)
bot4 = sorted(nums[:4])
for num in nums[4:] :
if num > top4[3] :
top4.append(num)
top4.sort(reverse=True)
top4.pop()
if num < bot4[3] :
bot4.append(num)
bot4.sort()
bot4.pop()
return min([top4[i] - bot4[3 - i] for i in range(4)])int cmp(const void* one, const void* two) {
return *((int *) one) - *((int *) two);
}
int minDifference(int* nums, int numsSize) {
if (numsSize <= 4)
return 0;
int top4[4] = {nums[0], nums[1], nums[2], nums[3]};
qsort(top4, 4, sizeof(int), cmp);
int bot4[4] = {top4[3], top4[2], top4[1], top4[0]};
for (int i = 4; i < numsSize; i++) {
if (nums[i] > top4[3]) {
top4[0] = top4[1];
top4[1] = top4[2];
top4[2] = top4[3];
top4[3] = nums[i];
} else if (nums[i] > top4[2]) {
top4[0] = top4[1];
top4[1] = top4[2];
top4[2] = nums[i];
} else if (nums[i] > top4[1]) {
top4[0] = top4[1];
top4[1] = nums[i];
} else if (nums[i] > top4[0]) {
top4[0] = nums[i];
}
if (nums[i] < bot4[3]) {
bot4[0] = bot4[1];
bot4[1] = bot4[2];
bot4[2] = bot4[3];
bot4[3] = nums[i];
} else if (nums[i] < bot4[2]) {
bot4[0] = bot4[1];
bot4[1] = bot4[2];
bot4[2] = nums[i];
} else if (nums[i] < bot4[1]) {
bot4[0] = bot4[1];
bot4[1] = nums[i];
} else if (nums[i] < bot4[0]) {
bot4[0] = nums[i];
}
}
int a = (top4[3] - bot4[0] < top4[2] - bot4[1]) ? top4[3] - bot4[0] : top4[2] - bot4[1];
int b = (top4[1] - bot4[2] < top4[0] - bot4[3]) ? top4[1] - bot4[2] : top4[0] - bot4[3];
return (a < b) ? a : b;
}class Solution {
public:
int minDifference(vector<int>& nums) {
if (nums.size() <= 4)
return 0;
int top4[4] = {nums[0], nums[1], nums[2], nums[3]};
sort(top4, top4 + 4);
int bot4[4] = {top4[3], top4[2], top4[1], top4[0]};
for (int i = 4; i < nums.size(); i++) {
if (nums[i] > top4[3]) {
top4[0] = top4[1];
top4[1] = top4[2];
top4[2] = top4[3];
top4[3] = nums[i];
} else if (nums[i] > top4[2]) {
top4[0] = top4[1];
top4[1] = top4[2];
top4[2] = nums[i];
} else if (nums[i] > top4[1]) {
top4[0] = top4[1];
top4[1] = nums[i];
} else if (nums[i] > top4[0]) {
top4[0] = nums[i];
}
if (nums[i] < bot4[3]) {
bot4[0] = bot4[1];
bot4[1] = bot4[2];
bot4[2] = bot4[3];
bot4[3] = nums[i];
} else if (nums[i] < bot4[2]) {
bot4[0] = bot4[1];
bot4[1] = bot4[2];
bot4[2] = nums[i];
} else if (nums[i] < bot4[1]) {
bot4[0] = bot4[1];
bot4[1] = nums[i];
} else if (nums[i] < bot4[0]) {
bot4[0] = nums[i];
}
}
int a = (top4[3] - bot4[0] < top4[2] - bot4[1]) ? top4[3] - bot4[0] : top4[2] - bot4[1];
int b = (top4[1] - bot4[2] < top4[0] - bot4[3]) ? top4[1] - bot4[2] : top4[0] - bot4[3];
return (a < b) ? a : b;
}
};
class Solution {
public int minDifference(int[] nums) {
if (nums.length <= 4)
return 0;
int[] top4 = {nums[0], nums[1], nums[2], nums[3]};
Arrays.sort(top4); // ascending
int[] bot4 = {top4[3], top4[2], top4[1], top4[0]};
for (int i = 4; i < nums.length; i++) {
if (nums[i] > top4[3]) {
top4[0] = top4[1];
top4[1] = top4[2];
top4[2] = top4[3];
top4[3] = nums[i];
} else if (nums[i] > top4[2]) {
top4[0] = top4[1];
top4[1] = top4[2];
top4[2] = nums[i];
} else if (nums[i] > top4[1]) {
top4[0] = top4[1];
top4[1] = nums[i];
} else if (nums[i] > top4[0]) {
top4[0] = nums[i];
}
if (nums[i] < bot4[3]) {
bot4[0] = bot4[1];
bot4[1] = bot4[2];
bot4[2] = bot4[3];
bot4[3] = nums[i];
} else if (nums[i] < bot4[2]) {
bot4[0] = bot4[1];
bot4[1] = bot4[2];
bot4[2] = nums[i];
} else if (nums[i] < bot4[1]) {
bot4[0] = bot4[1];
bot4[1] = nums[i];
} else if (nums[i] < bot4[0]) {
bot4[0] = nums[i];
}
}
return Integer.min(Integer.min(top4[3] - bot4[0], top4[2] - bot4[1]),
Integer.min(top4[1] - bot4[2], top4[0] - bot4[3]));
}
}