Minimum Difference Between Largest And Smallest Value In Three Moves - Leetcode Solution

Problem statement: You are given an array nums with n integers, and you can perform the following operation any number of times:

• Choose any index i from 0 to n-1 and change the value of nums[i] to any integer.

Return the minimum difference between the largest and smallest value of nums after performing at most three operations.

Solution approach:

• Sort the given array.
• For the given array with n integers, there can be at most four possible scenarios to get the minimum difference between largest and smallest value:
  • Change the first three elements to the last element.
  • Change the first two elements to the last two elements.
  • Change the first element to the last three elements.
  • Do not change any element.
• For the first scenario, calculate the difference between the new largest and smallest value. Compare it with the difference so far and update the minimum difference accordingly.
• Similarly, calculate the differences for the rest of the scenarios and update the minimum difference.
• Return the minimum difference as the final answer.

Code:

class Solution {
public:
    int minDifference(vector<int>& nums) {
        int n = nums.size();
        if(n<=3) return 0; //already sorted, hence the difference is 0
        sort(nums.begin(), nums.end());
        return min({nums[n-1]-nums[3], nums[n-2]-nums[2], nums[n-3]-nums[1], nums[n-4]-nums[0]});
    }
};

Time complexity: O(nlogn) (sorting the array takes O(nlogn) time)

Space complexity: O(1) (no extra space used)

Example:

Input: nums = [5,3,2,4]
Output: 0
Explanation:
After performing three operations, the array becomes [2,2,2,2]. The difference between the largest and smallest value is 0.

Optimization: Since there are only four scenarios possible, we can use variables to directly calculate the maximum and minimum values without sorting the array. This will improve the time complexity to O(n).

Code:

class Solution {
public:
    int minDifference(vector<int>& nums) {
        int n = nums.size();
        if(n<=4) return 0; //can change all elements to any value
        int a = INT_MAX, b = INT_MAX, c = INT_MAX, d = INT_MAX;
        int w = INT_MIN, x = INT_MIN, y = INT_MIN, z = INT_MIN;
        for(auto i: nums){
            if(i<=a){ //new smallest
                d = c;
                c = b;
                b = a;
                a = i;
            }
            else if(i<=b){ //new second smallest
                d = c;
                c = b;
                b = i;
            }
            else if(i<=c){ //new third smallest
                d = c;
                c = i;
            }
            else if(i<=d){ //new fourth smallest
                d = i;
            }
            if(i>=w){ //new largest
                z = y;
                y = x;
                x = w;
                w = i;
            }
            else if(i>=x){ //new second largest
                z = y;
                y = x;
                x = i;
            }
            else if(i>=y){ //new third largest
                z = y;
                y = i;
            }
            else if(i>=z){ //new fourth largest
                z = i;
            }
        }
        return min({w-a, x-b, y-c, z-d});
    }
};

Time complexity: O(n)

Space complexity: O(1) (no extra space used)

1