Java | O(n) with explanation using priorityQueues WITHOUT SORTING THE WHOLE ARRAY
We only need the 4 (3 possible changes plus 1) highest and 4 lowest numbers, as in case we take the 3 lowest numbers and convert them into the 4th (let\'s call 
We only need the 4 (3 possible changes plus 1) highest and 4 lowest numbers, as in case we take the 3 lowest numbers and convert them into the 4th (let\'s call it the minNumberInRangeIndex), the difference would be the max number(nums[maxNumberInRangeIndex]) minus the nums[minNumberInRangeIndex].\nWe use a sliding window technique to see if any of the other possible options might give us a lowest difference: we substract 1 from maxNumberInRange and minNumberInRange, check the difference between their values and save it as the min if it\'s less.\n\nAs we don\'t need all numbers, we don\'t need to sort the whole array. We can just go over it and collect the 4 lowest and 4 highest numbers with 2 priorityqueues. As each priority queue would be at most 4 of size, this gives us a runtime of O(n log 4) = O(n).\n\nThis solution runs in 31 ms though, instead of 14 ms that runs just sorting all the elems. This is because the tests are done with a very small n. If n was larger as the problem states (1 <= nums.length <= 10^5) this probably would be way faster than sorting. \n\nLet me know if I\'m wrong, it\'s my first post!\n\n```\nclass Solution {\n  public int minDifference(int[] nums) {\n    final int numberOfChanges = 3;\n    if (nums.length <= numberOfChanges + 1) {\n      return 0;\n    }\n    int[] numsSimplified = getSimplifiedArray(nums, numberOfChanges);\n    return minDifferenceSlidingWindow(numsSimplified, numberOfChanges);\n  }\n  \n  private int[] getSimplifiedArray(int[] nums, int numberOfChanges) {\n    Queue<Integer> higher = new PriorityQueue<>(); // Want to have the lowest number of the high numbers first\n    Queue<Integer> lower = new PriorityQueue<>(Collections.reverseOrder()); // Want to have the higher of the lowest\n    for (int i = 0; i < nums.length; i++) {\n      higher.add(nums[i]);\n      if (higher.size() > numberOfChanges + 1) {\n        int value = higher.remove();\n        lower.add(value);\n        if (lower.size() > numberOfChanges + 1) {\n          lower.remove();\n        }\n      }\n    }\n    int[] nums2 = new int[higher.size() + lower.size()];\n    while (lower.size() > 0) {\n      int value = lower.remove().intValue();\n      nums2[lower.size()] = value;\n    }\n    while (higher.size() > 0) {\n      int value = higher.remove().intValue();\n      nums2[nums2.length - higher.size() - 1] = value;\n    }\n    return nums2;\n  }\n  \n  private int minDifferenceSlidingWindow(int[] nums, int numberOfChanges) {\n    int maxIndex = nums.length - 1;\n    int minIndex = numberOfChanges;\n    int min = Integer.MAX_VALUE;\n    for (; minIndex >= 0; minIndex--, maxIndex--) {\n      int diff = nums[maxIndex] - nums[minIndex];\n      min = Math.min(min, diff);\n    }\n    return min;\n  }\n}\n```
['Heap (Priority Queue)', 'Java']