1ms linear java solution
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe approach for this problem is similar to one of the approaches for problem 907. The approach in question involves using DP to calculate the next greater array in the forward and backwards directions.\n\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nTo do this problem, we need to calculate four arrays.\nnextLarger: where nextLarger[i] is the smallest index > i where nums[nextLarger[i]] > nums[i]\nprevLarger: where prevLarger[i] is the largest index < i where nums[prevLarger[i]] > nums[i]\nnextOne: where nextOne[i] is the smallest index > i where nums[nextOne[i]] == nums[i] + 1\nprevOne: where prevOne[i] is the largest index < i where nums[prevOne[i]] == nums[i] or nums[i] + 1\n\nWe handle cases where the specified index does not exist by setting them to nums.length in the nextArr cases and -1 in the prevArr cases.\n\nThe reason for the difference in prevOne and nextOne is to deal with duplicates. One way to think of this is to imagine this problem with floats instead of integers. For every single float, we would add a very very small numbers (much smaller than the 1 / nums.length) so that equal elements are no longer equal but the difference would be really really small. In this tie-breaking situation, we would favor the numbers appear earlier in the array. If we do this, then sorting this array of floats would result in earlier elements appearing after later elements with the same value. If we did this, then with some minor adjustments (maybe instead of the condition sarr[i+1] - sarr[i] > 1, it would be sarr[i+1] - sarr[i] > 1.1 to account for any minor differences), we would get the exact same answer. If we were to write an algorithm for this, then nextOne and prevOne can be symmetric. Translating this back into integers, we realize that this is the same as having previous duplicates being considered ever so larger than duplicates that appear later in nums. Therefore, picking the previous index where the number is greater than i in the floats case is equivalent to picking the previous index where the number is greater than or equal to i in the integer case.\n\nOnce we calculate these values, then for each integer i, any array containing either the index at nextLarger[i] or prevLarger[i] while not containing the indicies at nextOne[i] nor prevOne[i] will be a valid subarray. \nThe best way to do this is to calculate the number of subarrays that do not contain nextOne[i] or prevOne[i] or (nextOne[i] - i) * (i - prevOne[i]), and to subtract it by the number of subarrays that do not contain nextOne[i] nor prevOne[i] but that also do not contain nextLarger[i] nor prevLarger[i]. \nThe number of subarrays that do not contain nextLarger[i] nor prevLarger[i] is given by the same formula (nextLarger[i] - i) * (i - prevLarger[i]). However, there is an edge case where there are subarrays that contains prevLarger[i] AND prevOne[i]. This is because while nextLarger[i] <= nextOne[i], prevLarger[i] >= prevOne[i] is not always the case due to the case with duplicates. Therefore, in this case, we must subtract these cases from (nextLarger[i] - i) * (i - prevLarger[i]). Given that prevOne[i] > prevLarger[i], the number of these cases would be (nextLarger[i] - i) * (prevOne[i] - prevLarger[i]). This is handled with the Math.max(prevLarger[i], prevOne[i]) statement in the code.\n\nCalculating nextOne and prevOne can be done by using a indicies array that is initialized to l or -1 respectively. The indicies array indicies[i] would store the smallest or largest index is is found at. This would require setting the length of indicies to be the largest element in nums. If nums[i] were allowed to be large numbers, then a HashMap could be used.\n\nCalculating nextLarger and prevLarger is trickier. This goes back to the solution for problem 907. The trick is to use DP to create the array. For nextLarger, we have the initial condition that nextLarger[nums.length - 1] = nums.length. For the DP step, we would try to nextLarger[i] by checking the number in front of it. If that number is larger, then we are done. However, if that number is smaller or equal, we would jump to the index of the number greater than that number, and we would repeat.\n\nThis algorithm is amortized linear: We can count how many times each index is visited. We know that each index will be visited once to determine it\'s value, which is linear. We divide the remaining visits into two cases:\nIntermediary jumps: index j is visited in determining the value for nextLarger[i]. nums[i] >= nums[j] meaning we jump to nextLarger[j]\nTerminating jumps: index j is visited in determining the value for nextLarger[i]. nums[i] < nums[j] meaning we assign nextLarger[i] to j. \nWe note that there are at most a linear amount of terminating jumps. Furthermore, we note that once an index j has been visited in an intermediary jump, it cannot be visited against by another intermediary jump. \nTo show this, note that by the construction of the algorithm, visiting an index implies that all of the values between this visited index and the current index in nextLarger that needs to be assigned are smaller than both of these values. This is because we keep visiting the next largest element. Therefore, a index that has already been visited in an intermediary jump cannot be visited again since that would violate this condition since there is a index before it that is larger.\nTherefore, there are an overall linear number of jumps.\n\n# Complexity\n- Time complexity: O(n + max(nums))\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nCreating the indicies array and initializing it takes O(max(nums)) time. Creating the four other arrays takes linear time, as does calculating the subarrays.\n\n- Space complexity: O(n + max(nums))\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nThere are 4 arrays created that are linear, and one array that is the size of the largest element in nums. \n\n# Code\n```java []\nclass Solution {\n    public int sumImbalanceNumbers(int[] nums) {\n        // for every single number\n        // a: get the index of the next number that is strictly greater than it\n        // b: get the index of the prev number that is strictly greater than it\n        // c: get the index of the next number that is 1 larger\n        // d: get the index of the prev number that is 1 smaller or equal\n        // these four arrays can be calculated in linear time relative to nums.length + max(nums)\n        // any substrings that contains a and/or b and does not contrain c or d will be valid\n        // calculated by takes all cases that does not contain c or d\n        // and subtracting the cases that do not contain a or b\n        // edge cases: \n        // if n is the largest element in the array, then there cannot be an imbalance \n        int l = nums.length, i, j;\n        int[] nextLarger = new int[l], prevLarger = new int[l], nextOne = new int[l], prevOne = new int[l];\n        // fill in the values for nextLarger\n        nextLarger[l - 1] = l;\n        for (i = l - 2 ; i >= 0 ; i --) {\n            j = i + 1;\n            while (j != l && nums[i] >= nums[j]) {\n                j = nextLarger[j];\n            }\n            nextLarger[i] = j;\n        }\n        // fill in the values for prevLarger\n        prevLarger[0] = -1;\n        for (i = 1 ; i < l ; i ++) {\n            j = i - 1;\n            while (j != -1 && nums[i] >= nums[j]) {\n                j = prevLarger[j];\n            }\n            prevLarger[i] = j;\n        }\n\n        int[] indicies = new int[l + 2];\n\n        // fill in nextOne\n        Arrays.fill(indicies, l);\n        for (i = l - 1 ; i >= 0 ; i --) {\n            nextOne[i] = indicies[nums[i] + 1];\n            indicies[nums[i]] = i;\n        }\n        // fill in prevOne\n        Arrays.fill(indicies, -1);\n        for (i = 0 ; i < l ; i ++) {\n            prevOne[i] = Math.max(indicies[nums[i]], indicies[nums[i] + 1]);\n            indicies[nums[i]] = i;\n        }\n\n        int sum = 0;\n        for (i = 0 ; i < l ; i ++) {\n            sum += (nextOne[i] - i) * (i - prevOne[i]) - (nextLarger[i] - i) * (i - Math.max(prevLarger[i], prevOne[i]));\n        }\n        return sum;\n    }\n}\n```\n\n![Screenshot 2024-12-12 051531.png](https://assets.leetcode.com/users/images/dc9971ed-2c85-4033-a79a-67d76de711aa_1734009482.1929002.png)\n
['Java']