[C++] Partial sort; O(n); with explanation
We just need to know the four smallest numbers and the four largest to choose our optimal strategy. We could sort the entire array, but we don\'t have to. We ca
We just need to know the four smallest numbers and the four largest to choose our optimal strategy. We could sort the entire array, but we don\'t have to. We can use [partial sort](https://en.cppreference.com/w/cpp/algorithm/partial_sort).\n\n```C++\nint minDifference(vector<int>& nums) {\n  int const N = nums.size();\n\n  // For up to four numbers, we can always make them all equal.\n  if (N <= 4) return 0;\n\n  // Shift the four smallest numbers to the beginning\n  // and the four largest numbers to the end.\n  std::partial_sort(nums.begin(), nums.begin() + 4, nums.end());\n  std::partial_sort(nums.rbegin(), nums.rbegin() + 4, nums.rend(), std::greater<int>());\n\n  // Try all four possible ways to pick our 3 moves.\n  int result = INT_MAX;\n  for (int l = 0; l <= 3; ++l)\n    result = std::min(result, nums[N-4+l] - nums[l]);\n  return result;\n}\n```
['C']