C++ | Multiset | Detailed Explanation
Approach\n- Use two for loops to generate all subarrays.\n- But we insert the new elements in a multiset, because it will sort the elements automatically.\n- We
# Approach\n- Use two for loops to generate all subarrays.\n- But we insert the new elements in a multiset, because it will sort the elements automatically.\n- We have three cases -\n- First case is when the new element to be inserted is the largert till now, so we just check it\'s difference with the last element of the set. If the diff>1, we increase the count (that is imbalance number) else we continue.\n- Second case is when the element is the samllest hence we have to insert it at the beginning of the set so we check the difference with the first element of the set. If diff>1, we increament the count else continue.\n- Third case is when the new element will be inserted in between two elements.\n- For this case, we check the diff of the the two elements in between which the new element will be inserted.\n- If their diff>1, we need to decrement the count because now the new element will be inserted and those two numbers will not be adjacent.\n- After that we check the diff of new element with both the numbers and if diff>1, we increment the count.\n- Finally we add the count in our final answer.\n\n\n# Code\n```\nclass Solution {\npublic:\n    int sumImbalanceNumbers(vector<int>& nums) {\n        int ans = 0;\n        int n = nums.size();\n        for(int i=0;i<n;i++)\n        {\n            int cnt = 0;\n            multiset<int> ms;\n            ms.insert(nums[i]);\n            for(int j=i+1;j<n;j++)\n            {\n                auto it = ms.upper_bound(nums[j]);\n                if(it==ms.end())\n                {\n                    it--;\n                    if(nums[j]-(*it)>1)\n                        cnt++;\n                }\n                else if(it==ms.begin())\n                {\n                    if((*it)-nums[j]>1)\n                        cnt++;\n                }\n                else\n                {\n                    int num1 = *it;\n                    it--;\n                    int num2 = *it;\n                    if(num1-num2>1)\n                    {\n                        cnt--;\n                        if(nums[j]-num2>1)\n                            cnt++;\n                        if(num1-nums[j]>1)\n                            cnt++;\n                    }\n                }\n                ms.insert(nums[j]);\n                ans+=cnt;\n            }\n        }\n        return ans;\n    }\n};\n```
['Hash Table', 'Binary Search', 'C++']