medium Minimum Difference Between Largest and Smallest Value in Three Moves

Problem Statement

You are given an integer array nums. You're allowed to change any of the numbers up to three times, turning them into any value you wish.

Return the minimum difference between the largest and smallest value of nums after updating the nums array.

Examples

• Example 1:

  • Input: [1,5,6,14,15]
  • Expected Output: 1
  • Justification: Change the numbers 14 and 15 to 2 and 3, respectively (or similarly small numbers). Now, the array is [1,2,3,5,6] with a minimum difference of 5 - 1 = 4.

• Example 2:

  • Input: [10,10,10,10,10]
  • Expected Output: 0
  • Justification: All numbers are the same, so even without any moves, the difference is already 0.

• Example 3:

  • Input: [1,100,200,300,400]
  • Expected Output: 99
  • Justification: Change the three highest values to any number between 1 and 100 (inclusive). For simplicity, changing 200, 300, and 400 to 2, 3, and 4 respectively will make the array [1,2,3,4,100], with a minimum difference of 100 - 1 = 99.

Solution

To solve this problem, the most straightforward approach is to sort the array. Sorting allows us to easily identify the candidates for modification (the largest and smallest values). We aim to minimize the gap between the smallest and largest numbers with up to three changes. Intuitively, it makes sense to either elevate the smallest numbers or reduce the largest ones. However, instead of directly changing values, we can analyze the effect of such changes by considering the possible scenarios after zero to three modifications.

This approach works because the relative difference we're trying to minimize becomes clear once the array is sorted. We'll compare the potential minimum differences after no change, one change, two changes, and three changes to find the smallest possible outcome. This strategy is effective because it leverages the sorted order to minimize the range efficiently, addressing the problem's core challenge without the need for direct value manipulation.

Step-by-Step Algorithm

1. Check for Edge Case: If the array length is 4 or fewer, return 0 because we can make all elements equal by performing up to three modifications.

2. Sort the Array: Sort the array in non-decreasing order to easily identify the smallest and largest values.

3. Calculate Potential Minimum Differences: Evaluate the minimum difference possible after performing up to three modifications by considering the following scenarios:

   • Convert the three smallest elements to the fourth smallest element. This scenario removes the influence of the three smallest numbers.

   • Convert the three largest elements to the fourth largest element. This effectively removes the influence of the three largest numbers.

   • Convert the largest element to the second largest element and the two smallest elements to the third smallest element.

   • Convert the two largest elements to the third largest element and the smallest element to the second smallest element.

4. Determine the Minimum Difference: Among the differences calculated in the scenarios above, find and return the smallest one as the minimum possible difference after performing up to three moves.

Algorithm Walkthrough

Let's consider the Input: nums = [1,5,6,14,15]

1. Check for Edge Case: The array has more than 4 elements, so we proceed with the algorithm.

2. Sort the Array: The array [1,5,6,14,15] is already in non-decreasing order.

3. Calculate Potential Minimum Differences:

   • Scenario 1: Convert the three smallest elements (1, 5, 6) to the fourth smallest element (14). The new array looks like [14,14,14,14,15]. The difference is 15 - 14 = 1.
   • Scenario 2: Convert the three largest elements (6, 14, 15) to the fourth largest element (5). The new array looks like [1,5,5,5,5]. The difference is 5 - 1 = 4.
   • Scenario 3: Convert the largest element (15) to the second largest element (14), and the two smallest elements (1, 5) to the third smallest element (6). The new array looks like [6,6,6,14,14]. The difference is 14 - 6 = 8.
   • Scenario 4: Convert the two largest elements (14, 15) to the third largest element (6), and the smallest element (1) to the second smallest element (5). The new array looks like [5,5,6,6,6]. The difference is 6 - 5 = 1.

4. Determine the Minimum Difference: The smallest difference among the calculated scenarios is 1.

Code

import java.util.Arrays;

public class Solution {

  public int minDifference(int[] nums) {
    // Edge case: If array has 4 or fewer elements, no difference can be made
    if (nums.length <= 4) return 0;
    Arrays.sort(nums); // Sort the array
    int n = nums.length;
    // Compare the potential minimum differences after 0 to 3 changes
    return Math.min(
      Math.min(nums[n - 1] - nums[3], nums[n - 4] - nums[0]),
      Math.min(nums[n - 2] - nums[2], nums[n - 3] - nums[1])
    );
  }

  public static void main(String[] args) {
    Solution solution = new Solution();
    // Example 1
    System.out.println(solution.minDifference(new int[] { 1, 5, 6, 14, 15 })); // Output: 4
    // Example 2
    System.out.println(
      solution.minDifference(new int[] { 10, 10, 10, 10, 10 })
    ); // Output: 0
    // Example 3
    System.out.println(
      solution.minDifference(new int[] { 1, 100, 200, 300, 400 })
    ); // Output: 99
  }
}

Complexity Analysis

Time Complexity

The primary operation in the algorithm is sorting the input array, which, for an array of length n, has a time complexity of in the average and worst cases. After sorting, the algorithm performs a constant number of operations to determine the minimum difference, resulting in a constant time complexity of . Therefore, the overall time complexity of the algorithm is dominated by the sorting step, making it .

Space Complexity

The space complexity of the algorithm is as the algorithm sorts the input array.