Python Easy to Understand Beats 92% With Explanation
Idea\nWe take a greedy approach to this problem. The greedy property is as follows:\n> There exists an optimal solution where the selected students form a subar
# Idea\nWe take a greedy approach to this problem. The greedy property is as follows:\n> There exists an optimal solution where the selected students form a subarray of the sorted scores.\n\nTo rephrase, we are claiming that an optimal solution may be selected from the subarrays of the array of sorted scores. To see that this claim is true, consider any arbitrary optimal solution. We may consider this solution as a subset of the sorted scores array. \n\nConsider the subarray of length `k` of the sorted scores array ending at the maximum element of this subset. It has the same maximum as the maximum of the subset, since the sorted scores array is sorted. But, its minimum is at least the minimum of the subset, since it must occur on or after it in the sorted array. Since the original subset was assumed to be optimal, we must conclude that this subarray is also optimal. That is, if an optimal solution exists, then there must exist an optimal solution using a subarray of the sorted scores. Given that an optimal solution must clearly exist, we are done.\n\nThis motivates the following algorithm:\n1. Sort `nums`\n2. Iterate through the `len(nums) - k + 1` subarrays of `nums` of size `k`, and find the one with minimum difference between its maximum and minimum element\n# Code\n```\ndef minimumDifference(nums: List[int], k: int) -> int:\n\tnums.sort()\n\tbest = float(\'inf\')\n\tfor i in range(len(nums) - k + 1):\n\t\tbest = min(best, nums[i+k - 1] - nums[i])\n\treturn best\n```\n Note that we initialize `best` to `float(\'inf\')` to ensure that it will not be selected in the `min` function call.\n # Runtime Analysis\n Let `n = len(nums)`. The sorting step takes `O(n log n)` time, and the iteration takes `O(n - k)` time, for a total runtime of `O(n log n)`. The memory used depends on the sorting methon. Python\'s default sorting method is [Timsort](https://en.wikipedia.org/wiki/Timsort), which uses `O(n)` memory, but with [Heapsort](https://en.wikipedia.org/wiki/Heapsort), this may be done with `O(1)` memory.\n \n This solution ran in 115ms, beating 92.14%, and used 14.1MB of memory, beating 92.51%.
['Greedy', 'Sliding Window', 'Python']