Sum of Beauty in the Array - Solution & Explanation

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

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

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

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

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

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

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

MediumArray18 min readAsked at: Amazon

Practice this problem

Problem Statement

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⁵

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.

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.

Code

C C++Java Python C#JavaScript

C++

Java

Python

JavaScript

Complexity

Time Complexity: O(n^2) due to nested loops.
Space Complexity: O(1) as it uses constant space.

Try this approach in the editor →

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.

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.

Code

C C++Java Python C#JavaScript

C++

Java

Python

JavaScript

Complexity

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.

Try this approach in the editor →

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.

Code

Python Java C++Go TypeScript Rust

Python

Java

C++

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

Approach	Complexity
Naive Iterative Approach	Time Complexity: O(n^2) due to nested loops. Space Complexity: O(1) as it uses constant space.
Optimized Prefix and Suffix Arrays Approach	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.
Preprocessing Right Minimum + Traversing to Maintain Left Maximum	—

Detailed 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

Video Solution

Sum of Beauty in the Array | LeetCode 2012 | English • CodeClips with Abhishek Ranjan • 1,390 views views

Watch 3 more video solutions →

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.

Ready to solve this problem?

Practice Sum of Beauty in the Array with our built-in code editor and test cases.

Practice on FleetCode

Best Time to Buy and Sell Stock

Maximum Value of an Ordered Triplet II

Problem Info

DifficultyMedium

Acceptance51.8%

Approaches3

Reading time18 min

Asked at

Amazon

Practice this problem

Open in Editor

Problem Statement

Approach Overview

Approach 1: Naive Iterative Approach

Code

Complexity

Approach 2: Optimized Prefix and Suffix Arrays Approach

Code

Complexity

Approach 3: Preprocessing Right Minimum + Traversing to Maintain Left Maximum

Code

Complexity Comparison

Detailed Complexity Analysis

Video Solution

Frequently Asked Questions

Related Problems

Ready to solve this problem?

Problem Info

Table of Contents