---
tags: leetcode
---

# [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/)
___
# My Solution
## The Key Idea for Solving This Coding Question
sorting + sliding window
## C++ Code

class Solution {
public:
    
    int minDifference(vector<int>& nums) {
        
        if (nums.size() < 5) {
            // If the number of elements is less than or equal to four, 
            // we can always adjust the values and let the minimum difference
            // to be zero.
            return 0;
        }
        
        // nums.size() >= 5;
        
        // Sort nums in ascending order.
        sort(begin(nums), end(nums));

        // Use the idea of sliding window to find the minimum defference
        // after three moves. Because nums is sorted, we can treat nums 
        // as circular array and choose three consecutive elements to 
        // find the answer. After we choose three consecutive elements as 
        // our window, assume the three consecutive elements are reset to 
        // the maximum value outside the window.
        int lastIdx = nums.size() - 1;
        
        // Now, the first three elements are our window.
        // The maximum value outside the window is the last element. Change
        // the values of the first three elements to the value of nums[lastIdx].
        int minDiff = nums[lastIdx] - nums[3];  
        
        // Treat nums as a circular array and choose nums[0], nums[1] and 
        // nums[lastIdx] to be our window.
        // The maximum value outside the window is nums[lastIdx - 1].
        // Change the values of nums[0], nums[1] and nums[lastIdx] to the
        // value of nums[lastIdx - 1].
        minDiff = min(minDiff, nums[lastIdx - 1] - nums[2]);
        
        // Based upon the idea described above, choose nums[0], 
        // nums[lastIdx] and nums[lastIdx - 1] to be our window.
        // Change the values of nums[0], nums[lastIdx] and 
        // nums[lastIdx - 1] to the value of num[lastIdx - 2].
        minDiff = min(minDiff, nums[lastIdx - 2] - nums[1]);
        
        // Based upon the idea described above, choose the last three
        // elements to be our window.
        // Change the values of the last three elements to the value 
        // of nums[last - 3].
        minDiff = min(minDiff, nums[lastIdx - 3] - nums[0]);
        
        // Since nums has been sorted, we don't have to iterate through 
        // the whole array.
        // After the silding window covers the first three and last three
        // elements, we can find the minimum difference.
        
        return minDiff;
    }
};

## Time Complexity
## Space Complexity
# Miscellaneous
<!--
# Test Cases

[5,3,2,4]

[1,5,0,10,14]

[3,100,20]

[6,6,0,1,1,4,6]

[1,5,6,14,15]

[1,5,0,10,14]

* Runtime Error:

[1,3]

* Wrong Answer:

[82,81,95,75,20]

* Wrong Answer:

[5948,61227,91810,80992,85935,26866,70043,88210,10182,16465,56751,12393,44729,85241,41385,81154,9063,50508,63955,56598,65134,21576,61467,51848,3040,59751,87114,16058,3140,48368,45513,76202,73911,11972,49341,13643,42300,38656,31043,17335,23081,42407,41167,23600,19257,13274,48446,85905,67090,55680,65455,25794,37980,62248,82653,72050,31236,547,75515]

-->