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 <vector>
2#include <algorithm>
3#include <cmath>
4using namespace std;
5
6int smallestRangeII(vector<int>& nums, int k) {
7 sort(nums.begin(), nums.end());
8 int result = nums.back() - nums.front();
9 for (int i = 0; i < nums.size() - 1; ++i) {
10 int high = max(nums[i] + k, nums.back() - k);
11 int low = min(nums.front() + k, nums[i + 1] - k);
12 result = min(result, high - low);
13 }
14 return result;
15}
16
17int main() {
18 vector<int> nums = {1, 3, 6};
19 int k = 3;
20 int result = smallestRangeII(nums, k);
21 return 0;
22}Similar to the C approach, this algorithm also sorts the array and calculates the potential range differences by iterating elements and modifying endpoints.
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.
1import
The approach is executed in a similar fashion in Java, with focus on edge redefinition, iterating across to ensure composition with endpoints remains valid getting minimal diff.