Difficulty: Easy | Acceptance: 73.50% | Paid: No Topics: Array, Math
You are given an integer array nums and an integer k.
In one operation, you can choose any index i where 0 <= i < nums.length and change nums[i] to nums[i] + x where x is an integer from the range [-k, k]. You can apply this operation at most once for each index i.
The score of nums is the difference between the maximum and minimum elements in nums after applying the operation.
Return the minimum score of nums after changing the values at each index.
- Examples
- Constraints
- Simple Iteration
- Sorting
- Built-in Functions
Examples
Example 1
Input:
nums = [1], k = 0
Output:
0
Explanation: The score is max(nums) - min(nums) = 1 - 1 = 0.
Example 2
Input:
nums = [0,10], k = 2
Output:
6
Explanation: Change nums to be [2, 8]. The score is max(nums) - min(nums) = 8 - 2 = 6.
Example 3
Input:
nums = [1,3,6], k = 3
Output:
0
Explanation: Change nums to be [4, 4, 4]. The score is max(nums) - min(nums) = 4 - 4 = 0.
Constraints
1 <= nums.length <= 10⁴
0 <= nums[i] <= 10⁴
0 <= k <= 10⁴
Simple Iteration
Intuition To minimize the range, decrease the maximum element by k and increase the minimum element by k. The new range is max - min - 2k, or 0 if negative.
Steps
- Find the minimum and maximum values by iterating through the array
- Calculate the result as max - min - 2k
- Return 0 if the result is negative, otherwise return the result
class Solution:
def smallestRangeI(self, nums: List[int], k: int) -> int:
if len(nums) == 1:
return 0
min_val = nums[0]
max_val = nums[0]
for num in nums:
if num < min_val:
min_val = num
if num > max_val:
max_val = num
result = max_val - min_val - 2 * k
return max(0, result)Complexity
- Time: O(n)
- Space: O(1)
- Notes: Optimal solution with single pass through the array
Sorting
Intuition After sorting, the minimum is at index 0 and maximum is at the last index. Calculate the range directly from these positions.
Steps
- Sort the array in ascending order
- The minimum is at index 0, maximum at the last index
- Calculate result as nums[last] - nums[0] - 2k
- Return 0 if negative, otherwise return the result
class Solution:
def smallestRangeI(self, nums: List[int], k: int) -> int:
if len(nums) == 1:
return 0
nums.sort()
result = nums[-1] - nums[0] - 2 * k
return max(0, result)Complexity
- Time: O(n log n)
- Space: O(1) or O(n) depending on sorting implementation
- Notes: Simpler code but slower due to sorting overhead
Built-in Functions
Intuition Use language-specific built-in functions to find min and max values directly, then compute the result.
Steps
- Use built-in min/max functions to find the range
- Calculate result as max - min - 2k
- Return 0 if negative, otherwise return the result
class Solution:
def smallestRangeI(self, nums: List[int], k: int) -> int:
if len(nums) == 1:
return 0
result = max(nums) - min(nums) - 2 * k
return max(0, result)Complexity
- Time: O(n)
- Space: O(1)
- Notes: Clean and concise code using built-in utilities