Leetcode Problem 2012. Sum of Beauty in the Array

2012. Sum of Beauty in the Array

Leetcode Solutions

Prefix Maximum and Suffix Minimum Approach

  1. Initialize an array prefixMax with the same length as nums and set prefixMax[0] to nums[0].
  2. Iterate through nums starting from index 1 to the end, updating prefixMax at each index with the maximum value between nums[i] and prefixMax[i-1].
  3. Initialize an array suffixMin with the same length as nums and set suffixMin[nums.length - 1] to nums[nums.length - 1].
  4. Iterate through nums starting from the second to last index to the beginning, updating suffixMin at each index with the minimum value between nums[i] and suffixMin[i+1].
  5. Initialize a variable totalBeauty to 0.
  6. Iterate through nums from index 1 to nums.length - 2. For each index i, check:
    • If nums[i] is greater than prefixMax[i-1] and less than suffixMin[i+1], add 2 to totalBeauty.
    • Else if nums[i] is greater than nums[i-1] and less than nums[i+1], add 1 to totalBeauty.
  7. Return totalBeauty.
UML Thumbnail

Simple Linear Scan

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...