JAVA - sorting O(nLog(n)) - only 4 choices
Once we have array sorted, we can cut down this problem to selecting among only 4 choices for making 3 moves. \n\nConsider below example:\na b c d e f g h i j (
Once we have array sorted, we can cut down this problem to selecting among only 4 choices for making 3 moves. \n\nConsider below example:\na b c d e f g h i j (say, this array is sorted)\n\n1. Will it matter if you change d, e, f, g to anything? No. You can set them all to a or j, and result will still be same.\n2. This means our focus can be concentrated on only changing either first three or last three elements.\n3. We can make following moves \n\ta. 3 from last, 0 from start. Set h, i, j to anything else between a - g. Diff: g - a\n\tb. 2 from last, 1 from start. Set i,j to anything between b - h, same for a. Diff: h - b\n\tc. 1 from last, 2 from start. Set j to anything between c - i, same for a,b. Diff: i - c\n\td. 0 from last, 3 from start. Set a,b,c to anything between d - j. Diff: j - d\n4. We can take minimum of these 4 scenarios and there goes our answer.\n5. Also, if array length is <= 4, you can set other three elements same as 4th one, making the difference 0.\n\n```\nclass Solution {\n    public int minDifference(int[] nums) {\n        if(nums.length <= 4)\n            return 0;\n        \n        int n = nums.length;\n        Arrays.sort(nums);\n        return Math.min(\n            Math.min(nums[n-1] - nums[3], nums[n-2] - nums[2]),\n            Math.min(nums[n-3] - nums[1], nums[n-4] - nums[0])\n        );\n    }\n}\n```\n\nTime complexity: O(n Log(n) ) (for sorting)\nspace complexity: O(1)
['Sorting', 'Java']