Leetcode 1509. Minimum Difference Between Largest and Smallest Value in Three Moves

Problem Explanation

We are given an array of integers and we are allowed to change up to 3 elements of this array. Our goal is to find the minimum difference between the largest and smallest value in the array after we perform these moves.

Our strategy will be to replace the three largest numbers and the three smallest numbers, and check all possible combinations.

The reason is that, in general, we want the minimum and maximum to be as close as possible, and we should attempt to decrease the maximum or increase the minimum to achieve this.

However, we don't only decrease the maximum or increase the minimum, because in some cases, the second smallest/largest number can already be very close to the maximum/minimum, and we would rather modify other numbers to achieve a smaller difference.

Therefore, our problem can be reduced to find the minimum difference between the fourth largest number and the first smallest number, the third largest and the second smallest, the second largest and the third smallest, and the first largest and the fourth smallest.

Let's walk through an example.

Expression:

1
2
3nums = [6,6,0,1,1,4,6]

1. We sort the array, which becomes [0, 1, 1, 4, 6, 6, 6].
2. We calculate the differences:
   • nums[3] - nums[0] = 4
   • nums[4] - nums[1] = 5
   • nums[5] - nums[2] = 5
   • nums[6] - nums[3] = 2
3. The minimum difference is 2.

We will now solve this problem in Python, Java, JavaScript, C++, and C#.

Python Solution

1
2python
3class Solution:
4    def minDifference(self, nums):
5        if len(nums) <= 4: # if array has less than 4 elements, we can turn them all equal
6            return 0
7        nums.sort() # sort the array
8        return min(b - a for a, b in zip(nums[:4], nums[-4:])) # check all possible combinations and return the smallest difference

Java Solution

1
2java
3import java.util.Arrays;
4
5public class Solution {
6    public int minDifference(int[] nums) {
7        if (nums.length <= 4) {
8            return 0;
9        }
10        Arrays.sort(nums);
11        int minDifference = Integer.MAX_VALUE;
12        for (int i = 0; i < 4; i++) {
13            minDifference = Math.min(minDifference, nums[nums.length - 4 + i] - nums[i]);
14        }
15        return minDifference;
16    }
17}

JavaScript Solution

1
2javascript
3class Solution {
4    minDifference(nums) {
5        if (nums.length <= 4) {
6            return 0;
7        }
8        nums.sort((a, b) => a - b);
9        let minDifference = Number.MAX_SAFE_INTEGER;
10        for (let i = 0; i < 4; i++) {
11            minDifference = Math.min(minDifference, nums[nums.length - 4 + i] - nums[i]);
12        }
13        return minDifference;
14    }
15}
16

C++ Solution

1
2cpp
3#include <algorithm>
4#include <vector>
5
6class Solution {
7public:
8    int minDifference(std::vector<int>& nums) {
9        if (nums.size() <= 4) {
10            return 0;
11        }
12        std::sort(nums.begin(), nums.end());
13        int minDifference = INT_MAX;
14        for (int i = 0; i < 4; i++) {
15            minDifference = std::min(minDifference, nums[nums.size() - 4 + i] - nums[i]);
16        }
17        return minDifference;
18    }
19};

C# Solution

1
2csharp
3using System;
4using System.Linq;
5
6public class Solution {
7    public int MinDifference(int[] nums) {
8        if (nums.Length <= 4) {
9            return 0;
10        }
11        Array.Sort(nums);
12        int minDifference = Int32.MaxValue;
13        for (int i = 0; i < 4; i++) {
14            minDifference = Math.Min(minDifference, nums[nums.Length - 4 + i] - nums[i]);
15        }
16        return minDifference;
17    }
18}

Each of the above solutions uses the approach outlined in the walkthrough. First, we check if the array has four or fewer elements. If it does, we return 0 since we can change all elements to be equal in less than three moves.

We then sort the array in ascending order. Afterwards, we calculate the difference between the largest and smallest numbers for each set of numbers (the fourth largest and the first smallest, the third largest and the second smallest, the second largest and the third smallest, and the first largest and the fourth smallest).

Finally, we return the minimum difference based on all the calculated differences.This approach results in a time complexity of O(n log n) due to the sorting operation, where n is the size of the input array. The space complexity is O(1) since we don't use any additional data structures for our calculations.

In conclusion, replacing the three largest and the three smallest numbers in the array allows us to reduce the spread of numbers. By doing so, we can decrease the difference between the maximum and minimum values in the array.

The provided solutions across different languages of Python, Java, JavaScript, C++, and C# utilize this concept by sorting the array and taking the differences between the fourth-largest and smallest numbers, down to the largest and fourth-smallest numbers. Through careful observation and walking through the given example, we were able to devise a theoretically sound approach to our problem. The implemented code demonstrates the effectiveness of this solution and does so in a manner that's easy to understand and follow.

Note: Although the solutions provided here involve sorting the array, a more optimized approach would be to use a priority queue (heap) to find the three largest and three smallest elements. This would reduce the time complexity to O(n log 3), which could potentially provide a more efficient solution for larger inputs. However, for simplicity and clarity, we focused on the sorting-based solution in this guide. For both these approaches, always use the most appropriate one depending on the specific constraints of your application.

In the end, understanding the question and walking through some examples is essential for decoding the problem and finding the most efficient way possible to solve it. The elegance of these solutions lies in the simplicity of the consideration of a few specific elements rather than the entire array to solve a seemingly complex problem.