Skip to content

2012. Sum of Beauty in the Array

Description

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.
  • 1, if nums[i - 1] < nums[i] < nums[i + 1], and the previous condition is not satisfied.
  • 0, if none of the previous conditions holds.

Return the sum of beauty of all nums[i] where 1 <= i <= nums.length - 2.

 

Example 1:

Input: nums = [1,2,3]
Output: 2
Explanation: For each index i in the range 1 <= i <= 1:
- The beauty of nums[1] equals 2.

Example 2:

Input: nums = [2,4,6,4]
Output: 1
Explanation: For each index i in the range 1 <= i <= 2:
- The beauty of nums[1] equals 1.
- The beauty of nums[2] equals 0.

Example 3:

Input: nums = [3,2,1]
Output: 0
Explanation: For each index i in the range 1 <= i <= 1:
- The beauty of nums[1] equals 0.

 

Constraints:

  • 3 <= nums.length <= 105
  • 1 <= nums[i] <= 105

Solutions

Solution 1: Preprocessing Right Minimum + Traversing to Maintain Left Maximum

Thinking

With \(n \le 10^5\), rescanning left/right extrema per \(i\) is quadratic. Beauty \(2\) needs \(nums[i]\) strictly above every left value and below every right value; beauty \(1\) only looks at neighbors.

Suffix minima \(right[i]\) are precomputed; a running \(l\) tracks the left maximum.

Each middle index first tests \(l < nums[i] < right[i+1]\) for \(2\), else the adjacent triple for \(1\).

We can preprocess the right minimum array \(right\), where \(right[i]\) represents the minimum value in \(nums[i..n-1]\).

Then we traverse the array \(nums\) from left to right, while maintaining the maximum value \(l\) on the left. For each position \(i\), we judge whether \(l < nums[i] < right[i + 1]\) holds. If it does, we add \(2\) to the answer. Otherwise, we judge whether \(nums[i - 1] < nums[i] < nums[i + 1]\) holds. If it does, we add \(1\) to the answer.

After the traversal, we can get the answer.

The time complexity is \(O(n)\), and the space complexity is \(O(n)\). Here, \(n\) is the length of the array \(nums\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
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 ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int sumOfBeauties(int[] nums) {
        int n = nums.length;
        int[] right = new int[n];
        right[n - 1] = nums[n - 1];
        for (int i = n - 2; i > 0; --i) {
            right[i] = Math.min(right[i + 1], nums[i]);
        }
        int ans = 0;
        int l = nums[0];
        for (int i = 1; i < n - 1; ++i) {
            int r = right[i + 1];
            if (l < nums[i] && nums[i] < r) {
                ans += 2;
            } else if (nums[i - 1] < nums[i] && nums[i] < nums[i + 1]) {
                ans += 1;
            }
            l = Math.max(l, nums[i]);
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int sumOfBeauties(vector<int>& nums) {
        int n = nums.size();
        vector<int> right(n, nums[n - 1]);
        for (int i = n - 2; i; --i) {
            right[i] = min(right[i + 1], nums[i]);
        }
        int ans = 0;
        for (int i = 1, l = nums[0]; i < n - 1; ++i) {
            int r = right[i + 1];
            if (l < nums[i] && nums[i] < r) {
                ans += 2;
            } else if (nums[i - 1] < nums[i] && nums[i] < nums[i + 1]) {
                ans += 1;
            }
            l = max(l, nums[i]);
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
func sumOfBeauties(nums []int) (ans int) {
    n := len(nums)
    right := make([]int, n)
    right[n-1] = nums[n-1]
    for i := n - 2; i > 0; i-- {
        right[i] = min(right[i+1], nums[i])
    }
    for i, l := 1, nums[0]; i < n-1; i++ {
        r := right[i+1]
        if l < nums[i] && nums[i] < r {
            ans += 2
        } else if nums[i-1] < nums[i] && nums[i] < nums[i+1] {
            ans++
        }
        l = max(l, nums[i])
    }
    return
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
function sumOfBeauties(nums: number[]): number {
    const n = nums.length;
    const right: number[] = Array(n).fill(nums[n - 1]);
    for (let i = n - 2; i; --i) {
        right[i] = Math.min(right[i + 1], nums[i]);
    }
    let ans = 0;
    for (let i = 1, l = nums[0]; i < n - 1; ++i) {
        const r = right[i + 1];
        if (l < nums[i] && nums[i] < r) {
            ans += 2;
        } else if (nums[i - 1] < nums[i] && nums[i] < nums[i + 1]) {
            ans += 1;
        }
        l = Math.max(l, nums[i]);
    }
    return ans;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
impl Solution {
    pub fn sum_of_beauties(nums: Vec<i32>) -> i32 {
        let n = nums.len();
        let mut right: Vec<i32> = vec![0; n];
        right[n - 1] = nums[n - 1];
        for i in (1..n - 1).rev() {
            right[i] = right[i + 1].min(nums[i]);
        }
        let mut ans = 0;
        let mut l = nums[0];
        for i in 1..n - 1 {
            let r = right[i + 1];
            if l < nums[i] && nums[i] < r {
                ans += 2;
            } else if nums[i - 1] < nums[i] && nums[i] < nums[i + 1] {
                ans += 1;
            }
            l = l.max(nums[i]);
        }
        ans
    }
}

Comments