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.
1using System;
2
3public class SmallestRange {
4 public int SmallestRangeII(int[] nums, int k) {
5 Array.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 SmallestRange sr = new SmallestRange();
17 int[] nums = {1, 3, 6};
18 int k = 3;
19 Console.WriteLine(sr.SmallestRangeII(nums, k)); // Output: 3
20 }
21}This approach in C# follows the same logical steps as previous solutions, relying on ordering and boundary testing at sorted array pivot points.
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.
1#include <iostream>
2#include <vector>
#include <algorithm>
using namespace std;
int smallestRangeII(vector<int>& nums, int k) {
sort(nums.begin(), nums.end());
int minVal = nums[0] + k, maxVal = nums.back() - k;
int result = nums.back() - nums[0];
for (int i = 0; i < nums.size() - 1; ++i) {
int currentMax = max(nums[i] + k, maxVal);
int currentMin = min(minVal, nums[i + 1] - k);
result = min(result, currentMax - currentMin);
}
return result;
}
int main() {
vector<int> nums = {1, 3, 6};
int k = 3;
cout << "Result: " << smallestRangeII(nums, k) << endl;
return 0;
}In C++, a direct calculation using sorted arrays where min/max hypothetical calculations are executed compactly around putative extremes and adjusted iteratively.