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 <= 1051 <= nums[i] <= 105Problem Overview: You are given an integer array nums. For every index i (excluding the first and last), you assign a beauty score based on ordering conditions with elements on the left and right. If nums[i] is strictly greater than all elements to its left and strictly smaller than all elements to its right, it contributes 2. Otherwise, if it is strictly between its immediate neighbors (nums[i-1] < nums[i] < nums[i+1]), it contributes 1. The task is to compute the total beauty across the array.
Approach 1: Naive Iterative Approach (O(n^2) time, O(1) space)
Iterate through every valid index i from 1 to n-2. For each position, scan the left portion of the array to compute the maximum value and scan the right portion to compute the minimum value. If max(left) < nums[i] < min(right), add 2 to the score. Otherwise check the local condition nums[i-1] < nums[i] < nums[i+1] and add 1 if it holds. This approach directly implements the definition but repeatedly recomputes left and right ranges, leading to quadratic time complexity.
Approach 2: Optimized Prefix and Suffix Arrays Approach (O(n) time, O(n) space)
Precompute helper arrays so each index can be evaluated in constant time. Build a prefix maximum array where prefixMax[i] stores the maximum value from index 0 to i. Build a suffix minimum array where suffixMin[i] stores the minimum value from index i to the end. When evaluating index i, check whether prefixMax[i-1] < nums[i] < suffixMin[i+1] to assign beauty 2. If that fails, check the local neighbor condition for beauty 1. Because prefix and suffix values are precomputed, each element is processed once, giving linear time.
This pattern appears often in array problems where you need information about elements on both sides of an index. Precomputing prefix maxima and suffix minima is a standard optimization also seen in prefix-based techniques and other dynamic programming style precomputation problems.
Recommended for interviews: The optimized prefix and suffix arrays approach. Interviewers expect you to recognize that repeatedly scanning the left and right sides is inefficient. Demonstrating the brute force first shows understanding of the problem definition, but moving to the O(n) precomputation solution shows algorithmic maturity and familiarity with common array optimization patterns.
This approach involves iterating through each element and checking both conditions for beauty. This involves additional nested loops for checking all elements on both sides of the current element. While intuitive, this approach leads to suboptimal performance due to multiple inner loops.
This C code iteratively calculates the beauty for each element by comparing it with all previous and next elements. This uses a nested loop for both left and right values.
Time Complexity: O(n^2) due to nested loops.
Space Complexity: O(1) as it uses constant space.
This approach enhances the previous method by precomputing prefix maximums and suffix minimums, allowing O(1) look-ups to check the main beauty condition. By avoiding nested loops, the time complexity is improved by reducing redundant computations.
This C code constructs two arrays to store prefix maxima and suffix minima. This allows for O(1) checks for each element beyond the first and last, ensuring an optimized solution.
Time Complexity: O(n), as it requires only a linear pass to fill prefix and suffix arrays.
Space Complexity: O(n), due to the additional arrays for storing prefix and suffix calculations.
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.
| Approach | Complexity |
|---|---|
| Naive Iterative Approach | Time Complexity: O(n^2) due to nested loops. |
| Optimized Prefix and Suffix Arrays Approach | Time Complexity: O(n), as it requires only a linear pass to fill prefix and suffix arrays. |
| Preprocessing Right Minimum + Traversing to Maintain Left Maximum | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Naive Iterative Approach | O(n^2) | O(1) | Useful for understanding the rules or when constraints are very small |
| Optimized Prefix and Suffix Arrays | O(n) | O(n) | Best general solution for large arrays and typical interview expectations |
Sum of Beauty in the Array | LeetCode 2012 | English • CodeClips with Abhishek Ranjan • 1,356 views views
Watch 4 more video solutions →Practice Sum of Beauty in the Array with our built-in code editor and test cases.
Practice on FleetCode