Minimize Amplitude After K Removals - Google Top Interview Questions

                        Solution in C++ :

int solve(vector<int>& nums, int k) {
    int n = nums.size();
    sort(nums.begin(), nums.end());  // O(nlogn)
    int min = nums.back() - nums[0];
    if (k == 0) return min;
    for (int i = 0; i + n - k - 1 < nums.size(); ++i) {  // O(n)
        if (nums[i + n - k - 1] - nums[i] < min) min = nums[i + n - k - 1] - nums[i];
    }
    return min;
}
                    

                        Solution in Java :

import java.util.*;

class Solution {
    public int solve(int[] nums, int k) {
        Arrays.sort(nums);
        int n = nums.length;
        if (k >= n - 1)
            return 0;

        int res = Integer.MAX_VALUE;
        for (int i = 0; i <= k; i++) {
            int remove_other = k - i;
            // remove i from left
            res = Math.min(res, nums[n - 1 - remove_other] - nums[i]);

            // remove i from right
            res = Math.min(res, nums[n - 1 - i] - nums[remove_other]);
        }
        return res;
    }
}
                    

                        Solution in Python : 
                            
class Solution:
    def solve(self, nums, k):
        keep = len(nums) - k
        nums.sort()
        return min(nums[i + keep - 1] - nums[i] for i in range(len(nums) - keep + 1))