LeetCode 2567 - Minimum Score by Changing Two Elements

The problem asks us to manipulate an array of integers, nums, in a very specific way to minimize a metric called the "score.

leetcodemediumarraygreedysorting

LeetCode Problem 2567

Difficulty: 🟡 Medium
Topics: Array, Greedy, Sorting

Solution

Problem Understanding

The problem asks us to manipulate an array of integers, nums, in a very specific way to minimize a metric called the "score." The score is defined as the sum of two quantities: the high score, which is the maximum absolute difference between any two elements in the array, and the low score, which is the minimum absolute difference between any two elements. The twist is that we are allowed to change up to two elements of the array to any values we choose in order to minimize this score.

In other words, given an array of length n, we want to find two elements to change such that, after those changes, the difference between the largest and smallest numbers (high score) and the smallest difference between any two numbers (low score) together sum to the smallest possible value.

The constraints tell us the input size can be quite large (3 <= nums.length <= 10^5) and that array values are positive integers up to 10^9. This means that a brute-force approach that examines every possible pair of changes is not feasible, as it would require combinatorial time.

Key edge cases include arrays that are already nearly uniform, arrays where the minimum or maximum element is repeated, or arrays of length exactly three, since any two elements can be changed to make all values equal.

Approaches

The brute-force approach would involve trying every possible combination of changing two elements to any integer values, and then computing the resulting score. This guarantees correctness but is computationally infeasible because the number of combinations grows quadratically and the range of values is extremely large (1 to 10^9).

The optimal approach leverages the insight that the maximum and minimum elements largely determine the high score, and the largest gaps between sorted elements determine the low score. By sorting the array, we can focus only on the boundary elements. Specifically, to minimize the score after two changes, we only need to consider three main strategies:

  1. Change the two largest elements to match the smaller ones.
  2. Change the two smallest elements to match the larger ones.
  3. Change the smallest and largest elements, leaving the middle intact.

Sorting the array allows us to examine only a few candidate high score scenarios without iterating over every possible pair of changes.

Approach Time Complexity Space Complexity Notes
Brute Force O(n^2 * n) O(1) Try all pairs of elements to change; compute min and max differences; too slow for n=10^5
Optimal O(n log n) O(1) Sort array; consider boundary elements only; check three key cases for minimal score

Algorithm Walkthrough

  1. Sort the array. Sorting allows us to consider the smallest and largest elements efficiently. Let the sorted array be nums_sorted.
  2. Identify key candidates. After sorting, the candidates for minimal high score after two changes involve the extreme elements:
  • Change the two largest elements to reduce the maximum difference.
  • Change the two smallest elements to reduce the maximum difference.
  • Change the smallest and largest element in a mixed way to balance the difference.
  1. Compute candidate scores. For a sorted array [a0, a1, ..., an-1], the possible minimized high scores after changing two elements are:
  • nums[n-3] - nums[0] (change two largest elements)
  • nums[n-1] - nums[2] (change two smallest elements)
  • nums[n-2] - nums[1] (change one smallest and one largest element)
  1. Return the minimum of these candidates. The minimal possible high score dominates the low score because the minimum absolute difference can always be reduced to zero by choosing appropriate values for the changed elements.

Why it works: By focusing on sorted boundary elements, we account for all situations that affect the maximum difference. The problem allows arbitrary value assignment, so we can always reduce the minimum difference to zero with two changes, and the high score is bounded by the remaining boundary elements.

Python Solution

from typing import List

class Solution:
    def minimizeSum(self, nums: List[int]) -> int:
        n = len(nums)
        if n <= 3:
            return 0  # Can always make all elements equal
        
        nums.sort()
        # Three strategies: change two largest, change two smallest, change smallest+largest
        option1 = nums[-3] - nums[0]  # change two largest
        option2 = nums[-1] - nums[2]  # change two smallest
        option3 = nums[-2] - nums[1]  # change one smallest, one largest
        
        return min(option1, option2, option3)

The implementation first handles the edge case of n <= 3, where we can trivially set all elements equal to achieve zero score. Sorting the array simplifies identifying the largest and smallest elements. Then, three possible minimal high scores are computed based on boundary manipulation, and the minimum is returned as the answer.

Go Solution

import "sort"

func minimizeSum(nums []int) int {
    n := len(nums)
    if n <= 3 {
        return 0
    }
    
    sort.Ints(nums)
    
    option1 := nums[n-3] - nums[0] // change two largest
    option2 := nums[n-1] - nums[2] // change two smallest
    option3 := nums[n-2] - nums[1] // change one smallest and one largest
    
    min := option1
    if option2 < min {
        min = option2
    }
    if option3 < min {
        min = option3
    }
    
    return min
}

In Go, sorting is done using sort.Ints. The edge case for small arrays is handled first. The three candidate high scores are calculated and compared manually, as Go lacks a built-in min for multiple integers.

Worked Examples

Example 1: nums = [1, 4, 7, 8, 5]

  1. Sort: [1, 4, 5, 7, 8]
  2. Candidates:
  • nums[-3] - nums[0] = 5 - 1 = 4
  • nums[-1] - nums[2] = 8 - 5 = 3
  • nums[-2] - nums[1] = 7 - 4 = 3
  1. Minimum score = 3

Example 2: nums = [1, 4, 3]

  1. Length ≤ 3 → return 0 directly.

Complexity Analysis

Measure Complexity Explanation
Time O(n log n) Sorting dominates; all other operations are O(1)
Space O(1) Sorting can be done in place; only constant extra space is needed

Sorting is required to identify the boundary elements efficiently, and the problem constraints make O(n log n) acceptable for n up to 10^5.

Test Cases

# Provided examples
assert Solution().minimizeSum([1,4,7,8,5]) == 3  # Example 1
assert Solution().minimizeSum([1,4,3]) == 0      # Example 2

# Edge cases
assert Solution().minimizeSum([1,1,1,1]) == 0    # All equal
assert Solution().minimizeSum([1,100,200]) == 0  # Length 3, can make equal
assert Solution().minimizeSum([1,2,3,4]) == 1    # Small array
assert Solution().minimizeSum([1,2,3,1000]) == 2 # Change extremes
Test Why
[1,4,7,8,5] Standard case with multiple options
[1,4,3] Small array, can reduce to zero
[1,1,1,1] Already uniform, score zero
[1,100,200] Length 3, trivial zero score
[1,2,3,4] Minimal high score after two changes
[1,2,3,1000] Large gap to test boundary changes

Edge Cases

Edge Case 1: Small arrays. When n <= 3, any array can be made uniform by changing two elements, resulting in a score of 0. This is handled explicitly at the beginning of the algorithm.

Edge Case 2: Already uniform array. If all elements are equal, the score is already zero. The algorithm correctly computes candidates as zero or less, returning zero.

Edge Case 3: Large maximum difference. Arrays where one element is extremely larger than the others could cause naive solutions to miscalculate the optimal two elements to change. By sorting and focusing on the first three and last three elements, the algorithm always captures the optimal change scenario.

Edge Case 4: Arrays with consecutive duplicates. The minimum absolute difference could initially be zero, but two changes may shift boundaries. Sorting and considering only boundary differences ensures the low score can always be minimized.