Sponsored
Sponsored
After sorting the array, our potential strategy is to focus on bridging the maximum and minimum gap by controlling possible breakpoints where the boundary conditions for minimum and maximum flip due to the presorted state.
Time Complexity: O(n log n) due to the sorting operation. Space Complexity: O(1) if we ignore input space.
1import java.util.Arrays;
2
3public class SmallestRangeII {
4 public int smallestRangeII(int[] nums, int k) {
5 Arrays.sort(nums);
6 int result = nums[nums.length - 1] - nums[0];
7 for (int i = 0; i < nums.length - 1; i++) {
8 int high = Math.max(nums[i] + k, nums[nums.length - 1] - k);
9 int low = Math.min(nums[0] + k, nums[i + 1] - k);
10 result = Math.min(result, high - low);
11 }
12 return result;
13 }
14
15 public static void main(String[] args) {
16 SmallestRangeII obj = new SmallestRangeII();
17 int[] nums = {1, 3, 6};
18 int k = 3;
19 System.out.println(obj.smallestRangeII(nums, k)); // Output: 3
20 }
21}This Java solution mimics the strategy used in other languages: by sorting and iterating to test setting breakpoints along the range, minimizing the boundary spread.
A slight variation that considers minimizing and maximizing simultaneously, with the goal of finding directly altered extremes without sequence traversals.
Time Complexity: O(n log n), Space Complexity: O(1) for array due to in-place.
1using System;
2
public class SmallestRangeII {
public int SmallestRange(int[] nums, int k) {
Array.Sort(nums);
int minVal = nums[0] + k;
int maxVal = nums[nums.Length - 1] - k;
int result = nums[nums.Length - 1] - nums[0];
for (int i = 0; i < nums.Length - 1; i++) {
int currentMax = Math.Max(nums[i] + k, maxVal);
int currentMin = Math.Min(minVal, nums[i + 1] - k);
result = Math.Min(result, currentMax - currentMin);
}
return result;
}
public static void Main(string[] args) {
SmallestRangeII solution = new SmallestRangeII();
int[] nums = {1, 3, 6};
int k = 3;
Console.WriteLine(solution.SmallestRange(nums, k));
}
}For C#, possibilities are identified and recalculated succinctly based on splaying between conceivable limits, testing reduction consecutively.