C++ || BRUTE FORCE TO OPTIMISED || WITH EXPLANTION
Starting with the brute for soln firstly generate all the subarray of the given array and then sort the given subarray . Now in the sorted subarray check for th
Starting with the brute for soln firstly generate all the subarray of the given array and then sort the given subarray . Now in the sorted subarray check for the indexes whose diff if next index is greater than 1. Add the count to total count.\n\n**Time complexity: o(n)^^3log(n)(TLE);**\no(n)^^2 for generating the subarray and nlog(n) for sorting \nCode for the same:\n\n```\nclass Solution {\npublic:\n    int sumImbalanceNumbers(vector<int>& nums) {\n        int count=0;\n        int n= nums.size();\n        for(int i=0; i<n; i++){\n            for(int j=i; j<n; j++){\n                vector<int>temp(nums.begin()+i,nums.begin()+j+1);\n                sort(temp.begin(),temp.end());\n                int k= temp.size();\n                for(int l=0; l<k-1; l++){\n                    if(temp[l+1]-temp[l]>1) count++;\n                }\n            }\n        }\n        return count;\n        \n    }\n};\n```\n\n\n\n\nNow the optimised approach is based on some observation.\nConsider the array [1,2,3,4,5] we know the imbalance number will be zero.\nNow consider subarray [1,3,4,5] the imbalance no for subarray will be 2 because 3-1 is greater than 1.\nWhat do u observe? Imbalance number depends on number of segment an array can be broken into. That is what is the idea.\nStart genrating the subarray from the first element of the array. Now start adding elements check if it can be part of previously genrated segments.\nConfused how to check?\nConsider an element nums[j] which is to be added to the subarray then check if nums[j]-1 && nums[j]+1 is present or not.\nif both are present this element will act as connector an our count will decrrease by 1 as one segment is less now.\nif only one element is present no effect or duplicate then no effect.\nif both elements are not present then the new segment of nums[j] is generated and count increases by 1. I hope u get the logic it will be more clear by code.\n\n```\nclass Solution {\npublic:\n    int sumImbalanceNumbers(vector<int>& nums) {\n        int n= nums.size();\n        int count=0;\n        for(int i=0; i<n; i++){\n            unordered_set<int>st;\n            int currcount=0;\n            for(int j=i; j<n; j++){\n                if(!st.count(nums[j])){\n                    if(st.count(nums[j]+1) && st.count(nums[j]-1)){\n                        currcount--;\n                    }\n                    else if(!st.empty() && !st.count(nums[j]-1) && !st.count(nums[j]+1)){\n                        currcount++;\n                    }\n                }\n                st.insert(nums[j]);\n                count+= currcount;\n                \n            }\n        }\n        return count;\n        \n    }\n};\n```\n**Please upvote if this was helpful!**\n
['C', 'Ordered Set']