Minimum Score by Changing Two Elements - Video Solutions
B. Minimum Score by Changing Two Elements - LEETCODE BIWEEKLY CONTEST 98 (Detailed Logic explained)
Minimum Score by Changing Two Elements - Video Solution
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 907 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
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.
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. |