# Sum of Beauty in the Array
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/sum-of-beauty-in-the-array)
Canonical: https://scaleengineer.com/dsa/problems/sum-of-beauty-in-the-array
**Data structures:** Array
---
## 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 _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`

# Approaches
## Brute Force Iteration
This approach directly translates the problem statement into code. We iterate through each possible index `i` (from `1` to `n-2`) and, for each `i`, we check the conditions for beauty scores of 2, 1, and 0 in that specific order by scanning the left and right subarrays.
**Time:** O(n^2) - The outer loop runs `n-2` times. Inside this loop, we iterate up to `i` times to find the left maximum and `n-1-i` times to find the right minimum. In total, the inner operations take O(n) time. Therefore, the total time complexity is O(n) * O(n) = O(n^2). · **Space:** O(1) - We only use a few variables to store the running sum, loop indices, and temporary max/min values. The space used does not depend on the size of the input array.
**Pros:** Simple to understand and implement directly from the problem definition.; Uses constant extra space, making it memory efficient.
**Cons:** Highly inefficient due to nested loops and redundant calculations.; Will likely result in a 'Time Limit Exceeded' (TLE) error for large inputs as specified in the constraints.
### Explanation
The brute-force method involves a straightforward iteration through the relevant indices of the array. For each index `i` from `1` to `n-2`, we perform the checks as described in the problem.

1.  **Check for beauty of 2:** We need to verify that `nums[i]` is greater than every element before it and smaller than every element after it. This is done by two separate inner loops. The first inner loop finds the maximum element in `nums[0...i-1]`, and the second finds the minimum in `nums[i+1...n-1]`. If `nums[i]` satisfies the condition, we add 2 to our total sum.

2.  **Check for beauty of 1:** If the first condition is not met, we proceed to check the simpler, local condition: `nums[i-1] < nums[i] < nums[i+1]`. If this holds, we add 1 to the sum.

3.  **Beauty of 0:** If neither of the above conditions is true, the beauty is 0, and we add nothing.

This process is repeated for all applicable indices.

```java
class Solution {
    public int sumOfBeauties(int[] nums) {
        int n = nums.length;
        int totalBeauty = 0;

        for (int i = 1; i < n - 1; i++) {
            // Find max on the left
            int maxLeft = 0;
            for (int j = 0; j < i; j++) {
                maxLeft = Math.max(maxLeft, nums[j]);
            }

            // Find min on the right
            int minRight = 100001; // Constraint: nums[i] <= 10^5
            for (int k = i + 1; k < n; k++) {
                minRight = Math.min(minRight, nums[k]);
            }

            if (maxLeft < nums[i] && nums[i] < minRight) {
                totalBeauty += 2;
            } else if (nums[i - 1] < nums[i] && nums[i] < nums[i + 1]) {
                totalBeauty += 1;
            }
        }
        return totalBeauty;
    }
}
```
### Algorithm
- Initialize a variable `totalBeauty` to 0.
- Loop through the array with an index `i` from `1` to `nums.length - 2`.
- Inside the loop, for each `nums[i]`:
    - **Check for beauty 2:**
        - Find the maximum element in the subarray `nums[0...i-1]` by iterating from `j = 0` to `i-1`.
        - Find the minimum element in the subarray `nums[i+1...n-1]` by iterating from `k = i+1` to `n-1`.
        - If `nums[i]` is strictly greater than the found maximum and strictly less than the found minimum, add 2 to `totalBeauty` and continue to the next `i`.
    - **Check for beauty 1:**
        - If the condition for beauty 2 is not met, check if `nums[i-1] < nums[i] < nums[i+1]`.
        - If this local condition is true, add 1 to `totalBeauty`.
- After the loop finishes, return `totalBeauty`.

