TC: O(n) | without STL | Simple Intuition | Recursion
Intuition\nYou don\'t need to sort entire array.\nJust 4 smallest and 4 biggest elements are required.\n\nThen Apply recursion or iteration to get minDifference
# Intuition\nYou don\'t need to sort entire array.\nJust 4 smallest and 4 biggest elements are required.\n\nThen Apply recursion or iteration to get minDifference.\n    change last 3 elements\n    change last 2 elements & first 1 element\n    change last 1 element & first 2 element\n    change first 3 elements\nchanging: change  to new max elem or new min elem\n\nnextSmallestElem() function will give you next Smallest Elem\nnextLargestElem() function will give you next Largest Elem\n\n# Code\n```\nclass Solution {\n    int nextLargestElem(vector<int> &nums, vector<int> &smallCopy, unordered_set<int> &st){\n        int n = nums.size(), ind = -1;\n        int largest = INT_MAX, smallest = INT_MIN; \n         if(smallCopy.size() > 4)\n            largest = smallCopy.back();\n        for(int i=0; i<n; i++){\n            if(smallest <= nums[i] && nums[i] <= largest){\n                if(st.find(i) == st.end()){\n                    smallest = nums[i];\n                    ind = i;\n                }\n            }\n        }\n        st.insert(ind);\n        return nums[ind];\n    }\n    int nextSmallestElem(vector<int> &nums, vector<int> &smallCopy, unordered_set<int> &st){\n        int n = nums.size(), ind = -1;\n        int smallest = INT_MIN, largest = INT_MAX; \n        if(smallCopy.size())\n            smallest = smallCopy.back();\n        for(int i=0; i<n; i++){\n            if(smallest <= nums[i] && nums[i] <= largest){\n                if(st.find(i) == st.end()){\n                    largest = nums[i];\n                    ind = i;\n                }\n            }\n        }\n        st.insert(ind);\n        return nums[ind];\n    }\n    void findMinDiff(int start, int end, int moves, long long &minDiff, vector<int> &smallCopy){\n        if(moves == 3){    \n            minDiff = min<long long>((long long)smallCopy[end] - (long long)smallCopy[start], minDiff);\n            return;\n        }\n        findMinDiff(start+1, end, moves+1, minDiff, smallCopy);\n        findMinDiff(start, end-1, moves+1, minDiff, smallCopy);\n    }\npublic:\n    int minDifference(vector<int>& nums) {\n        int n = nums.size();\n        long long minDiff = 1e15;\n        vector<int> smallCopy;\n        unordered_set<int> st;\n        if(n <= 4)  return 0;\n        if(n < 8){\n            for(auto num: nums) smallCopy.push_back(num);\n            sort(smallCopy.begin(), smallCopy.end());\n        }\n        else{\n            for(int i=0; i<4; i++)\n                smallCopy.push_back(nextSmallestElem(nums, smallCopy, st));\n            for(int i=0; i<4; i++)\n                smallCopy.push_back(nextLargestElem(nums, smallCopy, st));\n            reverse(smallCopy.begin()+4, smallCopy.end());\n        }\n        findMinDiff(0, smallCopy.size()-1, 0, minDiff, smallCopy);\n        return minDiff;\n    }\n};\n```
['C++']