Smallest Range I

Problem Description

You are given an integer array nums and an integer k. In one operation, you can choose any index i 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 in the array. The score of nums is the difference between the maximum and minimum elements in nums. Return the minimum score of nums after applying the mentioned operation at most once for each index.

Key Insights

• The maximum possible value in nums can be reduced by k.
• The minimum possible value in nums can be increased by k.
• The score can be minimized by adjusting the maximum downwards and the minimum upwards.
• If the difference between the maximum and minimum values is less than or equal to 2*k, the score can be zero, as we can bring them together.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

To solve the problem, we can follow these steps:

1. Determine the maximum and minimum values in the nums array.
2. Adjust the maximum downwards by k and the minimum upwards by k.
3. Calculate the new score as max(nums) - min(nums).
4. If this score is less than or equal to 2*k, the result is 0. Otherwise, return the calculated score.

We use simple arithmetic operations and comparisons, making it efficient and straightforward.

Code Solutions