## Prefix and Suffix Precomputation
The brute-force approach is slow because it repeatedly scans the left and right subarrays. We can optimize this by precomputing the necessary information. Specifically, for each index `i`, we need the maximum of all elements to its left and the minimum of all elements to its right. This can be done efficiently in linear time using auxiliary space.
**Time:** O(n) - The algorithm consists of two main passes over the array. The first pass to populate the `suffixMin` array takes O(n) time. The second pass to calculate the total beauty also takes O(n) time. Therefore, the total time complexity is O(n) + O(n) = O(n). · **Space:** O(n) - We use an auxiliary array `suffixMin` of size `n` to store the suffix minimums. The space for `prefixMax` and other variables is constant, so the overall space complexity is dominated by the `suffixMin` array.
**Pros:** Highly efficient with linear time complexity, making it suitable for large inputs.; The logic is a clear optimization of the brute-force method, avoiding redundant work.
**Cons:** Requires extra space proportional to the input size, which might be a concern for extremely large inputs in a memory-constrained environment (though acceptable for this problem's constraints).
### Explanation
The core idea is to avoid re-computation by storing the results of prefix maximums and suffix minimums. A fully optimized approach would use two arrays, one for prefix maxes and one for suffix mins. However, we can optimize the space slightly by calculating the prefix maximums on-the-fly while iterating.

1.  **Precompute Suffix Minimums:** We create an array, let's call it `suffixMin`, where `suffixMin[i]` holds the minimum value in the subarray `nums[i...n-1]`. This can be calculated in a single pass from right to left.
    - `suffixMin[n-1] = nums[n-1]`
    - For `i` from `n-2` down to `0`, `suffixMin[i] = min(nums[i], suffixMin[i+1])`.

2.  **Calculate Total Beauty in One Pass:** After precomputing `suffixMin`, we can iterate through `nums` from `i = 1` to `n-2`. In this pass, we maintain a variable `prefixMax` which stores the maximum value encountered so far (i.e., `max(nums[0...i-1])`).
    - For each `nums[i]`, the condition for beauty 2, `max(nums[0...i-1]) < nums[i] < min(nums[i+1...n-1])`, can now be checked in O(1) time as `prefixMax < nums[i] < suffixMin[i+1]`.
    - If this is true, we add 2 to the total. Otherwise, we check the condition for beauty 1.
    - After checking the conditions for `nums[i]`, we update `prefixMax = max(prefixMax, nums[i])` before moving to the next index.

This combination of precomputation and a single main pass reduces the overall time complexity to linear.

```java
class Solution {
    public int sumOfBeauties(int[] nums) {
        int n = nums.length;
        
        // suffixMin[i] stores the minimum value in nums[i...n-1]
        int[] suffixMin = new int[n];
        suffixMin[n - 1] = nums[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            suffixMin[i] = Math.min(nums[i], suffixMin[i + 1]);
        }
        
        int totalBeauty = 0;
        int prefixMax = nums[0]; // Stores the maximum value in nums[0...i-1]
        
        for (int i = 1; i < n - 1; i++) {
            // Check for beauty of 2
            if (prefixMax < nums[i] && nums[i] < suffixMin[i + 1]) {
                totalBeauty += 2;
            } 
            // Check for beauty of 1
            else if (nums[i - 1] < nums[i] && nums[i] < nums[i + 1]) {
                totalBeauty += 1;
            }
            
            // Update prefixMax for the next iteration
            prefixMax = Math.max(prefixMax, nums[i]);
        }
        
        return totalBeauty;
    }
}
```
### Algorithm
- Get the length of the array, `n`.
- Create a `suffixMin` array of size `n` to store the minimum value from index `i` to the end of the array.
- Populate `suffixMin` by iterating from `n-2` down to `0`. Set `suffixMin[i] = min(nums[i], suffixMin[i+1])`.
- Initialize `totalBeauty = 0`.
- Initialize a variable `prefixMax = nums[0]` to keep track of the maximum value seen so far from the left.
- Iterate `i` from `1` to `n-2`:
    - Check for beauty of 2: If `prefixMax < nums[i] && nums[i] < suffixMin[i+1]`, add 2 to `totalBeauty`.
    - Else, check for beauty of 1: If `nums[i-1] < nums[i] && nums[i] < nums[i+1]`, add 1 to `totalBeauty`.
    - Update `prefixMax = max(prefixMax, nums[i])` for the next iteration.
- Return `totalBeauty`.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
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;
  }
};

```

### Python

```python
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

```