319. Minimum Removals From Array to Make Max Minus Min At Most K

Given an array of n integers and an integer K, find the minimum number of elements that must be removed so that, among the remaining elements, the difference between the maximum and the minimum is at most K.

Input: Three lines: n; n space-separated integers; the integer K. Output: Print a single integer - the minimum number of elements that must be removed so max - min <= K among the rest.

1 <= n <= 10^5

This is technically a two-pointer/sliding-window problem dressed up as DP-adjacent (it's categorized here for its 'reduce to an optimal substructure via sorting' flavor) - recognizing the underlying two-pointer technique is more important than forcing an explicit DP table.

Find the minimum number of elements to remove so the remaining elements' max minus min is at most K. Brute force: Try every possible subset of the array and check its max-min spread, finding the largest valid one - this is exponential (2^n subsets), impractical for n up to 10^5. Optimised: Sorting first proves that only CONTIGUOUS ranges of the sorted array ever need to be considered as optimal candidates - a two-pointer sweep then finds the largest such valid range in a single linear pass, since both pointers only ever move forward.

Sort the array, then for each left boundary index i, binary search for the rightmost index j such that arr[j] - arr[i] <= K, since the sorted array guarantees everything between i and j also satisfies the bound. The window length is j - i + 1, and the largest such window across all i gives the maximum number of elements that can be kept, so the answer is n minus that maximum. This replaces the brute force's linear rescan for every starting point with a logarithmic search, which is faster whenever windows are long, though it doesn't yet exploit the fact that the right boundary only ever moves forward as the left boundary advances. Time: O(n log n) Space: O(1)

Sort the array, then use two pointers: as the left pointer advances one step at a time, the right pointer only ever needs to move forward (never backward) to stay within the K bound, since the array is sorted and shrinking the window from the left can only make more elements fit on the right. This means the right pointer traverses the whole array at most once in total across all left positions, avoiding the repeated binary searches of the previous approach and shrinking the per-element work from logarithmic to amortized constant, leaving the overall cost dominated purely by the initial sort. Time: O(n log n) Space: O(1)

Sort the array first so elements are in order, then for every possible starting element (acting as the minimum of a kept subset), scan forward linearly counting how many subsequent elements are within K of it before the difference exceeds K, keeping track of the largest such count found across all starting points. The answer is n minus that maximum count, since keeping the largest valid window means removing the fewest elements. Recomputing a fresh linear scan from every starting index makes this quadratic overall. Time: O(n^2) Space: O(1)

1. Sort the array - once sorted, any subset kept without removal is optimal to keep as a CONTIGUOUS run of the sorted array (skipping elements can only hurt, since keeping a wider contiguous range never increases the spread more than a scattered subset would need to). 2. Use TWO POINTERS over the sorted array: for each right endpoint i, advance the left pointer j while arr[i]-arr[j] > K. 3. Track the LARGEST valid window length found; the answer is n minus that length.

Time: O(n log n), dominated by the initial sort - the two-pointer sweep afterward is O(n). Space: O(1) extra space beyond the sort itself.

Test n = 1 (0 removals needed), an array already within K of itself (0 removals), and n = 10^5 (upper bound) for the sort-plus-two-pointer approach.

Be ready to justify explicitly why only CONTIGUOUS sorted ranges need to be considered - any non-contiguous kept subset could always be replaced by a contiguous range of the same size with an equal or smaller spread, since sorting groups similar values together.