1
class Solution {
2
  public int smallestRangeII(int[] nums, int k) {
3
    int n = nums.length;
4
    if (n == 1) return 0; // Max and min are the same
5

6
    Arrays.sort(nums);
7

8
    // score = minimum(max-min)
9
    // To minimize the score, need to add k to small numbers (Initial part of array)
10
    // and need to subtract k from large numbers (End part of array)
11

12
    // It might happen that when we add k to a number
13
    // And subtract k from another number
14
    // The minimum and maximum can change
15

16
    // If k>=nums[n-1]-nums[0] the score will always increase if we add k to some
17
    // numbers and subtract k from some numbers
18
    // Hence, the minimum score is the current score
19

20
    if (k >= nums[n - 1] - nums[0]) {
21
      return nums[n - 1] - nums[0];
22
    }
23

24
    // Now k < nums[n-1]-nums[0]
25
    // Add k to first p numbers and subtract k from remaining numbers
26
    // LEFT SEGMENT: First p numbers where we add k
27
    // RIGHT SEGMENT: Remaining numbers where we subtract k
28

29
    // LEFT SEGMENT: (nums[0]+k,nums[1]+k,......,nums[p-1]+k)
30
    // RIGHT SEGMENT: (nums[p]-k,nums[p+1]-k,.......nums[n-1]-k)
31

32
    // Question: Where is p?
33
    // Answer: We try all possible values for p and min score everytime
34

35
    // After subtracting and adding k to numbers,
36
    // the new minimum and maximum will be
37
    // minimum = min (nums[0]+k , nums[p]-k)
38
    // maximum = max (nums[p-1]+k, nums[n-1]-k)
39

40
    int minScore = nums[n - 1] - nums[0];
41
    for (int p = 1; p < n; p++) {
42
      int min = Math.min(nums[0] + k, nums[p] - k);
43
      int max = Math.max(nums[p - 1] + k, nums[n - 1] - k);
44
      minScore = Math.min(minScore, max - min);
45
    }
46

47
    return minScore;
48
  }
49
}