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.
1#include <stdio.h>
2#include <stdlib.h>
3
4int compare(const void* a, const void* b) {
5 return (*(int*)a - *(int*)b);
6}
7
8int smallestRangeII(int* nums, int numsSize, int k) {
9 qsort(nums, numsSize, sizeof(int), compare);
10 int result = nums[numsSize - 1] - nums[0];
11 for (int i = 0; i < numsSize - 1; i++) {
12 int high = fmax(nums[i] + k, nums[numsSize - 1] - k);
13 int low = fmin(nums[0] + k, nums[i + 1] - k);
14 result = fmin(result, high - low);
15 }
16 return result;
17}
18
19int main() {
20 int nums[] = {1, 3, 6};
21 int k = 3;
22 int result = smallestRangeII(nums, 3, k);
23 printf("%d\n", result); // Output: 3
24 return 0;
25}The algorithm first sorts the input array, then calculates the initial difference between the maximum and minimum. It iterates over the array proposing the change boundary at each index, calculating potential new high and low values (by adjusting ends with ±k), and preserving the minimal difference found.
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.
1function smallestRangeII
This JS solution offers extensive analysis by anchoring doubling range increments at both ends of nums to ascertain if middle anomalies can have residual deductions.