kya O(N) possible hain !? Lets Solve || C++, Beats 100% ??
Check Out My New Channel : https://www.youtube.com/@Intuit_and_Code\n> if you came for O(N) approach then skip the first part\n# Intuition\n\n\n Describe your f
**Check Out My New Channel : https://www.youtube.com/@Intuit_and_Code**\n> if you came for O(N) approach then skip the first part\n# Intuition\n![image.png](https://assets.leetcode.com/users/images/6493934f-8440-4fc6-8776-4c4ba40b87f4_1719982297.7597213.png)\n\n<!-- Describe your first thoughts on how to solve this problem. -->\nMera pehla thought yeh tha ki agar main array ko sort kar doon, toh mujhe easily smallest aur largest elements mil jayenge. Phir main different combinations ko check kar sakta hoon taaki minimum difference find kar saku after removing up to 3 elements.\n\nIsko ese bhi soch sakte hain ki prefix suffix sliding window on an array and size hme upto 3 tk rkhna hain \n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. Agar array size 4 ya usse kam hai, toh return 0.\n2. Array ko sort karo.\n3. Ek loop chalao jo 4 combinations ko check kare (0 se 3 tak loop).\n4. Har combination mein, sabse chhota aur sabse bada element choose karo aur unka difference nikaalo.\n5. Minimum difference ko update karo aur return karo.\n\n# Image Visualization [ dont have table-pen so notebook me smjh lo]\n![WhatsApp Image 2024-07-03 at 10.16.08 AM.jpeg](https://assets.leetcode.com/users/images/2950be14-564d-47d7-854b-c6ab425159b1_1719982048.9703321.jpeg)\n\n\n# Complexity\n- Time complexity: O(nlogn)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(1)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n    int minDifference(vector<int>& n) {\n        if(n.size()<=4){\n            return 0;\n        }\n        int ans=INT_MAX;\n        sort(n.begin(),n.end());\n\n        int w=-1,siz=n.size()-2;\n        for(int i=0;i<=3;i++){\n            // nxtmin\n            int nxtmin = n[w+1];\n            // prevmax\n            int prevmax = n[siz+w-1];\n\n            ans = min(ans,prevmax-nxtmin);\n            w++;\n        }\n        \n        return ans;\n    }\n};\n```\n\n\n# Intuition & Approach\n![image.png](https://assets.leetcode.com/users/images/ad4b00bb-7587-466a-8036-1fa7ca5abf8f_1719982260.5012903.png)\nToh ghum firake baat aa rhi thi ki we need atleast 4 minimum element and then 4 maximum element jisse hamara computation possible ho\ntoh without sorting finding 4 max and 4 min is possible\nbs thoda code bada likhna pda \uD83E\uDD75\n\n# Complexity\n- Time complexity: O(N)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(1)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n    int minDifference(vector<int>& n) {\n        if (n.size() <= 4) {\n            return 0;\n        }\n\n        // Initialize variables to store the four smallest and four largest values\n        int min1 = INT_MAX, min2 = INT_MAX;\n        int min3 = INT_MAX, min4 = INT_MAX;\n        int max1 = INT_MIN, max2 = INT_MIN;\n        int max3 = INT_MIN, max4 = INT_MIN;\n\n        // Traverse the array once to find the four smallest and four largest elements\n        for (int num : n) {\n            if (num < min1) {\n                min4 = min3;\n                min3 = min2;\n                min2 = min1;\n                min1 = num;\n            } else if (num < min2) {\n                min4 = min3;\n                min3 = min2;\n                min2 = num;\n            } else if (num < min3) {\n                min4 = min3;\n                min3 = num;\n            } else if (num < min4) {\n                min4 = num;\n            }\n\n            if (num > max1) {\n                max4 = max3;\n                max3 = max2;\n                max2 = max1;\n                max1 = num;\n            } else if (num > max2) {\n                max4 = max3;\n                max3 = max2;\n                max2 = num;\n            } else if (num > max3) {\n                max4 = max3;\n                max3 = num;\n            } else if (num > max4) {\n                max4 = num;\n            }\n        }\n\n        // Compute the minimum difference by considering different removal strategies\n        vector<int> smallest = {min1, min2, min3, min4};\n        vector<int> largest = {max1, max2, max3, max4};\n        int ans = INT_MAX;\n        \n        for (int i = 0; i < 4; ++i) {\n            ans = min(ans, largest[3-i] - smallest[i]);\n        }\n\n        return ans;\n    }\n};\n```\n
['Array', 'Greedy', 'Sliding Window', 'Sorting', 'C++']