Nth_element and Single Pass| C++ 11 ms 100% | Java 2 ms 100% | Python3 241 ms 99%
Intuition\nUsing no more than 3 element removals, we need to minimize the array diameter, which is the max difference between its elements (the task statement s
# Intuition\nUsing no more than 3 element removals, we need to minimize the array diameter, which is the max difference between its elements (the task statement says "change element to any value", but from the target function perspective it\'s effectively the same as the element removal).\n\nObviously we are going to choose among minimal and maximal elements, specifically from these cases:\n* Remove 3 minimums\n* Remove 2 minimums and 1 maximum\n* Remove 1 minimum and 2 maximums\n* Remove 3 maximums\n\nThe first case requires access to the 4-th minimum, and the last case requires access to the 4-th maximum. Once we have these, we can simply pick the minimal diameter from the following expressions:\n* Ultimate maximum - 4-th minimum\n* 2-nd maximum - 3-rd minimum\n* 3-rd maximum - 2-nd minimum\n* 4-th maximum - ultimate minimum\n\nConsidering the limitations (up to $10^5$ array elements and their values in the range of $[-10^9; 10^9]$), the main performance-affecting matter is how to pick those 4 minimums and 4 maximums.\n\n# Approach\n\nFor 4-element or shorter arrays the result is 0 since the set degrades to 1 point after 3 or fewer element removals.\n\nIf we have 8 or fewer elements, we can sort the array using a standard library sort routine, and this will give us the smallest 4 elements at the beginning of the array and the largest 4 elements at the end of the array, in ascending order. We can take this route for slightly larger sizes, e.g. 16 or 32, but for $n=10^3$ we are going to have an average of $n \\times log_2(n) = 10^4$ element swaps to achieve full ordering, which we actually don\'t need; we only need min 4 and max 4 elements. For the maximal length of $10^5$ the standard library sort would give us an average of $1.7 \\times 10^6$ element comparisons, which is too slow.\n\nThe element value range is too wide for a Count sort. Radix sort might be a better choice, but it has too high constant multiplier. It might be more practical to use a quick selection algorithm.\n\n## Quick Select\n\nC++ has a nice STL function `nth_element`, which does all the magic. We pick the 4 smallest elements with one call and the 4 largest elements with another call. We can even exclude the first 4 elements from the second call\'s range since we know they are minimal. Then we sort 4-element subarrays on both ends (even bubble sort would do).\n\nJDK is not generous enough, so we have to implement our own `nth_element`. It\'s similar to Quicksort with the main distinction of recursion going to just one half of the array. Subarrays small enough are sorted using a JDK function.\n\nThe number of swaps in `nth_element` would be $C \\times (n + \\frac n k + \\frac n {k^2} + ...) = C \\times n \\times \\frac {1 - \\frac 1 k} {1 - \\frac 1 {k^{log_2(n)}}} = C \\times n \\times {k^{log_2(\\frac n 2)}} \\frac {k - 1} {k^{log_2(n)} - 1}$ where $1 \\le k \\le 2 $ depends on the quality of the pivot choice, and $C$ is a constant. So the algorithm time complexity becomes linear except the wost case with $k$ degenerating to $1$ and making the series diverge. This can be countered by picking a median-3 pivot or some other techniques, but we don\'t use those here to minimize expensive array accesses in Java.\n\nAs for Python, its main rule is "never implement algorithms in Python". Enormously high cost of interpreted language and its data structures often nullifies asymptotic complexity advantage. Whatever we program in Python, we should seek for out-of-the-box implementations of algorithms in C libraries. A quick selection implementation is available in _numpy_, but copying all the list data to a _numpy_ array would degrade the memory complexity to $O(n)$.\n\n## Multi-Value Accumulation\n\nAn alternative way to find minimums and maximums is to collect them in a separate accumulator during a single pass.\n\nFor C++ we could use local variables (4 for min and 4 for max, maintaining sorted lists in them). The advantage of this approach is that if the CPU has enough named registers, the entire calculation can go without memory accesses (apart from reading the input array). We could even use binary search to determine the insertion point. E.g. if we had maximums `10 5 1 0`, and we need to insert `14`, we could first compare it to the second element (`5`) and depending on the result, seek the insertion point to the left or to the right of it. For 5 possible insertion points there would be no more than 3 comparisons in total, resulting in $O(n \\times \\lceil log_2(m+1) \\rceil)$ comparisons and $2 \\times n$ swaps where $m$ is the number of extremums to track.\n\nA heap-based accumulation in $4 \\times 2$ variables is also possible for C++, giving the same asymptotic complexity and potentially better execution time (for moving fewer elements on average insertions).\n\nA Python implementation, as mentioned above, should look for a library function to do the algorithm. We could use a builtin `sort` for smaller arrays and heap-based n-minimum and n-maximum search from `heapq`. Different watermarks have been tried, and we have chosen 64.\n\n# Complexity\n- Time complexity: $O(n)$\n- Space complexity: $O(1)$\n\n# Code\n\n## Quick Select\n\n``` C++ []\nclass Solution {\npublic:\n    static int minDifference(vector<int>& nums) {\n        const uint n = nums.size();\n        if (n <= 4) return 0;\n        const auto beg = nums.begin(), end = nums.end();\n        if (n <= 16)\n            sort(beg, end);\n        else {\n            nth_element(beg, beg + 3u, end);\n            sort(beg, beg + 4u);\n            nth_element(beg + 4u, end - 4u, end);\n            sort(end - 4u, end);\n        }\n        return min(min(nums[n-4u]-nums[0], nums[n-3u]-nums[1]), min(nums[n-2u]-nums[2], nums[n-1u]-nums[3]));\n    }\n};\n```\n``` Java []\nclass Solution {\n    private static void nth_element(final int[] arr, final int ibeg, final int pos, final int iend) {\n        if (ibeg + 8 >= iend) {\n            Arrays.sort(arr, ibeg, iend);\n            return;\n        }\n        int beg = ibeg, end = iend;\n        final var pivot = arr[(beg+end)/2];\n\n        // Divide the values about the pivot\n        while (true) {\n            while (beg + 1 < end && arr[beg] < pivot)\n                beg++;\n            while (end > beg + 1 && arr[end-1] > pivot)\n                end--;\n            if (beg + 1 >= end)\n                break;\n\n            final var t = arr[beg];\n            arr[beg] = arr[end-1];\n            arr[end-1] = t;\n            beg++;\n            end--;\n        }\n        if (arr[beg] < pivot)\n            beg++;\n\n        // Recurse on one of the two sides\n        nth_element(arr, pos < beg ? ibeg : beg, pos, pos < beg ? beg : iend);\n    }\n\n    public static int minDifference(final int[] nums) {\n        final int n = nums.length;\n        if (n <= 4) return 0;\n        if (n <= 16)\n            Arrays.sort(nums);\n        else {\n            nth_element(nums, 0, 3, n);\n            Arrays.sort(nums, 0, 4);\n            nth_element(nums, 4, n - 4, n);\n            Arrays.sort(nums, n - 4, n);\n        }\n        return Math.min(Math.min(nums[n-4]-nums[0], nums[n-3]-nums[1]), Math.min(nums[n-2]-nums[2], nums[n-1]-nums[3]));\n    }\n}\n```\n\n## Multi-Value Accumulation - Sorted List\n\n``` C++ []\nclass Solution {\npublic:\n    static int minDifference(vector<int>& nums) {\n        const uint n = nums.size();\n        if (n <= 4) return 0;\n        const auto beg = nums.begin(), end = nums.end();\n        int a = INT_MAX, b = INT_MAX, c = INT_MAX, d = INT_MAX,\n            w = INT_MIN, x = INT_MIN, y = INT_MIN, z = INT_MIN;\n        for (const int v : nums) {\n            if (v < b) {\n                d = c, c = b;\n                if (v < a) b = a, a = v;\n                else b = v;\n            }\n            else if (v < c) d = c, c = v;\n            else if (v < d) d = v;\n            if (v > x) {\n                z = y, y = x;\n                if (v > w) x = w, w = v;\n                else x = v;\n            }\n            else if (v > y) z = y, y = v;\n            else if (v > z) z = v;\n        }\n        return min(min(z - a, y - b), min(x - c, w - d));\n    }\n};\n```\n\n## Multi-Value Accumulation - Heap\n\n``` C++ []\nclass Solution {\npublic:\n    static int minDifference(vector<int>& nums) {\n        const uint n = nums.size();\n        if (n <= 4) return 0;\n        const auto beg = nums.begin(), end = nums.end();\n        int a = INT_MAX, b = INT_MAX, c = INT_MAX, d = INT_MAX, // max-heap for mins:  a > b  a > c  b > d\n            w = INT_MIN, x = INT_MIN, y = INT_MIN, z = INT_MIN; // min-heap for maxes: w < x  w < y  x < z\n        for (const int v : nums) {\n            if (v < a) {\n                // push v\n                int e;\n                if (v > b) e = b, b = v;\n                else e = v;\n                // pop\n                if (b > c) {\n                    a = b;\n                    if (d > e) b = d, d = e;\n                    else b = e;\n                }\n                else a = c, c = e;\n            }\n            if (v > w) {\n                // push v\n                int t;\n                if (v < x) t = x, x = v;\n                else t = v;\n                // pop\n                if (x < y) {\n                    w = x;\n                    if (z < t) x = z, z = t;\n                    else x = t;\n                }\n                else w = y, y = t;\n            }\n        }\n        // Convert heaps to sorted lists\n        if (b < c) swap(b, c);\n        else if (c < d) swap(c, d);\n        if (x > y) swap(x, y);\n        else if (y > z) swap(y, z);\n        return min(min(z - a, y - b), min(x - c, w - d));\n    }\n};\n```\n``` Python3 []\nclass Solution:\n    def minDifference(self, nums: List[int]) -> int:\n        # 3 cases depending on length\n        n = len(nums)\n        if n <= 4: return 0\n        if n <= 64:\n            nums.sort()\n            ns = nums[:4]\n            nl = nums[:-5:-1]\n        else:\n            ns = heapq.nsmallest(4, nums)\n            nl = heapq.nlargest(4, nums)\n        return min(nl[3]-ns[0], nl[2]-ns[1], nl[1]-ns[2], nl[0]-ns[3])\n```\n\n# Measurements\n\n|Language|Algorithm|Time, ms|Beating|Memory, Mb|Beating|Submission Link|\n|-|-|-|-|-|-|-|\n|C++|Quick Select|11|100%|37.62|97.67%|https://leetcode.com/problems/minimum-difference-between-largest-and-smallest-value-in-three-moves/submissions/1307832772|\n|C++|Sorted List|14|100%|37.81|94.31%|https://leetcode.com/problems/minimum-difference-between-largest-and-smallest-value-in-three-moves/submissions/1308231423|\n|C++|Heap|15|100%|37.8|95.34%|https://leetcode.com/problems/minimum-difference-between-largest-and-smallest-value-in-three-moves/submissions/1308571539|\n|Java|Quick Select|2|100%|56.73|83.99%|https://leetcode.com/problems/minimum-difference-between-largest-and-smallest-value-in-three-moves/submissions/1307928224|\n|Python3|Heap|241|99.06%|27.89|19.81%|https://leetcode.com/problems/minimum-difference-between-largest-and-smallest-value-in-three-moves/submissions/1308101213|
['Array', 'Sorting', 'Quickselect', 'C++', 'Java', 'Python3']