MediumNo. 2012
Sum of Beauty in the Array — LeetCode 2012 Python Solution
- Topics
- Array
- Reading time
- 3 min
- Source
- leetcode.com
The problem
You are given a 0-indexed integer array nums. For each index i (1 <= i <= nums.length - 2) the beauty of nums[i] equals: 2, if nums[j] < nums[i] < nums[k], for all 0 <= j < i and for all i < k <= nums.length - 1.
Example
- Input
- nums = [1,2,3]
- Output
- 2
- Explanation
- For each index i in the range 1 <= i <= 1:
Python solution
class Solution:
def sumOfBeauties(self, nums: List[int]) -> int:
n = len(nums)
right = [nums[-1]] * n
for i in range(n - 2, -1, -1):
right[i] = min(right[i + 1], nums[i])
ans = 0
l = nums[0]
for i in range(1, n - 1):
r = right[i + 1]
if l < nums[i] < r:
ans += 2
elif nums[i - 1] < nums[i] < nums[i + 1]:
ans += 1
l = max(l, nums[i])
return ansComplexity
- Time
- O(n)
- Space · auxiliary
- O(n)
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 2016 | Maximum Difference Between Increasing Elements | Easy |
| 0057 | Insert Interval | Medium |
| 0228 | Summary Ranges | Easy |
| 0485 | Max Consecutive Ones | Easy |
| 0665 | Non-decreasing Array | Medium |
| 0674 | Longest Continuous Increasing Subsequence | Easy |
Frequently asked questions
- How hard is LeetCode 2012. Sum of Beauty in the Array?
LeetCode 2012. Sum of Beauty in the Array is rated Medium on LeetCode.
- What is the time complexity of LeetCode 2012. Sum of Beauty in the Array?
The Python solution on this page runs in O(n).
- What is the space complexity of LeetCode 2012. Sum of Beauty in the Array?
The Python solution on this page uses O(n) auxiliary space.
- What topics does LeetCode 2012. Sum of Beauty in the Array cover?
LeetCode 2012. Sum of Beauty in the Array is tagged Array on LeetCode.