✅💯🔥Explanations No One Will Give You🎓🧠2 Detailed Approaches🎯🔥Extremely Simple And Effective🔥
\n        \n            \n                Nothing is impossible. The word itself says \'I\'m possible!\'"\n                    \n        \n        \n           
<blockquote>\n        <p>\n            <b>\n                Nothing is impossible. The word itself says \'I\'m possible!\'"\n            </b>        \n        </p>\n        <p>\n            --- Audrey Hepburn ---\n        </p>\n</blockquote>\n\n# \uD83D\uDC51Problem Explanation and Understanding:\n\n## \uD83C\uDFAF Problem Description\nYou are given a list of integers ```nums``` and three moves. On each move you can choose any number in list and turn it into any nubmer you want. You want to return the minimum difference between the maximum and the minimum elements in ```nums``` after perfoming up to 3 moves.\n\n## \uD83D\uDCE5\u2935\uFE0F Input:\n- Integer array ```nums```\n\n## \uD83D\uDCE4\u2934\uFE0F Output:\nThe minimum possible difference after after perfomin up to 3 moves.\n\n---\n\n# 1\uFE0F\u20E3\u2728 Approach 1: Greedy + Sorting\n\n# \uD83E\uDD14 Intuition\nIn fact, both approaches are pretty simillar, so once you understand this approach the second will be trivial\n- Okay, let\'s think, if we have <= 4 elements in array, then we always can make all elements equal and make the minimum possible difference 0 (we can\'t achieve any lower difference because difference between something bigger or equal to something else is always >= 0)\n- Do we interested in every element in ```nums```? Obviously not, we want to keep difference between maximum and minimum as small as possible, so on every step we want either to decrease maximum or increase minimum so ```maximum - minimum``` will become smaller. \n- So, considering that we have only 3 moves, we can either move maximum three times to left or minimum three times to right. We always want to perform exactly 3 moves because doing lesser doesn\'t have sense because if we can try to achieve smaller difference why we wouldn\'t? \n- To make it easier to find the "next minimum/maximum" element of the list, we will sort the list and check all possible options for moving these values \u200B\u200Bto achieve the minimum difference.\n\n# \uD83D\uDC69\uD83C\uDFFB\u200D\uD83D\uDCBB Coding \n- As was said if ```len(nums)<=4``` then minimum difference is 0. \n- Sort ```nums``` to easily find next minimum/maximum\n- Find minimum difference between 4 options: move minimum 2 times and maximum 1, minimum 1 and maximum 2, minimum 3 and maximum 0, minimum 0 and  maximum 3\n\n# \uD83D\uDCD5 Complexity Analysis\n- \u23F0 Time complexity: O(n*log n), since we sort whole array \n- \uD83E\uDDFA Space complexity: O(n), since sorting takes extra space in most languages\n\n# \uD83D\uDCBB Code\n``` python []\nclass Solution:\n    def minDifference(self, nums: list[int]) -> int:\n        if len(nums) <= 4:\n            return 0\n        nums.sort()\n        return min(\n            nums[-4] - nums[0],\n            nums[-1] - nums[3],\n            nums[-3] - nums[1],\n            nums[-2] - nums[2],\n        )\n```\n``` C++ []\nclass Solution {\npublic:\n    int minDifference(vector<int>& nums) {\n        if (nums.size() <= 4) {\n            return 0;\n        }\n        sort(nums.begin(), nums.end());\n        return min({\n            nums[nums.size() - 4] - nums[0],\n            nums[nums.size() - 1] - nums[3],\n            nums[nums.size() - 3] - nums[1],\n            nums[nums.size() - 2] - nums[2]\n        });\n    }\n};\n```\n``` JavaScript []\nvar minDifference = function(nums) {\n    if (nums.length <= 4) {\n        return 0;\n    }\n    nums.sort((a, b) => a - b);\n    return Math.min(\n        nums[nums.length - 4] - nums[0],\n        nums[nums.length - 1] - nums[3],\n        nums[nums.length - 3] - nums[1],\n        nums[nums.length - 2] - nums[2]\n    );\n};\n```\n``` Java []\nclass Solution {\n    public int minDifference(int[] nums) {\n        if (nums.length <= 4) {\n            return 0;\n        }\n        Arrays.sort(nums);\n        return Math.min(\n            Math.min(nums[nums.length - 4] - nums[0], nums[nums.length - 1] - nums[3]),\n            Math.min(nums[nums.length - 3] - nums[1], nums[nums.length - 2] - nums[2])\n        );\n    }\n}\n```\n``` C []\nint compare(const void* a, const void* b) {\n    return (*(int*)a - *(int*)b);\n}\n\nint min(int a, int b) {\n    return a < b ? a : b;\n}\n\nint minDifference(int* nums, int numsSize) {\n    if (numsSize <= 4) {\n        return 0;\n    }\n    qsort(nums, numsSize, sizeof(int), compare);\n    return min(\n        min(nums[numsSize - 4] - nums[0], nums[numsSize - 1] - nums[3]),\n        min(nums[numsSize - 3] - nums[1], nums[numsSize - 2] - nums[2])\n    );\n}\n```\n\n\n# 2\uFE0F\u20E3\uD83D\uDE0E Approach 2: Greedy + Smart Sorting\n\n# \uD83E\uDD14 Intuition\n- To be honest, I\'ve thinked about this but this is first time I learnt about partial sort. We need only four maximum and four minimum elements, so why would we sort whole array for this? \n\n# \uD83D\uDC69\uD83C\uDFFB\u200D\uD83D\uDCBB Coding \n- All the same as before, but now if we have more than 4 elements we want to sort just maximums and minimums\n\n# \uD83D\uDCD7 Complexity Analysis\n- \u23F0 Time complexity: O(n), since we sort up to 8 elements (partial sort time complexity)\n- \uD83E\uDDFA Space complexity: O(1), since partial sort algorithms don\'t use extra memory\n\n# \uD83D\uDCBB Code\n``` python []\nclass Solution:\n    def minDifference(self, nums: list[int]) -> int:\n        n: int = len(nums)\n        if n <= 4:\n            return 0\n        elif n < 8:\n            nums.sort()\n        else:\n            nums = sorted(heapq.nsmallest(4, nums)) + sorted(heapq.nlargest(4, nums))\n\n        return min(\n            nums[-4] - nums[0],\n            nums[-1] - nums[3],\n            nums[-3] - nums[1],\n            nums[-2] - nums[2],\n        )\n```\n``` C++ []\nclass Solution {\npublic:\n    int minDifference(vector<int>& nums) {\n        int n = nums.size();\n        if (n <= 4) {\n            return 0;\n        } else if (n < 8) {\n            sort(nums.begin(), nums.end());\n        } else {\n            vector<int> smallest(nums.begin(), nums.end());\n            vector<int> largest(nums.begin(), nums.end());\n\n            partial_sort(smallest.begin(), smallest.begin() + 4, smallest.end());\n            partial_sort(largest.rbegin(), largest.rbegin() + 4, largest.rend());\n            \n            nums = vector<int>(smallest.begin(), smallest.begin() + 4);\n            nums.insert(nums.end(), largest.rbegin(), largest.rbegin() + 4);\n        }\n        \n        return min({\n            nums[nums.size() - 4] - nums[0],\n            nums[nums.size() - 1] - nums[3],\n            nums[nums.size() - 3] - nums[1],\n            nums[nums.size() - 2] - nums[2]\n        });\n    }\n};\n```\n``` JavaScript []\nvar minDifference = function(nums) {\n    const n = nums.length;\n    if (n <= 4) {\n        return 0;\n    } else if (n < 8) {\n        nums.sort((a, b) => a - b);\n    } else {\n        let smallest = nums.slice().sort((a, b) => a - b).slice(0, 4);\n        let largest = nums.slice().sort((a, b) => b - a).slice(0, 4);\n        nums = smallest.concat(largest.reverse());\n    }\n    return Math.min(\n        nums[nums.length - 4] - nums[0],\n        nums[nums.length - 1] - nums[3],\n        nums[nums.length - 3] - nums[1],\n        nums[nums.length - 2] - nums[2]\n    );\n};\n```\n``` Java []\nclass Solution {\n    public int minDifference(int[] nums) {\n        int n = nums.length;\n        if (n <= 4) {\n            return 0;\n        } else if (n < 8) {\n            Arrays.sort(nums);\n        } else {\n            PriorityQueue<Integer> smallest = new PriorityQueue<>(4);\n            PriorityQueue<Integer> largest = new PriorityQueue<>(4, Collections.reverseOrder());\n\n            for (int num : nums) {\n                smallest.offer(num);\n                if (smallest.size() > 4) {\n                    smallest.poll();\n                }\n                largest.offer(num);\n                if (largest.size() > 4) {\n                    largest.poll();\n                }\n            }\n            \n            int[] combined = new int[8];\n            for (int i = 0; i < 4; ++i) {\n                combined[i] = smallest.poll();\n            }\n            for (int i = 4; i < 8; ++i) {\n                combined[i] = largest.poll();\n            }\n            nums = combined;\n            Arrays.sort(nums);\n        }\n        return Math.min(\n            Math.min(nums[n - 4] - nums[0], nums[n - 1] - nums[3]),\n            Math.min(nums[n - 3] - nums[1], nums[n - 2] - nums[2])\n        );\n    }\n}\n```\n``` C []\nint compare(const void* a, const void* b) {\n    return (*(int*)a - *(int*)b);\n}\n\nvoid partial_sort(int* nums, int numsSize, int k) {\n    qsort(nums, numsSize, sizeof(int), compare);\n}\n\nint min(int a, int b) {\n    return a < b ? a : b;\n}\n\nint minDifference(int* nums, int numsSize) {\n    if (numsSize <= 4) {\n        return 0;\n    } else if (numsSize < 8) {\n        qsort(nums, numsSize, sizeof(int), compare);\n    } else {\n        int smallest[4];\n        int largest[4];\n        int smallestSize = 0;\n        int largestSize = 0;\n        int i;\n\n        for (i = 0; i < numsSize; i++) {\n            if (smallestSize < 4) {\n                smallest[smallestSize++] = nums[i];\n                if (smallestSize == 4) {\n                    partial_sort(smallest, 4, 4);\n                }\n            } else if (nums[i] < smallest[3]) {\n                smallest[3] = nums[i];\n                partial_sort(smallest, 4, 4);\n            }\n\n            if (largestSize < 4) {\n                largest[largestSize++] = nums[i];\n                if (largestSize == 4) {\n                    partial_sort(largest, 4, 4);\n                }\n            } else if (nums[i] > largest[3]) {\n                largest[3] = nums[i];\n                partial_sort(largest, 4, 4);\n            }\n        }\n\n        for (i = 0; i < 4; i++) {\n            nums[i] = smallest[i];\n            nums[4 + i] = largest[i];\n        }\n        qsort(nums, 8, sizeof(int), compare);\n    }\n    return min(\n        min(nums[numsSize - 4] - nums[0], nums[numsSize - 1] - nums[3]),\n        min(nums[numsSize - 3] - nums[1], nums[numsSize - 2] - nums[2])\n    );\n}\n```\n\n## \uD83D\uDCA1\uD83D\uDCA1\uD83D\uDCA1I encourage you to check out [my profile](https://leetcode.com/heir-of-god/) and [Project-S](https://github.com/Heir-of-God/Project-S) project for detailed explanations and code for different problems (not only Leetcode). Happy coding and learning!\uD83D\uDCDA\n\n### Please consider *upvote*\u2B06\uFE0F\u2B06\uFE0F\u2B06\uFE0F because I try really hard not just to put here my code and rewrite testcase to show that it works but explain you WHY it works and HOW. Thank you\u2764\uFE0F\n\n## If you have any doubts or questions feel free to ask them in comments. I will be glad to help you with understanding\u2764\uFE0F\u2764\uFE0F\u2764\uFE0F\n\n![There is image for upvote](https://assets.leetcode.com/users/images/fde74702-a4f6-4b9f-95f2-65fa9aa79c48_1716995431.3239644.png)\n
['Array', 'Greedy', 'C', 'Sorting', 'Python', 'C++', 'Java', 'Python3', 'JavaScript']