C++ || Very Simple and Fast || Beats 95% || Iterate over all subarrays
Intuition\n Describe your first thoughts on how to solve this problem. \nUpper Constraint for N is 10^3. Total Subarrays are O(N^2). \nIterating through each su
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nUpper Constraint for N is 10^3. Total Subarrays are O(N^2). \nIterating through each subarray is absolutely feasible.\n\nIf I know the imbalance number of subarray A[i, i+1, i+2 ... i+k], then I can find the imbalance number for subarray A[i, i+1, i+2 ... i+k, i+k+1] quite easily. \nAs, the new number can either increase the imbalance number by atmost 1 or decrease it by atmost 1. \n\nFor example : Consider the subarray : [1, 3, 5]. Now suppose the next element is 2. How would the imbalance number change ? Similarly think for 3, 4, 6 and 7. The conditions where imbalance number increases or decreases or remains the same would be clear to you.\n[See code for those conditions]\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nMaintain an array/vector/hashset/map to represent the elements present in the subarray that is being currently considered.\n\nIterate through all subarrays in O(N^2) while appropriately modifying the current imbalance number [\'count\' in below code] and final ans.\n\nMake sure to redo the status of all current elements, before shifting the start of the subarray in the next iteration.\n\n# Complexity\n- Time complexity: O(N^2)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n\n- Space complexity: O(N) [or or more appropriately O(max_element(Arr))]\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n\n# Code\n```\nclass Solution {\npublic:\n    int sumImbalanceNumbers(vector<int>& nums) {\n        int n = nums.size(), ans = 0, count;\n        vector<int> present(1002, false);\n        for(int i=0;i<n;i++) {\n            present[nums[i]] = true;\n            count = 0;\n            for(int j=i+1;j<n;j++) {\n                if(!present[nums[j]]) {\n                    if(!present[nums[j]+1] && !present[nums[j]-1])\n                        count ++;\n                    else if(present[nums[j]+1] && present[nums[j]-1])\n                        count --;\n                }\n                present[nums[j]] = true;\n                ans += count;\n            }\n            for(int j=i;j<n;j++)\n                present[nums[j]] = false;\n        }\n        return ans;\n    }\n};\n```\nYes, I agree with you.\nThis problem should be labelled as \'Medium\' and not \'Hard\'.\nKindly Upvote..!!\n\n![image.png](https://assets.leetcode.com/users/images/a31e383c-f4fe-4b02-8221-6cca5e966de3_1688626000.7124975.png)\n
['Array', 'Hash Table', 'Greedy', 'C++']