1. Description
Given an integer array nums, define its low score as the smallest absolute difference between elements at two distinct indices, and its high score as the largest such difference.
The array’s score is the sum of its low and high scores.
You may replace two elements with any integers. Return the smallest score obtainable after these replacements.
2. Example
Example 1
Input: nums = [1,4,7,8,5]
Output: 3
Explanation: Replace nums[0] and nums[1] with 6 to obtain [6,6,7,8,5]. The equal elements give a low score of 0, and the high score is 8 - 5 = 3. The total is 3.
Example 2
Input: nums = [1,4,3]
Output: 0
Explanation: Replace nums[1] and nums[2] with 1. All elements are then equal, giving both a low score and a high score of 0.
3. Constraints
- 3 <= nums.length <= 10$^5$
- 1 <= nums[i] <= 10$^9$
4. Solutions
Greedy
n = nums.size()
Time complexity: O(n) on average
Space complexity: O(1)
| |