Min Amplitude
Given an Array A, find the minimum amplitude you can get after changing up to 3 elements. Amplitude is the range of the array (basically difference between largest and smallest element).
Example 1:
Input: [1, 3, 1, 8, 5 4] Output: 2 Explanation: we can change 1, 1, 8 to 3, 4 or 5 Example 2:
Input: [10, 10, 3, 4, 10] Output: 0 Explanation: change 3 and 4 to 10
Here is an approach to find the minimum amplitude after changing up to 3 elements in the array:
Sort the array in ascending order.
Initialize min amplitude as the difference between the last and first elements (range of original array).
Iterate through the array:
 Try changing the current element to the element before and after it, up to 3 changes.
 Compute the new amplitude as max  min in the modified array.
 Update the min amplitude if the new amplitude is smaller.
 Return the min amplitude.


The key ideas are:
 Sort to simplify min/max calculation
 Iterate through, changing elements and computing amplitude
 Track minimum amplitude found
We change up to 3 elements this way and take the minimum resulting amplitude.
Efficient Solution
You don’t need a full sort. You only need to know the 3 greatest and 3 least elements. Scanning the array that many times may sound like a lot but it’s asymptotically better than sorting.
Sorting the entire array is unnecessary for this problem. A better approach is:
Find the 3 smallest elements using linear scan (O(N))
Find the 3 largest elements using linear scan (O(N))
Initialize min amplitude as difference between max of 3 largest and min of 3 smallest (O(1))
Iterate through remaining elements (O(N)):
 Try changing element to one of the 3 largest or smallest (O(1))
 Compute new amplitude (O(1))
 Update min amplitude if smaller (O(1))
Return min amplitude
This reduces the complexity from O(NlogN) for sorting to O(N) since we only need a few linear scans.
The key insight is that we don’t need the entire array sorted, just the extremes to compute amplitude. Finding these extremes in linear time is sufficient.
You’re right that a sorting based approach is overkill for this specific problem. Great observation! Using linear scans to find only the necessary min/max values is far more optimal.
Here is Python code implementing the optimized approach using linear scans to find min/max rather than full sort:


Key points:
 Linearly scan once to find 3 min, once for 3 max
 Skip min/max values when iterating rest
 Check changing to min or max
 Update min amplitude
This minimizes work by avoiding full sort and only finding min/max values needed.