algoadvance

You are given an integer array nums and an integer k. For each element in the nums array, you can increase or decrease it by k at most once.

The objective is to minimize the difference between the maximum and minimum values of the array after performing at most one operation (+k or -k) on each element.

Return the smallest possible difference between the maximum and minimum values of the array after performing the mentioned operation.

Clarifying Questions

1. Are the elements in the nums array distinct?
   • Not necessarily. The elements in the array can be duplicate values.
2. What are the constraints on nums and k?
   • 1 <= nums.length <= 10^4
   • 0 <= k <= 10^4
   • 0 <= nums[i] <= 10^4
3. Can k be zero?
   • Yes, and if k is zero, the difference will naturally be the difference between the maximum and minimum of the original array.

Strategy

1. Observation:
   • Increasing or decreasing each element by k will shift the possible range of values the elements can take.
   • Therefore, the new minimum value in the array can be min(nums) - k and the new maximum value can be max(nums) + k.
2. Key Insight:
   • To minimize the difference, we observe that by decreasing the highest value by k and increasing the lowest value by k, the potential range of the array can be tightened around the original mean.

Formula:

• Original minimum = min(nums)
• Original maximum = max(nums)
• Possible new minimum = min(nums) + k
• Possible new maximum = max(nums) - k
• The smallest range after operations = max(0, (max(nums) - k) - (min(nums) + k))

Code

Here’s the implementation of the above strategy in Python.

def smallestRangeI(nums, k):
    min_num = min(nums)
    max_num = max(nums)
    return max(0, (max_num - k) - (min_num + k))

# Example usage:
nums = [1, 3, 6]
k = 3
print(smallestRangeI(nums, k))  # Output: 0

Time Complexity

• Calculating the minimum and maximum of the array takes O(n), where n is the number of elements in nums.
• The rest of the operations (subtraction and max calculations) take constant time O(1).

Thus, the overall time complexity of the solution is O(n).

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?