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.
  • 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 _thesum of beauty of all _nums[i]where1 <= i <= nums.length -2.

Examples

Example 1

1
2
3
4

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

1
2
3
4
5

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

1
2
3
4

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 <= 10^5
  • 1 <= nums[i] <= 10^5

Solution

Method 1 – Prefix Min/Max Arrays

Intuition

To efficiently check if all elements to the left are less and all to the right are greater, precompute prefix maximums and suffix minimums. This allows constant-time checks for the beauty-2 condition. The beauty-1 condition is checked directly.

Approach

  1. Build a prefix maximum array (left_max) where left_max[i] is the maximum of nums[0..i].
  2. Build a suffix minimum array (right_min) where right_min[i] is the minimum of nums[i..n-1].
  3. For each index i from 1 to n-2:
    • If left_max[i-1] < nums[i] < right_min[i+1], beauty is 2.
    • Else if nums[i-1] < nums[i] < nums[i+1], beauty is 1.
    • Else, beauty is 0.
  4. Sum the beauties.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
public:
    int sumOfBeauties(vector<int>& nums) {
        int n = nums.size();
        vector<int> left_max(n), right_min(n);
        left_max[0] = nums[0];
        for (int i = 1; i < n; ++i) left_max[i] = max(left_max[i-1], nums[i]);
        right_min[n-1] = nums[n-1];
        for (int i = n-2; i >= 0; --i) right_min[i] = min(right_min[i+1], nums[i]);
        int ans = 0;
        for (int i = 1; i < n-1; ++i) {
            if (left_max[i-1] < nums[i] && nums[i] < right_min[i+1]) ans += 2;
            else if (nums[i-1] < nums[i] && nums[i] < nums[i+1]) ans += 1;
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

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

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

class Solution {
    fun sumOfBeauties(nums: IntArray): Int {
        val n = nums.size
        val leftMax = IntArray(n)
        val rightMin = IntArray(n)
        leftMax[0] = nums[0]
        for (i in 1 until n) leftMax[i] = maxOf(leftMax[i-1], nums[i])
        rightMin[n-1] = nums[n-1]
        for (i in n-2 downTo 0) rightMin[i] = minOf(rightMin[i+1], nums[i])
        var ans = 0
        for (i in 1 until n-1) {
            if (leftMax[i-1] < nums[i] && nums[i] < rightMin[i+1]) ans += 2
            else if (nums[i-1] < nums[i] && nums[i] < nums[i+1]) ans += 1
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution:
    def sumOfBeauties(self, nums: list[int]) -> int:
        n = len(nums)
        left_max = [0] * n
        right_min = [0] * n
        left_max[0] = nums[0]
        for i in range(1, n):
            left_max[i] = max(left_max[i-1], nums[i])
        right_min[-1] = nums[-1]
        for i in range(n-2, -1, -1):
            right_min[i] = min(right_min[i+1], nums[i])
        ans = 0
        for i in range(1, n-1):
            if left_max[i-1] < nums[i] < right_min[i+1]:
                ans += 2
            elif nums[i-1] < nums[i] < nums[i+1]:
                ans += 1
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

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

class Solution {
    sumOfBeauties(nums: number[]): number {
        const n = nums.length;
        const leftMax = new Array(n).fill(0);
        const rightMin = new Array(n).fill(0);
        leftMax[0] = nums[0];
        for (let i = 1; i < n; i++) leftMax[i] = Math.max(leftMax[i-1], nums[i]);
        rightMin[n-1] = nums[n-1];
        for (let i = n-2; i >= 0; i--) rightMin[i] = Math.min(rightMin[i+1], nums[i]);
        let ans = 0;
        for (let i = 1; i < n-1; i++) {
            if (leftMax[i-1] < nums[i] && nums[i] < rightMin[i+1]) ans += 2;
            else if (nums[i-1] < nums[i] && nums[i] < nums[i+1]) ans += 1;
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n) — Each pass (left max, right min, and main loop) is linear.
  • 🧺 Space complexity: O(n) — For the prefix and suffix arrays.