Very Simple and Short Multiset Solution with Explaination 90% 90%
Intuition\n Describe your first thoughts on how to solve this problem. \nThe intuition is simple assume we have a sorted array sorr formed usng subarray[i,j] an
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe intuition is simple assume we have a sorted array `sorr` formed usng subarray[i,j] and it\'s imbalance number is known to be `x` and now we insert `j + 1` element in `sorr` and we find it would affect our imbalance number.\n\n**to keep a sorted subarray we would be using a multiset.**\n*We generate all subarrays in O(N^2) and try to calculate the affect of adding a number to that sorted subarray.*\n\neg:- Let the array be `............ab..........` \nIf we add `j + 1`th in the array it would be stored on the index of `lower_bound(sorr.begin(), sorr.end(), nums[j + 1])`\n\n***assume this index lies between `a & b`.***\n\n- if c is getting inserted between `a & b` then it might reduce the `imbalance` score by 1 if and only if `a & b` exists and `a & b` were contributing to the `imbalance score` i.e `b - a > 1`.\n``` C++ []\nif(right != mst.end() && right != mst.begin() && *right - *left > 1){\n    cnt--;\n}\n```\n\n- If c is getting inserted between `a & b` then it might add a imbalance score between `a & c` if and only if a exists and `c - a > 1`.\n``` C++ []\nif(right != mst.begin() && nums[j] - *left > 1){\n    cnt++;\n}\n```\n- If c is getting inserted between `a & b` then it might add a imbalance score between `c & b` if and only if b exists and `b - c > 1`.\n```C++ []\nif(right != mst.end() && *right - nums[j] > 1){\n    cnt++;\n}\n```\n\n# Complexity\n- Time complexity: $$O(N^2 * Log(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 sumImbalanceNumbers(vector<int>& nums) {\n        int n = nums.size();\n        int ans = 0;\n        for(int i = 0; i < n; i++){\n            multiset<int> mst;\n            int cnt = 0;\n            mst.insert(nums[i]);\n            for(int j = i + 1; j < n; j++){\n                auto right = mst.lower_bound(nums[j]);\n                auto left = right;\n                left--;\n                if(right != mst.end() && right != mst.begin() && *right - *left > 1){\n                    cnt--;\n                }\n                if(right != mst.begin() && nums[j] - *left > 1){\n                    cnt++;\n                }\n                if(right != mst.end() && *right - nums[j] > 1){\n                    cnt++;\n                }\n                ans += cnt;\n                mst.insert(nums[j]);\n            }\n        }\n        return ans;\n    }\n};\n```
['Array', 'Greedy', 'Sorting', 'C++']