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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Score by Changing Two Elements

Number: 2706

Difficulty: Medium

Paid? No

Companies: N/A

Problem Description

Given an integer array nums, you are allowed to change exactly two elements to any value. The score of the array is defined as the sum of:

  • The low score: the minimum absolute difference between any two integers in nums.
  • The high score: the maximum absolute difference between any two integers in nums. Return the minimum possible score after performing exactly two changes.

Key Insights

  • Sorting the array lets you quickly access the extreme (smallest and largest) values.
  • With two changes, you can adjust the “extremes” by either: • Changing the two smallest elements, • Changing the two largest elements, or • Changing one smallest and one largest.
  • In each scenario, the low score can be forced to 0 (by duplicating a value) so the overall score is determined by the range (high score) of the remaining elements.
  • Thus, after sorting, consider three candidate strategies: • Option 1: Set the two smallest equal to the third smallest, making the new minimum nums[2]. The score is nums[n-1] - nums[2]. • Option 2: Set the two largest equal to the third largest, making the new maximum nums[n-3]. The score is nums[n-3] - nums[0]. • Option 3: Change one smallest and one largest so that the new extremes become nums[1] and nums[n-2]. The score is nums[n-2] - nums[1].

Space and Time Complexity

Time Complexity: O(n log n) due to sorting.
Space Complexity: O(n) (or O(1) if sorting is done in-place).

Solution

Sort the array to determine the order of elements and evaluate three scenarios corresponding to which two elements are changed. For each:

  1. When changing the two smallest, the new minimum becomes the third smallest element.
  2. When changing the two largest, the new maximum becomes the third largest element.
  3. When changing one smallest and one largest, the new extremes become the second smallest and second largest. Since the low score can be forced to 0 by making duplicate values, the overall score is the difference between the resulting maximum and minimum. The final answer is the minimum score among these three computed ranges.

Code Solutions

# Python solution for Minimum Score by Changing Two Elements

def minimumScore(nums):
    # Sort the array to access extreme values
    nums.sort()
    n = len(nums)
    
    # Option 1: Change the two smallest elements.
    # New minimum becomes nums[2] while the maximum remains unchanged.
    option1 = nums[n - 1] - nums[2]
    
    # Option 2: Change the two largest elements.
    # New maximum becomes nums[n - 3] while the minimum remains unchanged.
    option2 = nums[n - 3] - nums[0]
    
    # Option 3: Change the smallest and the largest element.
    # New range becomes from nums[1] to nums[n - 2].
    option3 = nums[n - 2] - nums[1]
    
    # The final answer is the minimum score among these options.
    return min(option1, option2, option3)

# Example usage:
print(minimumScore([1, 4, 7, 8, 5]))  # Expected Output: 3
print(minimumScore([1, 4, 3]))         # Expected Output: 0
← Back to All Questions