We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Minimum Difference Between Largest and Smallest Value in Three Moves

Difficulty: Medium

Problem Description

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.

Key Insights

  • You can perform up to three moves to change elements in the array.
  • The goal is to minimize the difference between the maximum and minimum values of the array after the moves.
  • Sorting the array helps identify potential candidates for the maximum and minimum values after modifications.
  • The minimum difference can be achieved by either increasing the smallest values or decreasing the largest values.

Space and Time Complexity

Time Complexity: O(n log n) - due to sorting the array.
Space Complexity: O(1) - only a constant amount of extra space is used.

Solution

To solve this problem, we can follow these steps:

  1. Sort the given array nums.
  2. Calculate the potential minimum differences by considering the smallest and largest elements that can be adjusted after up to three moves.
  3. The possible scenarios involve changing up to three smallest elements or three largest elements, and we need to compute the differences accordingly.
  4. The minimum of these differences will be our answer.

Code Solutions

def minDifference(nums):
    # Edge case: If the array has 4 or fewer elements, we can make them all equal.
    if len(nums) <= 4:
        return 0
    
    # Sort the array
    nums.sort()
    
    # Calculate the minimum difference after 3 moves
    return min(
        nums[-1] - nums[3],  # Remove the 3 smallest elements
        nums[-2] - nums[2],  # Remove the 2 smallest and 1 largest
        nums[-3] - nums[1],  # Remove the 1 smallest and 2 largest
        nums[-4] - nums[0]   # Remove the 3 largest elements
    )
← Back to All Questions