first, since we can change two elements of nums, and we are trying to minimise both the high and the low score,
intuitively it makes sense that we are trying to change either the maximum or minimum values to be equal to one of the values left in the array.
that will always set our low score to be equal to 0, meaning we are now trying to optimise for the lowest high score.
this leaves us with 3 possible cases for how we can form the lowest high score, by using the difference between:
- the highest value and the third lowest value, by changing the lowest and the second lowest values
- the second highest value and the second lowest value, by changing the highest and the lowest values
- the third highest value and the lowest value, by changing the highest and the second highest values
therefore, the solution can be found by iterating through the array to find the three lowest and three highest values, then taking the smallest of the three differences above.
code link to code
class Solution {
public:
int minimizeSum(vector<int>& nums) {
int mn1{INT32_MAX}, mn2{INT32_MAX}, mn3{INT32_MAX};
int mx1{0}, mx2{0}, mx3{0};
for (int num : nums) {
if (mn1 > num) {
mn3 = mn2;
mn2 = mn1;
mn1 = num;
} else if (mn2 > num) {
mn3 = mn2;
mn2 = num;
} else if (mn3 > num) {
mn3 = num;
}
if (mx1 < num) {
mx3 = mx2;
mx2 = mx1;
mx1 = num;
} else if (mx2 < num) {
mx3 = mx2;
mx2 = num;
} else if (mx3 < num) {
mx3 = num;
}
}
return min({mx1 - mn3, mx2 - mn2, mx3 - mn1});
}
};complexity link to complexity
- Time:
O(n)- Space:
O(1)
time taken link to time taken
- 3 minutes and 40 seconds