Sum of Beauty in the Array solution and explanation
3 more videos on this problem
Sum of Beauty in the Array | LeetCode 2012 | EnglishCodeClips with Abhishek Ranjan · 10:13 · 1K views
2012 Sum of Beauty in the Array LeetCodeAnimated Anand · 7:06 · 1K views
2012. Sum of Beauty in the Array (Leetcode Medium)Programming Live with Larry · 8:05 · 995 views
Leetcode 2012. Sum of Beauty in the Array (Weekly Contest 259 Q2)Yinghua Hu · 20:48 · 176 views
The 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, ifnums[j] < nums[i] < nums[k], for all0 <= j < iand for alli < k <= nums.length - 1.1, ifnums[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] <= 105
Approach overview
Problem 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.
Approach 1: Naive Iterative Approach
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.
def sum_of_beauty(nums):
sum_beauty = 0
for i in range(1, len(nums) - 1):
max_left = max(nums[:i])
min_right = min(nums[i+1:])
if nums[i] > max_left and nums[i] < min_right:
sum_beauty += 2
elif nums[i - 1] < nums[i] < nums[i + 1]:
sum_beauty += 1
return sum_beauty
nums = [2, 4, 6, 4]
print("Sum of Beauty:", sum_of_beauty(nums))public class Solution {
public int sumOfBeauty(int[] nums) {
int sumBeauty = 0;
int n = nums.length;
for (int i = 1; i < n - 1; i++) {
int maxLeft = nums[0];
for (int j = 0; j < i; j++) {
maxLeft = Math.max(maxLeft, nums[j]);
}
int minRight = nums[i + 1];
for (int k = i + 1; k < n; k++) {
minRight = Math.min(minRight, nums[k]);
}
if (nums[i] > maxLeft && nums[i] < minRight) {
sumBeauty += 2;
} else if (nums[i - 1] < nums[i] && nums[i] < nums[i + 1]) {
sumBeauty += 1;
}
}
return sumBeauty;
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] nums = {2, 4, 6, 4};
System.out.println("Sum of Beauty: " + sol.sumOfBeauty(nums));
}
}#include <iostream>
#include <vector>
int sumOfBeauty(std::vector<int>& nums) {
int sumBeauty = 0;
int n = nums.size();
for (int i = 1; i < n - 1; ++i) {
int maxLeft = nums[0];
for (int j = 0; j < i; ++j) {
maxLeft = std::max(maxLeft, nums[j]);
}
int minRight = nums[i + 1];
for (int k = i + 1; k < n; ++k) {
minRight = std::min(minRight, nums[k]);
}
if (nums[i] > maxLeft && nums[i] < minRight) {
sumBeauty += 2;
} else if (nums[i - 1] < nums[i] && nums[i] < nums[i + 1]) {
sumBeauty += 1;
}
}
return sumBeauty;
}
int main() {
std::vector<int> nums = {2, 4, 6, 4};
std::cout << "Sum of Beauty: " << sumOfBeauty(nums) << std::endl;
return 0;
}function sumOfBeauty(nums) {
let sumBeauty = 0;
for (let i = 1; i < nums.length - 1; i++) {
let maxLeft = Math.max(...nums.slice(0, i));
let minRight = Math.min(...nums.slice(i + 1));
if (nums[i] > maxLeft && nums[i] < minRight) {
sumBeauty += 2;
} else if (nums[i - 1] < nums[i] && nums[i] < nums[i + 1]) {
sumBeauty += 1;
}
}
return sumBeauty;
}
console.log("Sum of Beauty:", sumOfBeauty([2, 4, 6, 4]));#include <stdio.h>
int sumOfBeauty(int* nums, int numsSize) {
int sumBeauty = 0;
for (int i = 1; i < numsSize - 1; ++i) {
int maxLeft = nums[0];
for (int j = 0; j < i; ++j) {
if (nums[j] > maxLeft) maxLeft = nums[j];
}
int minRight = nums[i + 1];
for (int k = i + 1; k < numsSize; ++k) {
if (nums[k] < minRight) minRight = nums[k];
}
if (nums[i] > maxLeft && nums[i] < minRight) {
sumBeauty += 2;
} else if (nums[i - 1] < nums[i] && nums[i] < nums[i + 1]) {
sumBeauty += 1;
}
}
return sumBeauty;
}
int main() {
int nums[] = {2,4,6,4};
int numsSize = sizeof(nums) / sizeof(nums[0]);
printf("Sum of Beauty: %d\n", sumOfBeauty(nums, numsSize));
return 0;
}using System;
public class Solution {
public int SumOfBeauty(int[] nums) {
int sumBeauty = 0;
int n = nums.Length;
for (int i = 1; i < n - 1; i++) {
int maxLeft = nums[0];
for (int j = 0; j < i; j++) {
maxLeft = Math.Max(maxLeft, nums[j]);
}
int minRight = nums[i + 1];
for (int k = i + 1; k < n; k++) {
minRight = Math.Min(minRight, nums[k]);
}
if (nums[i] > maxLeft && nums[i] < minRight) {
sumBeauty += 2;
} else if (nums[i - 1] < nums[i] && nums[i] < nums[i + 1]) {
sumBeauty += 1;
}
}
return sumBeauty;
}
public static void Main() {
int[] nums = new[] {2, 4, 6, 4};
Console.WriteLine("Sum of Beauty: " + new Solution().SumOfBeauty(nums));
}
}This Python solution employs slicing and built-in functions to compute max and min on sections of the list, keeping the solution concise.
Time Complexity: O(n^2).
Space Complexity: O(1) but with some overhead due to slicing.
Approach 2: Optimized Prefix and Suffix Arrays Approach
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.
def sum_of_beauty(nums):
n = len(nums)
max_prefix = [0] * n
min_suffix = [0] * n
sum_beauty = 0
max_prefix[0] = nums[0]
for i in range(1, n):
max_prefix[i] = max(max_prefix[i-1], nums[i])
min_suffix[n-1] = nums[n-1]
for i in range(n-2, -1, -1):
min_suffix[i] = min(min_suffix[i+1], nums[i])
for i in range(1, n-1):
if nums[i] > max_prefix[i-1] and nums[i] < min_suffix[i+1]:
sum_beauty += 2
elif nums[i-1] < nums[i] < nums[i+1]:
sum_beauty += 1
return sum_beauty
nums = [2, 4, 6, 4]
print("Sum of Beauty:", sum_of_beauty(nums))public class Solution {
public int sumOfBeauty(int[] nums) {
int n = nums.length;
int[] maxPrefix = new int[n];
int[] minSuffix = new int[n];
int sumBeauty = 0;
maxPrefix[0] = nums[0];
for (int i = 1; i < n; i++) {
maxPrefix[i] = Math.max(maxPrefix[i-1], nums[i]);
}
minSuffix[n-1] = nums[n-1];
for (int i = n - 2; i >= 0; i--) {
minSuffix[i] = Math.min(minSuffix[i+1], nums[i]);
}
for (int i = 1; i < n - 1; i++) {
if (nums[i] > maxPrefix[i-1] && nums[i] < minSuffix[i+1]) {
sumBeauty += 2;
} else if (nums[i - 1] < nums[i] && nums[i] < nums[i + 1]) {
sumBeauty += 1;
}
}
return sumBeauty;
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] nums = {2, 4, 6, 4};
System.out.println("Sum of Beauty: " + sol.sumOfBeauty(nums));
}
}#include <iostream>
#include <vector>
#include <algorithm>
int sumOfBeauty(std::vector<int>& nums) {
int sumBeauty = 0;
int n = nums.size();
std::vector<int> maxPrefix(n), minSuffix(n);
maxPrefix[0] = nums[0];
for (int i = 1; i < n; ++i) {
maxPrefix[i] = std::max(maxPrefix[i-1], nums[i]);
}
minSuffix[n-1] = nums[n-1];
for (int i = n - 2; i >= 0; --i) {
minSuffix[i] = std::min(minSuffix[i+1], nums[i]);
}
for (int i = 1; i < n - 1; ++i) {
if (nums[i] > maxPrefix[i-1] && nums[i] < minSuffix[i+1]) {
sumBeauty += 2;
} else if (nums[i - 1] < nums[i] && nums[i] < nums[i + 1]) {
sumBeauty += 1;
}
}
return sumBeauty;
}
int main() {
std::vector<int> nums = {2, 4, 6, 4};
std::cout << "Sum of Beauty: " << sumOfBeauty(nums) << std::endl;
return 0;
}function sumOfBeauty(nums) {
const n = nums.length;
const maxPrefix = new Array(n);
const minSuffix = new Array(n);
let sumBeauty = 0;
maxPrefix[0] = nums[0];
for (let i = 1; i < n; i++) {
maxPrefix[i] = Math.max(maxPrefix[i-1], nums[i]);
}
minSuffix[n-1] = nums[n-1];
for (let i = n - 2; i >= 0; i--) {
minSuffix[i] = Math.min(minSuffix[i+1], nums[i]);
}
for (let i = 1; i < n - 1; i++) {
if (nums[i] > maxPrefix[i-1] && nums[i] < minSuffix[i+1]) {
sumBeauty += 2;
} else if (nums[i-1] < nums[i] && nums[i] < nums[i+1]) {
sumBeauty += 1;
}
}
return sumBeauty;
}
console.log("Sum of Beauty:", sumOfBeauty([2, 4, 6, 4]));#include <stdio.h>
int sumOfBeauty(int* nums, int numsSize) {
int sumBeauty = 0;
int maxPrefix[numsSize];
int minSuffix[numsSize];
maxPrefix[0] = nums[0];
for (int i = 1; i < numsSize; ++i) {
maxPrefix[i] = (nums[i] > maxPrefix[i-1]) ? nums[i] : maxPrefix[i-1];
}
minSuffix[numsSize-1] = nums[numsSize-1];
for (int i = numsSize - 2; i >= 0; --i) {
minSuffix[i] = (nums[i] < minSuffix[i+1]) ? nums[i] : minSuffix[i+1];
}
for (int i = 1; i < numsSize - 1; ++i) {
if (nums[i] > maxPrefix[i-1] && nums[i] < minSuffix[i+1]) {
sumBeauty += 2;
} else if (nums[i - 1] < nums[i] && nums[i] < nums[i + 1]) {
sumBeauty += 1;
}
}
return sumBeauty;
}
int main() {
int nums[] = {2,4,6,4};
int numsSize = sizeof(nums) / sizeof(nums[0]);
printf("Sum of Beauty: %d\n", sumOfBeauty(nums, numsSize));
return 0;
}using System;
public class Solution {
public int SumOfBeauty(int[] nums) {
int n = nums.Length;
int[] maxPrefix = new int[n];
int[] minSuffix = new int[n];
int sumBeauty = 0;
maxPrefix[0] = nums[0];
for (int i = 1; i < n; i++) {
maxPrefix[i] = Math.Max(maxPrefix[i-1], nums[i]);
}
minSuffix[n-1] = nums[n-1];
for (int i = n - 2; i >= 0; i--) {
minSuffix[i] = Math.Min(minSuffix[i+1], nums[i]);
}
for (int i = 1; i < n - 1; i++) {
if (nums[i] > maxPrefix[i-1] && nums[i] < minSuffix[i+1]) {
sumBeauty += 2;
} else if (nums[i - 1] < nums[i] && nums[i] < nums[i + 1]) {
sumBeauty += 1;
}
}
return sumBeauty;
}
public static void Main() {
int[] nums = {2, 4, 6, 4};
Console.WriteLine("Sum of Beauty: " + new Solution().SumOfBeauty(nums));
}
}Utilizing two arrays for precomputed maxima and minima, this Python solution efficiently determines beauty using constant checks.
Time Complexity: O(n).
Space Complexity: O(n).
Approach 3: Preprocessing Right Minimum + Traversing to Maintain Left Maximum
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.
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;
}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
}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
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Naive Iterative Approach | Time Complexity: O(n^2). |
| Optimized Prefix and Suffix Arrays Approach | Time Complexity: O(n). |
| Preprocessing Right Minimum + Traversing to Maintain Left Maximum | – |
Complexity analysis
| 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 |
Frequently asked questions
Is Sum of Beauty in the Array easy or hard?
The problem is rated Medium because the rules themselves are simple but recognizing the prefix and suffix optimization is the key challenge. Candidates who attempt brute force first often realize the inefficiency and then improve it to an O(n) solution.
Sum of Beauty in the Array Python/Java solution
Most implementations build prefixMax and suffixMin arrays and then iterate once through the array to accumulate the beauty score. The same algorithm works across languages such as Python, Java, C++, and JavaScript because it relies only on array traversal and simple comparisons.
How to solve Sum of Beauty in the Array in O(n)?
Create a prefix array where prefixMax[i] stores the maximum value from index 0 to i, and a suffix array where suffixMin[i] stores the minimum value from i to the end. For each index i from 1 to n-2, check if prefixMax[i-1] < nums[i] < suffixMin[i+1] to add 2 beauty points. If that condition fails, check the local ordering nums[i-1] < nums[i] < nums[i+1] to add 1 point.
What is the best approach for Sum of Beauty in the Array?
The most efficient solution uses prefix maximum and suffix minimum arrays. Precompute the maximum value to the left of every index and the minimum value to the right, then evaluate each element in constant time. This reduces repeated scanning and gives an overall O(n) time complexity with O(n) extra space.
Is Sum of Beauty in the Array asked at Google/Amazon/Meta?
Array scanning and prefix-suffix precomputation patterns commonly appear in interviews at companies like Google, Amazon, and Meta. While the exact problem may vary, recognizing how to maintain left-side maximums and right-side minimums is a common interview expectation.
What data structure is used in Sum of Beauty in the Array?
The main data structures are arrays used for prefix maximum and suffix minimum precomputation. These helper arrays allow constant-time lookups of the largest value on the left and the smallest value on the right for each index.
What is the time complexity of Sum of Beauty in the Array?
The optimal solution runs in O(n) time by precomputing prefix maximum and suffix minimum arrays and then scanning the array once more to compute beauty values. A straightforward brute force implementation takes O(n^2) time because it scans the left and right sides for every index.