Solution Explanation: Smallest Range II

This problem asks to find the minimum possible range (difference between the maximum and minimum element) in an array after applying a transformation to each element. Each element can be either increased or decreased by a given integer k.

Approach: Greedy + Sorting

The optimal solution utilizes a greedy approach combined with sorting. The core idea is that to minimize the range, we should try to bring the elements closer together. This is achieved by strategically increasing some elements and decreasing others.

1. Sort the array: Sorting allows us to easily identify the smallest and largest elements, and also simplifies the process of considering different combinations of increasing and decreasing elements.

2. Iterate and consider pairs: We iterate through the sorted array. For each element nums[i], we consider the impact of applying the transformation:

   • We assume elements from nums[0] to nums[i-1] are increased by k and elements from nums[i] to nums[n-1] are decreased by k (where n is the length of the array).

   • We calculate the new minimum (mi) and maximum (mx) values based on this assumption. The new minimum is the smaller of nums[0] + k and nums[i] - k, and the new maximum is the larger of nums[i-1] + k and nums[n-1] - k.

   • We update the minimum range (ans) if the current range (mx - mi) is smaller than the current minimum.

3. Return the minimum range: After iterating through all elements, we return the minimum range found.

Time and Space Complexity

• Time Complexity: O(n log n) due to the sorting step. The iteration through the array takes O(n) time.
• Space Complexity: O(log n) or O(1) depending on the sorting implementation used. In-place sorting algorithms would have O(1) space complexity.

Code Examples

The code examples below implement this approach in several programming languages. They all follow the same basic structure: sort the array, iterate, calculate the minimum and maximum, and update the minimum range.

Python:

class Solution:
    def smallestRangeII(self, nums: List[int], k: int) -> int:
        nums.sort()
        ans = nums[-1] - nums[0]  # Initialize with the initial range
        for i in range(1, len(nums)):
            mi = min(nums[0] + k, nums[i] - k)
            mx = max(nums[i - 1] + k, nums[-1] - k)
            ans = min(ans, mx - mi)
        return ans
 

Java:

class Solution {
    public int smallestRangeII(int[] nums, int k) {
        Arrays.sort(nums);
        int n = nums.length;
        int ans = nums[n - 1] - nums[0];
        for (int i = 1; i < n; ++i) {
            int mi = Math.min(nums[0] + k, nums[i] - k);
            int mx = Math.max(nums[i - 1] + k, nums[n - 1] - k);
            ans = Math.min(ans, mx - mi);
        }
        return ans;
    }
}

C++:

class Solution {
public:
    int smallestRangeII(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        int ans = nums[n - 1] - nums[0];
        for (int i = 1; i < n; ++i) {
            int mi = min(nums[0] + k, nums[i] - k);
            int mx = max(nums[i - 1] + k, nums[n - 1] - k);
            ans = min(ans, mx - mi);
        }
        return ans;
    }
};

Go:

func smallestRangeII(nums []int, k int) int {
	sort.Ints(nums)
	n := len(nums)
	ans := nums[n-1] - nums[0]
	for i := 1; i < n; i++ {
		mi := min(nums[0]+k, nums[i]-k)
		mx := max(nums[i-1]+k, nums[n-1]-k)
		ans = min(ans, mx-mi)
	}
	return ans
}
 
func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}
 
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

These examples demonstrate the core algorithm. Minor variations might exist depending on the specific language features and libraries used. Remember to include necessary header files or import statements for sorting and mathematical functions as needed.