✅ Beat 100% | ✨ O(N) | 🏆 Most Efficient Solution | 💯 Simply Two Passes
Intuition\n Describe your first thoughts on how to solve this problem. \n\n## Rephrase the problem\n\nA imbalance spot, or gap in an array is number $x$ for whi
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n## Rephrase the problem\n\nA *imbalance spot*, or *gap* in an array is number $x$ for which there exists the next greater number that is not $x + 1$. For example in `[1, 4, 2]` only `2` is a gap as the next greater number is `4`, not `3`.\n\nWe are looking for the **sum of (number of gaps in a subarray)**.\n\n## Reorder the summation\nInstead of finding all the gaps in a subarray and sum up all different subarrays, we can do it in the alternative way:\n  * Consider a *gap*, find how many subarrays contain that *gap*.\n  * We then sum up all different *gap*s\n\n## Define `left_edge` and `right_edge`\nFor `nums[i]`:\n  * `left_edge` is defined as the *last* index `j` such that $j < i$ and `nums[j] == nums[i] + 1`. (or $-1$ if they don\'t exist)\n  * `right_edge` is defined as the *first* index `j` such that $j > i$ and `nums[j] == nums[i] + 1`. (or $N$ if they don\'t exist)\n\nThe number of subarrays that contain the gap of `nums[i]` can be found as:\n`(i - left_edge) * (right_edge - i)`\n\n## Fix Flaw 1: Duplicates\nThe above analysis ignored the duplicated numbers. When a subarray contains `nums[i1] == nums[i2]`, only one of them can contribute to the *gap*. As a tie break we choose the last one of the duplicates in the subarray.\n\nWe need to update our definition of `right_edge` to include this fix:\n  * `right_edge` is defined as the *first* index `j` such that $j > i$ and `nums[j] == nums[i] + 1 || nums[j] == nums[i]`.\n\n## Fix Flaw 2: No Greater Number\nThe above analysis also ignores the possibility that `nums[i]` could be the greatest number of this subarray which makes it not a *gap*.\n\nWe could try to build some data structure to answer the question "whether and how many subarrays contains a larger number of `nums[i]`". However it\'s complicated and slow.\n\nIf we instead consider "How many times we over-counted the gaps"? \nThat is: "how many times we count `nums[i]` as a gap but it\'s actually the largest number of this subarray?"\n\nThe answer is amazingly simple: For each subarray, there is one and only one largest number, therefore we over-counted exactly $N \\times (N + 1) / 2$ times.\n(This is simply the number of all subarrays)\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nWe do two simple passes to find `right_edge` and `left_edge` of each `i` and sum up the counts.\n\nAt the end we fix the math by subtracting $N \\times (N + 1) / 2$ from the `count`.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$$\\Theta(N)$$\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$$\\Theta(N)$$\n\n# Code\n```\nclass Solution {\npublic:\n  int sumImbalanceNumbers(vector<int>& nums) {\n    const int N = nums.size();\n\n    // last index of each value as we seen during the iteration.\n    vector<int> last_index(N + 2, N);\n    vector<int> right_edge(N);\n    for (int i = N - 1; i >= 0; --i) {\n      int num = nums[i];\n      right_edge[i] = std::min(last_index[num], last_index[num + 1]);\n      last_index[num] = i;\n    }\n\n    int count = 0;\n\n    std::fill(last_index.begin(), last_index.end(), -1);\n    for (int i = 0; i < N; ++i) {\n      int num = nums[i];\n      int left_edge = last_index[num + 1];\n      count += (i - left_edge) * (right_edge[i] - i);\n      last_index[num] = i;\n    }\n\n    return count - N * (N + 1) / 2;\n  }\n};\n```
['Math', 'C++']