Python3 | Brute Force (TLE) and O(n) solution with explanation | 86%ile runtime
Here is how I arrived at the solution to this problem:\n\n## Attempt #1 - Brute Force:\nEssentially the idea here is to compute the rolling maximum and minimum 
Here is how I arrived at the solution to this problem:\n\n## Attempt #1 - Brute Force:\nEssentially the idea here is to compute the rolling maximum and minimum values in every iteration inside the ```for``` loop.\n\nBelow is the implementation of the above stated approach:\n```\nclass Solution:\n    def sumOfBeauties(self, nums: List[int]) -> int:\n        beauty=[0]*len(nums)\n        for i in range(1,len(nums)-1):\n            leftarr=nums[:i]\n            rightarr=nums[i+1:]\n            if(max(leftarr)<nums[i] and min(rightarr)>nums[i]):\n                beauty[i]=2\n            elif(nums[i-1]<nums[i] and nums[i+1]>nums[i]):\n                beauty[i]=1\n            else:\n                beauty[i]=0\n        return sum(beauty)\n```\n\nAs expected, this solution TLEd.\n\n## Attempt #2 - Optimized approach:\n\nEssentially what you need to do is use 2 arrays: ```left``` and ```right```.\n\n```left``` is used to store maximum value of the array in the domain ```[0,k)``` where k is any index of the array, the first element of which is initialized as ```a[0]```, the first element of the array.\n\n```right``` is used to store minimum value of the array in the domain ```[k+1,len(arr))``` where k is any index of the array, the last element of which is initialized as ```a[-1]```, the first element of the array.\n\nPre-computation of these values brings down the time complexity of the program from ```O(n**2)``` to ```O(n)``` because it helps us avoid computing the rolling maximum and minimum in every iteration.\n\nBelow is the implementation of the above stated approach:\n```\nclass Solution:\n    def sumOfBeauties(self, a: List[int]) -> int:\n        temp,temp2=a[0],a[-1]\n        left=([a[0]]+[0]*(len(a)-1))\n        right=[0]*(len(a)-1) + [a[-1]]\n        for i in range(1,len(a)):\n            left[i]=max(a[i-1],temp)\n            temp=left[i]\n        for i in range(len(a)-2,-1,-1):\n            right[i]=min(a[i+1],temp2)\n            temp2=right[i]\n        res=0\n        for i in range(1,len(a)-1):\n            if(a[i]>left[i] and a[i]<right[i]):\n                res+=2\n            elif(a[i]>a[i-1] and a[i]<a[i+1]):\n                res+=1\n        return res\n```
['Python3']