Watch 10 video solutions for Minimum Score by Changing Two Elements, a medium level problem involving Array, Greedy, Sorting. This walkthrough by Joyjit Codes has 906 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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. |