Java | 0(n)| 100% faster
The logic behind is that we are maintaining two arrays leftmax and rightmin . leftmax array will store the max value for each index i from 0 to i-1 (both includ
The logic behind is that we are maintaining two arrays leftmax and rightmin . leftmax array will store the max value for each index i from 0 to i-1 (both included). Moreover, rightmin array will store the min value for each index i from i+1 to n (both included).We will traverse the array from  1<=i<= N -2, since 0 and last index will never contribute to answer.If the value at index i lies in the middle of its adjecent indexes ( ie nums[i-1]<nums[i]<nums[i+1] ) then we will increment the value of beauty by 1.\nAlso , if it is greater than leftmax[i] and rightmin[i] we will increment the value of beauty by 1.\n\nTime Complexity (TC) - 0(n)\nSpace Complexity (SC) - 0(n)\n\n**Better Approach:-** You can keep a variable leftmax instead of array.So, it can be done using one extra array only,instead of two.\n\n\'\'\'\n\n\tpublic int sumOfBeauties(int[] nums) {\n        int[] leftmax = new int[nums.length];\n\t\tint max = nums[0];\n\t\tfor (int i = 1; i < nums.length-1; i++) {\n\t\t\tleftmax[i] = max;\n\t\t\tmax = Math.max(max, nums[i]);\n\t\t}*\n\n\t\tint[] rightmin = new int[nums.length];\n\t\tmax = nums[nums.length - 1];\n\t\tfor (int i = nums.length - 2; i >= 1; i--) {\n\t\t\trightmin[i] = max;\n\t\t\tmax = Math.min(max, nums[i]);\n\t\t}\n\n\t\tint beauty = 0;\n\n\t\tfor (int i = 1; i < nums.length - 1; i++) {\n\t\t\tif (nums[i] > nums[i - 1] && nums[i] < nums[i + 1]) {\n\t\t\t\tbeauty++;\n\t\t\t\tif (nums[i] > leftmax[i] && nums[i] < rightmin[i]) {\n\t\t\t\t\tbeauty++;\n\t\t\t\t}\n\t\t\t}\n\t\t}\n\t\treturn beauty;\n    }\n\t\n\t\n\t
['Java']