Scale Engineer

Minimum Score by Changing Two Elements

Med
#2347Time: O(N log N), dominated by the sorting algorithm.Space: O(log N) or O(N), depending on the space used by the sorting algorithm. In Java, `Arrays.sort` for primitives has an average space complexity of O(log N).
Patterns
Greedy
Algorithms
Sorting
Data structures
Array

Prompt

You are given an integer array nums.

  • The low score of nums is the minimum absolute difference between any two integers.
  • The high score of nums is the maximum absolute difference between any two integers.
  • The score of nums is the sum of the high and low scores.

Return the minimum score after changing two elements of nums.

 

Example 1:

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

Output: 3

Explanation:

  • Change nums[0] and nums[1] to be 6 so that nums becomes [6,6,7,8,5].
  • The low score is the minimum absolute difference: |6 - 6| = 0.
  • The high score is the maximum absolute difference: |8 - 5| = 3.
  • The sum of high and low score is 3.

Example 2:

Input: nums = [1,4,3]

Output: 0

Explanation:

  • Change nums[1] and nums[2] to 1 so that nums becomes [1,1,1].
  • The sum of maximum absolute difference and minimum absolute difference is 0.

 

Constraints:

  • 3 <= nums.length <= 105
  • 1 <= nums[i] <= 109

Approaches

3 approaches with complexity analysis and trade-offs.

A significantly more efficient approach involves sorting the array first. To minimize the difference between the maximum and minimum elements, we must alter the current extremes. After sorting, the smallest and largest elements are easy to identify. We only need to consider three strategic choices for which two elements to change: the two smallest, the two largest, or the single smallest and single largest.

Algorithm

  • Sort the input array nums.
  • Let n be the length of the array.
  • If n <= 3, return 0.
  • Calculate three potential scores:
    • score1 = nums[n-1] - nums[2] (changing the two smallest).
    • score2 = nums[n-3] - nums[0] (changing the two largest).
    • score3 = nums[n-2] - nums[1] (changing one smallest, one largest).
  • Return the minimum of score1, score2, and score3.

Walkthrough

The key insight is that the high score is determined by max(nums) - min(nums). To reduce this gap, we must change either the minimum element, the maximum element, or both. With two changes available, we have a few powerful options:

  1. Change the two smallest elements: By sorting the array, these are nums[0] and nums[1]. We can change them to match nums[2]. The new minimum becomes nums[2], and the maximum remains nums[n-1]. The new high score is nums[n-1] - nums[2].
  2. Change the two largest elements: These are nums[n-1] and nums[n-2]. We change them to match nums[n-3]. The new maximum becomes nums[n-3], and the minimum remains nums[0]. The new high score is nums[n-3] - nums[0].
  3. Change the smallest and the largest element: These are nums[0] and nums[n-1]. We change nums[0] to nums[1] and nums[n-1] to nums[n-2]. The new range is from nums[1] to nums[n-2]. The new high score is nums[n-2] - nums[1].

The minimum of these three resulting scores is our answer. As in the previous approach, the low score can be made 0 in each case.

import java.util.Arrays; class Solution {    public int minimizeSum(int[] nums) {        int n = nums.length;        if (n <= 3) {            return 0;        }         Arrays.sort(nums);         // Case 1: Change the two smallest elements.        // New range: nums[2] to nums[n-1]        int score1 = nums[n - 1] - nums[2];         // Case 2: Change the two largest elements.        // New range: nums[0] to nums[n-3]        int score2 = nums[n - 3] - nums[0];         // Case 3: Change the smallest and the largest element.        // New range: nums[1] to nums[n-2]        int score3 = nums[n - 2] - nums[1];         return Math.min(score1, Math.min(score2, score3));    }}

Complexity

Time

O(N log N), dominated by the sorting algorithm.

Space

O(log N) or O(N), depending on the space used by the sorting algorithm. In Java, `Arrays.sort` for primitives has an average space complexity of O(log N).

Trade-offs

Pros

  • Much more efficient than the brute-force approach.

  • The logic is clear and relatively easy to implement once the core idea is understood.

Cons

  • The O(N log N) time complexity is not optimal, as sorting the entire array is more work than necessary.

Solutions

class Solution {public  int minimizeSum(int[] nums) {    Arrays.sort(nums);    int n = nums.length;    int a = nums[n - 1] - nums[2];    int b = nums[n - 2] - nums[1];    int c = nums[n - 3] - nums[0];    return Math.min(a, Math.min(b, c));  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem