try all combos | solution for generic k moves
Intuition & Approach\n\nFirst note that instead of "changing" the elements, we can simply remove them instead, since we\'re allowed to change them to any value,
# Intuition & Approach\n\nFirst note that instead of "changing" the elements, we can simply remove them instead, since we\'re allowed to change them to any value, which means we can always change the chosen elements to the median of the input, thereby making their remaining presence in the array inconsequential.\n\nNow we first sort the input array, then try all possible combinations of `k`-removals: i.e. remove the first `k` elements from the left end of the sorted array (the `k`-smallest elements), and get the difference between the `k+1`-th (1-indexed) element (the new minimum) and the last element (the maximum); then try removing the smallest `k-1`-smallest elements plus the largest element, and get the difference between the `k`-th element (the new minimum) with the second last element (the new maximum); and so on, in the end we can just return the minimum difference found in all of those combinations of removals.\n\n# Code\n```\nclass Solution:\n    def minDifference(self, nums: List[int]) -> int:\n        k = 3   # maximum of 3 moves considered for this question\n\n        if len(nums) <= k + 1:\n            return 0\n\n        res, _ = math.inf, nums.sort()\n        for (a, b) in [(k - i, -(1 + i)) for i in range(k + 1)]:\n            # (a, b) will take on index values of: {(k, -1), (k-1, -2),\n            # (k-2, -3), ..., (2, -(k-1)) , (1, -k), (0, -(k+1))}; for\n            # k = 3, these are: {(3, -1), (2, -2), (1, -3), (0, -4)}\n            res = min(res, nums[b] - nums[a])\n\n        return res\n```\n\n# Complexity\n- Time complexity: $$O(nlogn)$$ for sorting `nums`\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(k)$$, where $k$ is the max number of moves allowed\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->
['Sorting', 'Python3']