Sum of Beauty in the Array

Med

#1832Time: 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.

Data structures

Array

Prompt

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 <= 10⁵
1 <= nums[i] <= 10⁵

Approaches

2 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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.

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.
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.
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.

1class Solution {2    public int sumOfBeauties(int[] nums) {3        int n = nums.length;4        int totalBeauty = 0;5 6        for (int i = 1; i < n - 1; i++) {7            // Find max on the left8            int maxLeft = 0;9            for (int j = 0; j < i; j++) {10                maxLeft = Math.max(maxLeft, nums[j]);11            }12 13            // Find min on the right14            int minRight = 100001; // Constraint: nums[i] <= 10^515            for (int k = i + 1; k < n; k++) {16                minRight = Math.min(minRight, nums[k]);17            }18 19            if (maxLeft < nums[i] && nums[i] < minRight) {20                totalBeauty += 2;21            } else if (nums[i - 1] < nums[i] && nums[i] < nums[i + 1]) {22                totalBeauty += 1;23            }24        }25        return totalBeauty;26    }27}

Complexity

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.

Trade-offs

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.

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.

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.

Walkthrough

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.

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]).
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.

1class Solution {2    public int sumOfBeauties(int[] nums) {3        int n = nums.length;4        5        // suffixMin[i] stores the minimum value in nums[i...n-1]6        int[] suffixMin = new int[n];7        suffixMin[n - 1] = nums[n - 1];8        for (int i = n - 2; i >= 0; i--) {9            suffixMin[i] = Math.min(nums[i], suffixMin[i + 1]);10        }11        12        int totalBeauty = 0;13        int prefixMax = nums[0]; // Stores the maximum value in nums[0...i-1]14        15        for (int i = 1; i < n - 1; i++) {16            // Check for beauty of 217            if (prefixMax < nums[i] && nums[i] < suffixMin[i + 1]) {18                totalBeauty += 2;19            } 20            // Check for beauty of 121            else if (nums[i - 1] < nums[i] && nums[i] < nums[i + 1]) {22                totalBeauty += 1;23            }24            25            // Update prefixMax for the next iteration26            prefixMax = Math.max(prefixMax, nums[i]);27        }28        29        return totalBeauty;30    }31}

Complexity

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.

Trade-offs

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).

Solutions

Solution

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

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

1class Solution:2    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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem