Concise O(n) C++ solution 14ms 14lines
Intuition\nLet $F(k)$ be the number of imbalance numbers of all subarrays that ends at index $k$. Given $F(k)$, one can find $F(k+1)$ in constant time.\n\n# App
# Intuition\nLet $F(k)$ be the number of imbalance numbers of all subarrays that ends at index $k$. Given $F(k)$, one can find $F(k+1)$ in constant time.\n\n# Approach\nStore the last index of each value, and use that to update and accumulate $F(k)$ for $k = 0, \\ldots, n-1$.\n\n# Complexity\n- Time complexity:\n$O(n)$\n\n- Space complexity:\n$O(n)$\n\n# Code\nhttps://leetcode.com/submissions/detail/984308237/\n```\nclass Solution {\npublic:\n    int sumImbalanceNumbers(vector<int>& nums) {\n        const int n = nums.size();\n        vector<int> index(n+2); // map from value to last_index + 1\n        int result = 0;\n        int dp = 0; // number of imbalance numbers up to nums[i]\n        for (int i = 0; i < n; ++i) {\n            int x = nums[i];\n            int base = index[x]; // to exclude subarrays that already have value x\n            auto [lo, hi] = minmax({index[x-1], index[x+1]});\n            dp += i - max(hi, base); // add the number of subarrays with a gap on both sides\n            dp -= max(lo, base) - base; // subtract the number of subarrays with consecutive values on both sides\n            result += dp;\n            index[x] = i + 1;\n        }\n        return result;\n    }\n};\n```
['C++']