1
// Need to consider each ith value as boundary and considering that,
2
// the max value can be max val - k or i-1 th value + k
3
// similarly the mn value can be min val + k or ith value - k
4
// Need to check the difference of max min for all ith positions and minimize
5
// this. Also check if the calculate min is larger than initial min or not
6
/*
7
Example :
8
     2 4 7 8 and k = 5
9
-k: -3 -1 2 3
10
+k: 7 9 12 13
11

12
here min value will be 9 -2 = 7 when i = 2 but intital diff between min and max
13
is 6, so the answer will be 6.
14
*/
15

16
class Solution {
17
 public:
18
  int smallestRangeII(vector<int> &nums, int k) {
19
    sort(nums.begin(), nums.end());
20
    int mn = nums.front();
21
    int mx = nums.back();
22
    if (mx - mn <= k) return mx - mn;
23
    int newMn = INT_MAX, newMx = INT_MIN;
24
    int ans = mx - mn;
25
    mn = mn + k;
26
    mx = mx - k;
27
    for (int i = 1; i < nums.size(); ++i) {
28
      newMn = min(mn, nums[i] - k);
29
      newMx = max(mx, nums[i - 1] + k);
30
      ans = min(ans, newMx - newMn);
31
    }
32
    return ans;
33
  }
34
};