Min Amplitude Google Python Interview Question

Given an integer array , the difference between the largest and smallest values is called amplitude. If you can change up to three elements of the array to any value, return the minimum possible amplitude.

Examples:

Example 1:

Input: arr = [4, -8, -1, 3, 7, 10, 5]

Output: 4

Explanation: By changing -8 and -1 to 3, and 10 to 7, the array can be transformed into [4, 3, 3, 3, 7, 7, 5]. The new maximum value is 7 and the new minimum value is 3, resulting in an amplitude of 7 - 3 = 4.

Example 2:

Input: arr = [3, 5, 10, 0]

Output: 0

Explanation: We can change 3, 5, and 10 to 0, resulting in the array [0, 0, 0, 0]. Since all values are the same, the maximum and minimum values are both 0, leading to an amplitude of 0 - 0 = 0.

Intuition

To minimize the amplitude of the array, we need to focus on reducing the gap between the largest and smallest values. Since we can change up to three numbers to any value, we should aim to make extreme values (either the largest or smallest) closer together.

Here's the idea:

1. Identify the largest and smallest numbers in the array since they directly influence the amplitude.
2. Change these extreme values to something closer to the middle values of the array.

For instance, let’s consider an example:

Given an array:

• Without changing any values, the amplitude is .
• By changing the largest () to a lower value and the smallest () to a higher one, we can reduce this amplitude.

Suppose we make these changes:

• Change to and to , resulting in .
• Now, the current largest element is (was the second largest originally) and the smallest is (was the second smallest).

With these changes, our new amplitude is .

But, we still have the option to change one more element! By changing either the next smallest or next largest value, we might make the amplitude even smaller. It’s important to explore different options, since sometimes changing the three largest or three smallest values (or a combination) gives the smallest possible amplitude.

Approach

To simplify this process, we can sort the array. Sorting allows us to efficiently find the next largest or smallest values after each potential change.

With a sorted array, we can try four main cases:

1. Change the three smallest elements: The new smallest number will be the fourth element, and the largest remains the last element.
2. Change two smallest elements and the largest element: The new smallest number will be the third element, and the largest will be the second-to-last.
3. Change the smallest element and two largest elements: The new smallest will be the second element, and the largest will be the third-to-last.
4. Change the three largest elements: The new smallest is the first element, and the largest is the fourth-to-last.

After trying all four combinations, we take the smallest difference among them.

Edge Case

If the array has fewer than 5 elements, we can return immediately since we can change all elements to be the same.

---

Algorithm

1. Sort the array to access elements in ascending order.
2. Handle cases with arrays of fewer than 5 elements by returning .
3. Compute the amplitude for each of the four cases by adjusting elements as described.
4. Return the minimum amplitude.

Here is the code: