Skip to main content
Talentd

Minimum Score by Changing Two Elements - Solution & Explanation

MediumArrayGreedySorting18 min read
Practice this problem

Problem Statement

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

Approach Overview

Problem Overview: You are given an integer array nums. You may change the value of any two elements to any number. The goal is to minimize the array's score, defined as the difference between the maximum and minimum element after the changes.

Approach 1: Greedy Approach by Sorting (O(n log n) time, O(1) extra space)

The key observation: changing two elements is equivalent to removing two extreme values that create the largest range. After sorting the array, only three meaningful scenarios exist. You either modify the two largest numbers, the two smallest numbers, or one smallest and one largest. After sorting, compute the score for these three possibilities: nums[n-3] - nums[0], nums[n-2] - nums[1], and nums[n-1] - nums[2]. The smallest of these values is the answer. Sorting exposes the boundary values so you can evaluate these cases directly without brute force. This pattern commonly appears in greedy problems involving extreme elements.

Approach 2: Sliding Window Technique (O(n log n) time, O(1) space)

After sorting the array, keep n-2 elements unchanged and treat the other two as the ones you modify. This converts the problem into finding the smallest range among all windows of length n-2. Slide a window across the sorted array and compute the difference between the last and first element of each window. Only three windows exist because the array size shrinks by two. The minimum difference across these windows gives the optimal score. This interpretation highlights how sorting combined with a window over the array simplifies range problems, a common pattern in array and sorting questions.

Recommended for interviews: The greedy sorting approach is what interviewers typically expect. It shows you recognize that modifying elements effectively removes extremes. A brute force attempt would try all modification combinations, which quickly becomes impractical. Identifying the three boundary cases after sorting demonstrates strong problem reduction and greedy reasoning.

Approach 1: Greedy Approach by Sorting

Sort the array. Consider changing two of the smallest or largest numbers to the other extreme. This could minimize the effect on the high and low scores.

The key here is to sort the array and then try to either increase the smallest two, decrease the largest two, or a combination of these to minimize the score.

We sort the array and calculate possible scores by removing two numbers using the available formulas. Return the minimum of all possible options.

Code

PythonJavaC++CC#JavaScript

Python

Java

C++

C

C#

JavaScript

Complexity

Time Complexity: O(n log n) due to sorting. Space Complexity: O(1) as it modifies the input array in-place.

Try this approach in the editor →

Approach 2: Sliding Window Technique

Given the sorted array, whenever you want to make minimal changes, a sliding window of potential element selections can ensure the low score is zero while reducing the high score.

This solution leverages a simplified sliding window, minimizing adjustments, allowing contiguous elements to yield small high scores.

Code

PythonJavaC++CC#JavaScript

Python

Java

C++

C

C#

JavaScript

Complexity

Time Complexity is O(n log n) because of sorting, Space Complexity is O(1).

Try this approach in the editor →

Approach 3: Sorting + Greedy

From the problem description, we know that the minimum score is actually the minimum difference between two adjacent elements in the sorted array, and the maximum score is the difference between the first and last elements of the sorted array. The score of the array nums is the sum of the minimum score and the maximum score.

Therefore, we can first sort the array. Since the problem allows us to modify the values of at most two elements in the array, we can modify a number to make it the same as another number in the array, making the minimum score 0. In this case, the score of the array nums is actually the maximum score. We can choose to make one of the following modifications:

Modify the smallest two numbers to nums[2], then the maximum score is nums[n - 1] - nums[2]; Modify the smallest number to nums[1] and the largest number to nums[n - 2], then the maximum score is nums[n - 2] - nums[1]; Modify the largest two numbers to nums[n - 3], then the maximum score is nums[n - 3] - nums[0]. Finally, we return the minimum score of the above three modifications.

The time complexity is O(n log n), and the space complexity is O(log n). Here, n is the length of the array nums.

Similar problems:

-1509. Minimum Difference Between Largest and Smallest Value in Three Moves

Code

PythonJavaC++GoTypeScriptRustC

Python

Java

C++

Go

TypeScript

Rust

C

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Greedy Approach by Sorting

Time Complexity: O(n log n) due to sorting. Space Complexity: O(1) as it modifies the input array in-place.

Sliding Window Technique

Time Complexity is O(n log n) because of sorting, Space Complexity is O(1).

Sorting + Greedy—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Greedy by SortingO(n log n)O(1)Standard solution. Sorting reveals extreme values so the three optimal cases can be checked directly.
Sliding Window on Sorted ArrayO(n log n)O(1)Useful when reasoning about keeping n-2 elements unchanged and minimizing the range of a fixed window.

Video Solution

B. Minimum Score by Changing Two Elements - LEETCODE BIWEEKLY CONTEST 98 (Detailed Logic explained) • Joyjit Codes • 907 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Minimum Score by Changing Two Elements easy or hard?
The problem is classified as Medium on LeetCode. The challenge is recognizing that changing two elements effectively removes two extremes that expand the range. Once that insight is clear, the implementation becomes straightforward after sorting.
Minimum Score by Changing Two Elements Python/Java solution
In Python or Java, sort the array first, then compute the minimum among three expressions: nums[n-3] - nums[0], nums[n-2] - nums[1], and nums[n-1] - nums[2]. The same logic works across languages including C++, C#, and JavaScript because it only depends on sorting and index access.
How to solve Minimum Score by Changing Two Elements in O(n)?
A strict O(n) solution is generally not used because identifying extreme ordering without sorting is harder than necessary. Sorting the array in O(n log n) already provides a simple and reliable solution. Once sorted, evaluating the three candidate ranges takes constant time.
What is the best approach for Minimum Score by Changing Two Elements?
The best approach sorts the array and checks three possible scenarios: remove the two largest elements, remove the two smallest elements, or remove one from each side. After sorting, compute nums[n-3] - nums[0], nums[n-2] - nums[1], and nums[n-1] - nums[2]. The minimum of these values is the optimal score. The time complexity is O(n log n) due to sorting and O(1) extra space.
Is Minimum Score by Changing Two Elements asked at Google/Amazon/Meta?
Problems that involve minimizing ranges by modifying elements appear frequently in interviews at companies like Amazon, Google, and Meta. The specific LeetCode problem may vary, but the greedy insight of removing extreme values after sorting is a common interview pattern.
What data structure is used in Minimum Score by Changing Two Elements?
The solution primarily relies on arrays and sorting. After sorting, simple index access retrieves the smallest and largest elements needed to evaluate the three possible scenarios. No additional complex data structures are required.
What is the time complexity of Minimum Score by Changing Two Elements?
The optimal solution runs in O(n log n) time because the array must be sorted first. After sorting, only three constant-time comparisons are required to evaluate the possible ranges. Space complexity is O(1) if sorting is done in place.

Ready to solve this problem?

Practice Minimum Score by Changing Two Elements with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays