Running Imbalance with TreeSet
Intuition\nEnumerating over all subarrays and finding the imbalance of each subarray is O(n^3), which is too slow.\n\nOne common idea for these types of problem
# Intuition\nEnumerating over all subarrays and finding the imbalance of each subarray is $$O(n^3)$$, which is too slow.\n\nOne common idea for these types of problems is to optimize this brute force by processing subarrays in an order where we can use the results from the previous subarray in the next calculation.\n\n# Approach\nLoop over all starting indices of our potential subarray. For each starting index `i`, keep a running `TreeSet` that will store the items we will put in our subarray starting at `i`. Also keep track of the running imbalance of the `TreeSet`, adding this imbalance to the answer if necessary.\n\nWhen we add an element `nums[j]` to the `TreeSet`, we only need to update the imbalance due to the elements just below and above the element we insert (which we will call `floor` and `ceiling` respectively). We have three (non-disjoint) cases.\n1. `nums[j] - floor > 1`: `floor` contributes 1 imbalance since it is too far away from `nums[j]`.\n2. `ceiling - nums[j] > 1`: `nums[j]` contributes 1 imbalance since it is too far away from `ceiling`.\n3. `ceiling - floor > 1`: If this case is true, `floor` will have previously contributed 1 imbalance before we add `nums[j]` to the subarray. However, if this case is true, then case (1) is true as well. This means that we will have overcounted the imbalance due to `floor` by 1, so we will need to subtract 1 in this case.\n\nNote: since the problem has the constraint `1 <= nums[i] <= nums.length`, an array can be used instead of a TreeSet to achieve an $$O(n^2)$$ runtime. However, this approach generalizes to arbitrary values of `nums[i]`.\n\n# Complexity\n- Time complexity: $$O(n^2\\lg n)$$\n\n- Space complexity: $$O(n)$$\n\n# Code\n```\nclass Solution {\n    public int sumImbalanceNumbers(int[] nums) {\n        int n = nums.length;\n\n        int res = 0;\n\n        for (int i = 0; i < n; ++i) {\n            TreeSet<Integer> subarray = new TreeSet<>();\n            int imbalance = 0;\n            for (int j = i; j < n; ++j) {\n                Integer floor = subarray.floor(nums[j]);\n                Integer ceiling = subarray.ceiling(nums[j]);\n                if (floor != null && nums[j] - floor > 1) {\n                    ++imbalance;\n                }\n                if (ceiling != null && ceiling - nums[j] > 1) {\n                    ++imbalance;\n                }\n                if (floor != null && ceiling != null && ceiling - floor > 1) {\n                    --imbalance;\n                }\n\n                res += imbalance;\n                subarray.add(nums[j]);\n            }\n        }\n\n        return res;\n    }\n}\n```
['Ordered Set', 'Java']