✔️[C++] || optimized Simple Code || Explained || TC: O( n ) , SC: O( 1 )
Please Upvote if it helps\u2B06\uFE0F\nWhy we will go for priority queue not for sorting ?\n--> Because this method only takes O( n ) time complexity and O( 1 )
#### *Please Upvote if it helps\u2B06\uFE0F*\n**Why we will go for priority queue not for sorting ?**\n*--> Because this method only takes O( n ) time complexity and O( 1 ) space complexity. But in sorting takes O( n log(n) ) time complexity. \nThe time comlexity for using priority queue is O( n ) because we restricted the size of priority queue to 4. So, total time complexity is O( n log(4) ) i.e. we can write it O( n ).*\n\n**We require only 4 largest element and 4 smallest element only for the required answer.**\nThe explanation of this is here: https://leetcode.com/problems/minimum-difference-between-largest-and-smallest-value-in-three-moves/discuss/730567/JavaC%2B%2BPython-Straight-Forward\n\n```\n\tint minDifference(vector<int>& nums) {\n        int n=nums.size();\n        if(n<5) return 0;\n        priority_queue<int> pq_min;\n        priority_queue <int, vector<int>, greater<int>> pq_max;\n        for(int i=0;i<n;++i){\n            if(pq_max.size()<4) pq_max.push(nums[i]), pq_min.push(nums[i]);\n            else{\n                if(pq_max.top()<nums[i]) pq_max.pop(), pq_max.push(nums[i]);\n                if(pq_min.top()>nums[i]) pq_min.pop(), pq_min.push(nums[i]);\n            }\n        }\n        \n        vector<int> min_four(4);\n        for(int i=0;i<4;++i) min_four[3-i]=pq_min.top(), pq_min.pop();\n        \n        int ans=INT_MAX;\n        for(int i=0;i<4;++i){\n            ans=min(ans, pq_max.top()-min_four[i]);\n            pq_max.pop();\n        }\n        return ans;\n    }\n```
['C']