Beats 96% | Best Solution | Explained💯
Intuition\n\nThoughts:\n1. Two pointer : Failed when realised you can\'t make more than 3 moves\n2. Recursion : As there were 4 possibilites strinking, but migh
# Intuition\n\nThoughts:\n1. Two pointer : Failed when realised you can\'t make more than 3 moves\n2. Recursion : As there were 4 possibilites strinking, but might give TLE\n3. Sorting and Greedy : THIS WORKS!\n\n# Approach\n\nSo I realised that if we can sort the array we just have to deal with the maximum and minimum elements in order to minimise the difference, so let\'s find out with an example:\n\nSuppose, I have `[1,5,0,10,14]`\n\nThe current minimum and maximum is 0 and 14, but we can do 3 operations on any of the 3 to minimise the difference, so let\'s observe that after sorting it becomes `[0,1,5,10,14]`. Now maximum difference with no operations is 14-0 = 14. \n\n$$Operation 1 :$$ So let\'s change either the 0 to 14 or 14 to 0, now it becomes `[0,1,5,10,0]`.\n\n$$Operation 2 :$$ Now maximum difference is 10-0 = 10, so lets change the 10 to 0 or 0 to 10, now it becomes `[0,1,5,0,0]`.\n\n$$Operation 3 :$$ Now difference is 5-0 = 5, so lets change 5 to 0 as well, now finally it becomes `[0,1,0,0,0]`.\n\nFinally we have exhausted all the operations and our answer is 1. Did you notice something?\n\nWe applied operations on the last 3 elements of the array in order to minimise it, thus applying on last 3 is a possibility. Similarly we can also apply on first three to make them equal of the 3 greater elements in order to minimise difference in the middle. Another one can be change the first two elements and change the last element and finally change the last two elements and first element only.\n\nThis works because the array is sorted and the elements that can create the maximum difference are residing at the extremes only.\n\nSo, to conclude:\n\n1. Sort the array\n2. $$Possibility 1$$ : `Change the last 3 elements`. So we can return n[n-4] - n[0];\n3. $$Possibility 2$$ : `Change the first 3 elements`. So we can return n[n-1] - n[3];\n4. $$Possibility 3$$ : `Change the last 2 and first 1 elements`. So we can return n[n-3] - n[1];\n5. $$Possibility 4$$ : `Change the last 1  and first 2 elements`. So we can return n[n-2] - n[2];\n\nThis all works for array length > 5. What is the array is of smaller length? It will always yeild answer as 0. How? TRY TO THINK. :)\n\n\n# Complexity\n- Time complexity: `O(n.log(n))`\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: `O(1)`\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n\n```java []\nclass Solution {\n    public int minDifference(int[] nums) {\n      if(nums.length < 5) return 0;\n      Arrays.sort(nums);\n      int p1 = nums[nums.length - 1] - nums[3];\n      int p2 = nums[nums.length - 2] - nums[2];\n      int p3 = nums[nums.length - 3] - nums[1];\n      int p4 = nums[nums.length - 4] - nums[0];\n      return Math.min(p1, Math.min(p2, Math.min(p3, p4)));\n    }\n}\n```\n```C++ []\nclass Solution {\npublic:\n    int minDifference(std::vector<int>& nums) {\n        if (nums.size() < 5) return 0;\n        std::sort(nums.begin(), nums.end());\n        int p1 = nums[nums.size() - 1] - nums[3];\n        int p2 = nums[nums.size() - 2] - nums[2];\n        int p3 = nums[nums.size() - 3] - nums[1];\n        int p4 = nums[nums.size() - 4] - nums[0];\n        return std::min({p1, p2, p3, p4});\n    }\n};\n\n```\n```python []\nclass Solution:\n    def minDifference(self, nums):\n        if len(nums) < 5:\n            return 0\n        nums.sort()\n        p1 = nums[-1] - nums[3]\n        p2 = nums[-2] - nums[2]\n        p3 = nums[-3] - nums[1]\n        p4 = nums[-4] - nums[0]\n        return min(p1, p2, p3, p4)\n```\n```Javascript []\nclass Solution {\n    minDifference(nums) {\n        if (nums.length < 5) return 0;\n        nums.sort((a, b) => a - b);\n        let p1 = nums[nums.length - 1] - nums[3];\n        let p2 = nums[nums.length - 2] - nums[2];\n        let p3 = nums[nums.length - 3] - nums[1];\n        let p4 = nums[nums.length - 4] - nums[0];\n        return Math.min(p1, p2, p3, p4);\n    }\n}\n```\n# UPVOTE PLEASE \uD83E\uDD79\uD83D\uDE4F
['Array', 'Greedy', 'Sorting', 'Python', 'C++', 'Java', 'Python3', 'JavaScript']