Problem

You are given an integer array nums.

In one move, you can choose one element of nums and change it to any value.

Return the minimum difference between the largest and smallest value of nums after performing at most three moves.

Examples

Example 1:

1
2
3
4
5
6
7

Input: nums = [5,3,2,4]
Output: 0
Explanation: We can make at most 3 moves.
In the first move, change 2 to 3. nums becomes [5,3,3,4].
In the second move, change 4 to 3. nums becomes [5,3,3,3].
In the third move, change 5 to 3. nums becomes [3,3,3,3].
After performing 3 moves, the difference between the minimum and maximum is 3 - 3 = 0.

Example 2:

1
2
3
4
5
6
7
8

Input: nums = [1,5,0,10,14]
Output: 1
Explanation: We can make at most 3 moves.
In the first move, change 5 to 0. nums becomes [1,0,0,10,14].
In the second move, change 10 to 0. nums becomes [1,0,0,0,14].
In the third move, change 14 to 1. nums becomes [1,0,0,0,1].
After performing 3 moves, the difference between the minimum and maximum is 1 - 0 = 1.
It can be shown that there is no way to make the difference 0 in 3 moves.

Example 3:

1
2
3
4
5
6
7

Input: nums = [3,100,20]
Output: 0
Explanation: We can make at most 3 moves.
In the first move, change 100 to 7. nums becomes [3,7,20].
In the second move, change 20 to 7. nums becomes [3,7,7].
In the third move, change 3 to 7. nums becomes [7,7,7].
After performing 3 moves, the difference between the minimum and maximum is 7 - 7 = 0.

Solution

Method 1 - Sorting

Intuition

If we have a sorted array, say in ascending order, we can see the difference between the elements is between elements at 0 and n - 1 index, where n is length of the array. But, here we have 3 moves given to us where we can change these values, to reduce this difference. For eg. we can make the largest 3 elements equal to smallest element.

Now, we have 4 plans:

  1. Remove the 3 largest elements.
  2. Remove the 2 largest elements and the smallest element.
  3. Remove the largest element and the 2 smallest elements.
  4. Remove the 3 smallest elements.
1
2

nums = [2,4,7,9,10,13,15,20]
n = 8
Case 1: Remove 3 largest elements

All three biggest elements can be replaced with 10

1

[2,4,7,9,10,13,15,20] -> [2,4,7,9,10,10,10,10] == can be written as nums[n - 4] - nums[0] == (10 - 2 = 8)
Case 2: Remove 2 largest elements + 1 smallest elements
1

[2,4,7,9,10,13,15,20] -> [4,4,7,9,10,13,13,13] == can be written as nums[n - 3] - nums[1] == (13 - 4 = 9)
Case 3: Remove 1 largest elements + 2 smallest elements
1

[2,4,7,9,10,13,15,20] -> [7,7,7,9,10,13,15,15] == can be written as nums[n - 2] - nums[2] == (15 - 7 = 9)
Case 4: Remove 3 smallest elements
1

[2,4,7,9,10,13,15,20] -> [9,9,9,9,10,13,15,20] == can be written as nums[n - 1] - nums[3] == (20 - 9 = 11)

Answer is minimum of all these cases, i.e. 8.

Video Explanation

Here is the video explanation of the same:

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {

	public int minDifference(int[] nums) {
		int n = nums.length;

		// If array has 4 or fewer elements, return 0 difference (all elements can be made equal)
		if (n <= 4) {
			return 0;
		}

		Arrays.sort(nums);

		int case1 = nums[n - 4] - nums[0];
		int case2 = nums[n - 3] - nums[1];
		int case3 = nums[n - 2] - nums[2];
		int case4 = nums[n - 1] - nums[3];

		return Math.min(Math.min(case1, case2), Math.min(case3, case4));

	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {

	public int minDifference(int[] nums) {
		int n = nums.length;

		// If array has 4 or fewer elements, return 0 difference (all elements can be made equal)
		if (n <= 4) {
			return 0;
		}

		Arrays.sort(nums);
		int ans = nums[n - 1] - nums[0];

		for (int i = 0; i <= 3; i++) {
			ans = Math.min(ans, nums[n - 1 - (3 - i)] - nums[i]);
		}

		return ans;
	}
}

Complexity

  • ⏰ Time complexity: O(n log n) where n is array size
  • 🧺 Space complexity: O(1)

Method 2 - Using max heap and min heap

Similar result can be obtained by storing the values in max and min heap, and get the results. We can just store 4 elements in both max and min heap, and calculate the values accordingly.

Method 3 - Using only 4 max and min elements

We only need the first four smallest and the last four largest numbers, thus sorting the entire array is unnecessary. Instead, we can use an array of size 4 to keep track of the top 4 smallest and top 4 largest elements.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

class Solution {
    public int minDifference(int[] nums) {
        if (nums.length <= 4) {
            return 0;
        }
        
        int[] min4 = new int[4];
        int[] max4 = new int[4];
        
        Arrays.fill(min4, Integer.MAX_VALUE);
        Arrays.fill(max4, Integer.MIN_VALUE);
        
        for (int num : nums) {
            boolean added = false;
            for (int j = 0; j < min4.length; j++) {
                if (num < min4[j]) {
                    shift(min4, j);
                    min4[j] = num;
                    added = true;
                    break;
                }
            }
            if (!added && min4[min4.length - 1] == Integer.MAX_VALUE) {
                min4[min4.length - 1] = num;
            }
        }
        
        for (int num : nums) {
            boolean added = false;
            for (int j = 0; j < max4.length; j++) {
                if (num > max4[j]) {
                    shift(max4, j);
                    max4[j] = num;
                    added = true;
                    break;
                }
            }
            if (!added && max4[max4.length - 1] == Integer.MIN_VALUE) {
                max4[max4.length - 1] = num;
            }
        }
        
        int ans = max4[0] - min4[0];
        for (int i = 0; i <= 3; i++) {
            ans = Math.min(ans, max4[3 - i] - min4[i]);
        }
        return ans;
    }
    private void shift(int[] a, int start) {
        int last = a[a.length - 1];
        for (int j = a.length - 1; j > start; j--) {
            a[j] = a[j - 1];
        }
        if (a.length < 4) {
            a[a.length - 1] = last;
        }
    }
}

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(1)