Sponsored
The idea is to sort the array and find the minimal difference after removing at most three elements from either side. By sorting the array, you can easily identify the largest and smallest values that might stay in the array. After sorting, the array becomes an ordered sequence, allowing you to attempt minimizing differences by changing elements from the edges.
This approach essentially checks the possible combinations of keeping n - 3 elements and removing the smallest, or the largest, or a mix of both.
Time Complexity: O(n log n) due to sorting. Space Complexity: O(1) since the sorting is in-place.
1using System;
2
3public class MinDifferenceSolution {
4 public int MinDifference(int[] nums) {
5 if (nums.Length <= 4) return 0;
6 Array.Sort(nums);
7 return Math.Min(
8 Math.Min(nums[nums.Length - 1] - nums[3], nums[nums.Length - 2] - nums[2]),
9 Math.Min(nums[nums.Length - 3] - nums[1], nums[nums.Length - 4] - nums[0])
10 );
11 }
12
13 public static void Main() {
14 int[] nums1 = {5, 3, 2, 4};
int[] nums2 = {1, 5, 0, 10, 14};
int[] nums3 = {3, 100, 20};
MinDifferenceSolution solution = new MinDifferenceSolution();
Console.WriteLine(solution.MinDifference(nums1)); // Output: 0
Console.WriteLine(solution.MinDifference(nums2)); // Output: 1
Console.WriteLine(solution.MinDifference(nums3)); // Output: 0
}
}The C# solution performs sorting using the built-in Array.Sort method. It then checks the minimum difference for the same four scenarios as explored in other languages, providing the optimized outcome.