You are given an integer array nums.
nums is the minimum absolute difference between any two integers.nums is the maximum absolute difference between any two integers.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:
nums[0] and nums[1] to be 6 so that nums becomes [6,6,7,8,5].Example 2:
Input: nums = [1,4,3]
Output: 0
Explanation:
nums[1] and nums[2] to 1 so that nums becomes [1,1,1].
Constraints:
3 <= nums.length <= 1051 <= nums[i] <= 109Problem 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.
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.
Time Complexity: O(n log n) due to sorting. Space Complexity: O(1) as it modifies the input array in-place.
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.
Time Complexity is O(n log n) because of sorting, Space Complexity is O(1).
| 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). |
| 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. |
B. Minimum Score by Changing Two Elements - LEETCODE BIWEEKLY CONTEST 98 (Detailed Logic explained) • Joyjit Codes • 906 views views
Watch 9 more video solutions →Practice Minimum Score by Changing Two Elements with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor