DDSA Solutions

2567. Minimum Score by Changing Two Elements

Time: O(n)
Space: O(1)

Problem Overview

The score is the sum of the smallest and largest pairwise absolute differences.

Intuition

The score is the sum of the smallest and largest pairwise absolute differences. With two free changes you can always copy an existing value and force the low score to 0, so the problem reduces to minimizing the high score. After ordering the values, the useful moves are to discard the two smallest entries, the two largest, or one from each end. That means only the three smallest and three largest matter, and a single linear pass that tracks those six order statistics is enough.

Algorithm

  1. 1Scan the array once while keeping the three smallest values a, b, c and the three largest values x, y, z.
  2. 2Candidate high scores are x minus c, z minus a, and y minus b.
  3. 3Return the minimum of those three candidates.

Example Walkthrough

Input: nums = [1, 4, 3, 7, 4, 1, 1]

  1. 1.The three smallest are 1, 1, 1 and the three largest are 7, 4, 4.
  2. 2.Dropping two mins gives high 6, dropping two maxes gives 3, and dropping one of each also gives 3.
  3. 3.The minimum high score is 3, and the low score can be made 0, so the answer is 3.

Output: 3

Common Pitfalls

  • •Do not add the low score after the changes. It can always be driven to 0 with a duplicate.
  • •A full sort works but is unnecessary. Only six extreme values are required.
  • •When n equals 3, discarding two extremes leaves a single value and the high score becomes 0.
  • •Track multiplicity carefully. Repeated equal values still occupy distinct slots among the three extremes.
2567.cs
C#
// Approach: Two changes can always make the low score 0 by duplicating a value,
// so minimize the high score. After identifying order statistics, the three
// options are remove the two smallest, the two largest, or one of each. Only
// the three smallest and three largest values are needed, found in one pass.
// Time: O(n) Space: O(1)

public class Solution
{
    public int MinimizeSum(int[] nums)
    {
        int a = int.MaxValue, b = int.MaxValue, c = int.MaxValue;
        int x = int.MinValue, y = int.MinValue, z = int.MinValue;

        foreach (int v in nums)
        {
            if (v <= a) { c = b; b = a; a = v; }
            else if (v <= b) { c = b; b = v; }
            else if (v < c) c = v;

            if (v >= x) { z = y; y = x; x = v; }
            else if (v >= y) { z = y; y = v; }
            else if (v > z) z = v;
        }

        return Math.Min(x - c, Math.Min(z - a, y - b));
    }
}
Was this solution helpful?

Related Problems