Imbalance Number Solution
Approach 1 - Brute Force\n Describe your approach to solving the problem. \n\n# Intuition\n Describe your first thoughts on how to solve this problem. \nSort an
# Approach 1 - Brute Force\n<!-- Describe your approach to solving the problem. -->\n\n# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nSort and compute the imbalance number of every subarray. Output the sum of all imbalance numbers.\n\n# Code\n```C++ []\nclass Solution {\npublic:\n    int sumImbalanceNumbers(const vector<int>& nums) {\n        int ans = 0;\n        \n        for (int i = 0; i < nums.size(); i++) {\n            for (int j = i+1; j < nums.size()+1; j++) {\n                vector<int> subarr (nums.begin()+i, nums.begin()+j);\n                sort(subarr.begin(), subarr.end());\n                ans += imbalance(subarr);\n            }\n        }\n        \n        return ans;\n    }\n        \n    int imbalance(const vector<int>& arr) {\n        int points = 0;\n        \n        for (int i = 0; i < arr.size()-1; i++) {\n            points += int(arr[i+1] - arr[i] > 1);\n        }\n                \n        return points;\n    }\n};\n```\n```Java []\nclass Solution {\n    public int sumImbalanceNumbers(int[] nums) {\n        int ans = 0;\n        \n        for (int i = 0; i < nums.length; i++) {\n            for (int j = i+1; j < nums.length+1; j++) {\n                int[] subarr = Arrays.copyOfRange(nums, i, j);\n                Arrays.sort(subarr);\n                ans += imbalance(subarr);\n            }\n        }\n        \n        return ans;\n    }\n        \n    public int imbalance(int[] arr) {\n        int points = 0;\n        \n        for (int i = 0; i < arr.length-1; i++) {\n            if (arr[i+1] - arr[i] > 1) {\n                points += 1;\n            }\n        }\n                \n        return points;\n    }\n}\n```\n```Python3 []\nclass Solution:\n    def sumImbalanceNumbers(self, nums: List[int]) -> int:\n        ans = 0\n        \n        for i in range(len(nums)):\n            for j in range(i+1, len(nums)+1):\n                subarr = nums[i:j]\n                subarr.sort()\n                ans += self.imbalance(subarr)\n        \n        return ans\n        \n    def imbalance(self, arr: List[int]) -> int:\n        points = 0\n        \n        for i in range(len(arr)-1):\n            points += int(arr[i+1] - arr[i] > 1)\n                \n        return points\n```\n\n# Complexity\n- Time complexity: $$O(n^3\\log(n))$$\n    - There are $$\\frac{(n+1)n}{2} = O(n^2)$$ subarrays\n    - Sorting a subarray is $$O(n\\log(n))$$ time\n    - Creating subarray and finding imbalance of sorted array is $$O(n)$$ time\n    - Total time is $$O(n^2)*O(n + n\\log(n)) = O(n^3 + n^3\\log(n)) = O(n^3\\log(n))$$  \n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(n)$$\n    - Each created subarray has $$n$$ elements at most \n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Approach 2 - Hash Set\n<!-- Describe your approach to solving the problem. -->\n\n# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nInstead of sorting subarrays, the elements of a subarray can be stored within a hash set. By extending subarrays rightward and comparing new elements to elements from previous subarrays, it is possible to determine a subarray\'s imbalance number in constant time.\n\nLet `nums[i...j]` be a subarray with an imbalance number of `x`. Let `S` be the set of all elements in `nums[i...j]`. The imbalance number of subarray `nums[i...j+1]` can be deduced by comparing `k = nums[j+1]` to the elements of `S`.\n\n1. If `k` is 1 away from exactly one element of `S`, `nums[i...j+1]` also has an imbalance of `x`\n    - If `k` is 1 more than previous max, imbalance is unchanged . \n    - If `k` is 1 less than previous min, imbalance is unchanged. \n    - If `k` is sandwiched between previous elements `a` and `b` in sorted order with `a + 1 = k` or `k + 1 = b`, the elements from `a` to `b` still contribute 1 imbalance point to the subarray and the total doesn\'t change\n2. If `k` is not 1 away from any elements of `S`, `nums[i...j+1]` has an imbalance of `x+1`\n    - If `k` exceeds previous max by more than 1, an imbalance point is gained\n    - If `k` lies beneath previous min by more than 1, an imbalance point is gained\n    - If `k` is sandwiched between previous elements `a` and `b` in sorted order, the elements from `a` to `b` now contribute 2 imbalance points to the subarray instead of 1. The total imbalance rises by 1.\n3. If `k` is 1 away from two elements of `S` and not currently contained in `S`, `nums[i...j+1]` has an imbalance of `x-1`\n    - Being 1 away from two elements is equivalent to being sandwiched between elements `a = k - 1` and `b = k + 1` in sorted order \n    - Previously `a` and `b` contributed 1 imbalance point. Now they contribute none.\n\nFor every index `i` of `nums`, examine each subarray extending rightward from `i`. Use the above analysis to figure out the imbalance of new subarrays using sets of elements from old subarrays. Output the sum of all these imbalances.\n\n# Algorithm  \n1. Create variable `ans` storing the sum of all imbalances. Set `ans = 0`.\n2. Have `i` iterate over numbers `0` to `nums.length`\n3. For each `i`: \n    - Create hash set `subNums` storing elements from previous subarrays \n    - Create variable `imbalance` recording imbalance of current subarray. Set `imbalance = 0.` \n    - Have `j` iterate over numbers `i` to `nums.length`\n4. For each `j`:\n    - Set `k = nums[j]`\n    - If `subNums` is nonempty AND `k-1`, `k`, and `k+1` are not in `subNums`, increment `imbalance` by 1\n    - If `k` is not in `subNums` AND `k+1` and `k-1` are in subNums, decrement `imbalance` by 1\n    - Insert `k` into `subNums` and add `imbalance` to `ans`\n5. Output `ans` \n\n# Code\n```C++ []\nclass Solution {\npublic:\n    int sumImbalanceNumbers(const vector<int>& nums) {\n        int ans = 0;\n        \n        for (int i = 0; i < nums.size(); i++) {\n            unordered_set<int> subNums;\n            int imbalance = 0;\n            \n            for (int j = i; j < nums.size(); j++) {\n                const int k = nums[j];\n                auto iter1 = subNums.find(k-1);\n                auto iter2 = subNums.find(k);\n                auto iter3 = subNums.find(k+1);\n\n                if (!subNums.empty() && iter1 == subNums.end() && iter2 == subNums.end() && iter3 == subNums.end()) {\n                    imbalance++;\n                }\n                if (iter2 == subNums.end() && iter1 != subNums.end() && iter3 != subNums.end()) {\n                    imbalance--;\n                }\n                \n                subNums.insert(k);\n                ans += imbalance;\n            }\n        }\n\n        return ans;\n    }\n};\n```\n```Java []\nclass Solution {\n    public int sumImbalanceNumbers(int[] nums) {\n        int ans = 0;\n        \n        for (int i = 0; i < nums.length; i++) {\n            HashSet<Integer> subNums = new HashSet<Integer> ();\n            int imbalance = 0;\n            \n            for (int j = i; j < nums.length; j++) {\n                final int k = nums[j];\n\n                if (!subNums.isEmpty() && !subNums.contains(k-1) && !subNums.contains(k) && !subNums.contains(k+1)) {\n                    imbalance++;\n                }\n                if (!subNums.contains(k) && subNums.contains(k-1) && subNums.contains(k+1)) {\n                    imbalance--;\n                }\n                \n                subNums.add(k);\n                ans += imbalance;\n            }\n        }\n\n        return ans;\n    }\n}\n```\n```Python3 []\nclass Solution:\n    def sumImbalanceNumbers(self, nums: List[int]) -> int:\n        ans = 0\n        n = len(nums)\n        \n        for i in range(n):\n            subNums = set()\n            imbalance = 0\n            \n            for j in range(i, n):\n                k = nums[j]\n\n                if len(subNums) > 0 and {k-1, k, k+1}.isdisjoint(subNums):\n                    imbalance += 1\n                if k not in subNums and {k-1, k+1}.issubset(subNums):\n                    imbalance -= 1\n\n                subNums.add(k)\n                ans += imbalance  \n        \n        return ans\n```\n\n# Complexity\n- Time complexity: $$O(n^2)$$\n    - There are $$\\frac{(n+1)n}{2} = O(n^2)$$ subarrays\n    - Checking and inserting elements in a hash set is $$O(1)$$ time\n    - Total time is $$O(n^2)*O(1) = O(n^2)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(n)$$\n    - The set contains $$n$$ elements at most \n<!-- Add your space complexity here, e.g. $$O(n)$$
['Hash Table', 'C++', 'Java', 'Python3']