Minimum Score by Changing Two Elements solution and explanation
9 more videos on this problem
B. Minimum Score by Changing Two Elements - LEETCODE BIWEEKLY CONTEST 98 (Detailed Logic explained)Joyjit Codes · 3:48 · 907 views
Minimum Score by Changing Two Elements || Leetcode-2567 || C++Aryan Mittal · 11:02 · 758 views
Minimum Score by Changing Two Elements || leetcode Biweekly 98 || Leetcode MediumBinaryMagic · 12:21 · 728 views
Leetcode Biweekly Contest 98 | 2567: Minimum Score By Changing Two Elements Solution | Newton SchoolCoding Community | Newton School · 9:38 · 539 views
2567. Minimum Score by Changing Two Elements | LeetCode MediumDeep Tech · 7:44 · 517 views
B. minimum score by changing two elements - leetcode Biweekly contest 98 problem 6361Code With U-DAY · 7:05 · 486 views
2567. Minimum Score by Changing Two Elements (Leetcode Medium)Programming Live with Larry · 7:43 · 234 views
【每日一题】LeetCode 2567. Minimum Score by Changing Two ElementsHuifeng Guan · 7:25 · 196 views
2567. Minimum Score by Changing Two Elements - Bi-Weekly Contest 98 (Explanation + Code)Sourin Majumdar · 14:38 · 150 views
Minimum Score by Changing Two Elements | Leetcode 2567 | BiWeekly 98Tech Courses · 5:51 · 130 views
The problem
You are given an integer array nums.
- The low score of
numsis the minimum absolute difference between any two integers. - The high score of
numsis the maximum absolute difference between any two integers. - The score of
numsis 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]andnums[1]to be 6 so thatnumsbecomes [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]andnums[2]to 1 so thatnumsbecomes [1,1,1]. - The sum of maximum absolute difference and minimum absolute difference is 0.
Constraints:
3 <= nums.length <= 1051 <= 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.
def min_score(nums):
nums.sort()
n = len(nums)
if n < 4:
return 0
return min(
nums[n-1] - nums[2], # Removing two smallest numbers
nums[n-2] - nums[1], # Removing one from each side
nums[n-3] - nums[0]
)import java.util.Arrays;
public class Solution {
public int minScore(int[] nums) {
Arrays.sort(nums);
int n = nums.length;
if (n < 4) return 0;
return Math.min(
nums[n-1] - nums[2],
Math.min(nums[n-2] - nums[1],
nums[n-3] - nums[0])
);
}
}#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
int minScore(vector<int>& nums) {
sort(nums.begin(), nums.end());
int n = nums.size();
if (n < 4) return 0;
return min({
nums[n-1] - nums[2],
nums[n-2] - nums[1],
nums[n-3] - nums[0]
});
}
};function minScore(nums) {
nums.sort((a, b) => a - b);
const n = nums.length;
if (n < 4) return 0;
return Math.min(
nums[n - 1] - nums[2],
nums[n - 2] - nums[1],
nums[n - 3] - nums[0]
);
}#include <stdio.h>
#include <stdlib.h>
int compare(const void *a, const void *b) {
return (*(int*)a - *(int*)b);
}
int minScore(int* nums, int numsSize) {
qsort(nums, numsSize, sizeof(int), compare);
if (numsSize < 4) return 0;
int score1 = nums[numsSize-1] - nums[2];
int score2 = nums[numsSize-2] - nums[1];
int score3 = nums[numsSize-3] - nums[0];
return score1 < score2 ? (score1 < score3 ? score1 : score3) : (score2 < score3 ? score2 : score3);
}using System;
public class Solution {
public int MinScore(int[] nums) {
Array.Sort(nums);
int n = nums.Length;
if (n < 4) return 0;
return Math.Min(Math.Min(nums[n-1] - nums[2],
nums[n-2] - nums[1]),
nums[n-3] - nums[0]);
}
}We sort the array and calculate possible scores by removing two numbers using the available formulas. Return the minimum of all possible options.
Time Complexity: O(n log n) due to sorting. Space Complexity: O(1) as it modifies the input array in-place.
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.
def min_score(nums):
nums.sort()
n = len(nums)
if n <= 4:
return 0
return min(nums[n-4] - nums[0], nums[n-1] - nums[3])import java.util.Arrays;
public class Solution {
public int minScore(int[] nums) {
Arrays.sort(nums);
int n = nums.length;
if (n <= 4) return 0;
return Math.min(nums[n-4] - nums[0], nums[n-1] - nums[3]);
}
}#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
int minScore(vector<int>& nums) {
sort(nums.begin(), nums.end());
int n = nums.size();
if (n <= 4) return 0;
return min(nums[n-4] - nums[0], nums[n-1] - nums[3]);
}
};function minScore(nums) {
nums.sort((a, b) => a - b);
const n = nums.length;
if (n <= 4) return 0;
return Math.min(nums[n - 4] - nums[0], nums[n - 1] - nums[3]);
}#include<stdio.h>
#include<stdlib.h>
int compare(const void *a, const void *b) {
return (*(int*)a - *(int*)b);
}
int minScore(int* nums, int numsSize) {
qsort(nums, numsSize, sizeof(int), compare);
if (numsSize <= 4) return 0;
int score1 = nums[numsSize - 4] - nums[0];
int score2 = nums[numsSize - 1] - nums[3];
return score1 < score2 ? score1 : score2;
}using System;
public class Solution {
public int MinScore(int[] nums) {
Array.Sort(nums);
int n = nums.Length;
if (n <= 4) return 0;
return Math.Min(nums[n-4] - nums[0], nums[n-1] - nums[3]);
}
}This solution leverages a simplified sliding window, minimizing adjustments, allowing contiguous elements to yield small high scores.
Time Complexity is O(n log n) because of sorting, Space Complexity is O(1).
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
function minimizeSum(nums: number[]): number {
nums.sort((a, b) => a - b);
const n = nums.length;
return Math.min(nums[n - 3] - nums[0], nums[n - 2] - nums[1], nums[n - 1] - nums[2]);
}func minimizeSum(nums []int) int {
sort.Ints(nums)
n := len(nums)
return min(nums[n-1]-nums[2], min(nums[n-2]-nums[1], nums[n-3]-nums[0]))
}impl Solution {
pub fn minimize_sum(mut nums: Vec<i32>) -> i32 {
nums.sort();
let n = nums.len();
(nums[n - 1] - nums[2])
.min(nums[n - 2] - nums[1])
.min(nums[n - 3] - nums[0])
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| 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 | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy by Sorting | O(n log n) | O(1) | Standard solution. Sorting reveals extreme values so the three optimal cases can be checked directly. |
| Sliding Window on Sorted Array | O(n log n) | O(1) | Useful when reasoning about keeping n-2 elements unchanged and minimizing the range of a fixed window. |
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.