2012. Sum of Beauty in the Array
Problem Description
In this problem, we are provided with a 0-indexed integer array nums
. We need to determine the "beauty" for each element nums[i]
at positions i
from 1
to nums.length - 2
, according to the following rules:
- The beauty is 2 if
nums[i]
is greater than all preceding elementsnums[j]
wherej < i
, and less than all succeeding elementsnums[k]
wherek > i
. - The beauty is 1 if
nums[i]
is greater than the immediate preceding elementnums[i - 1]
and less than the immediate succeeding elementnums[i + 1]
, but does not satisfy the condition for beauty 2. - The beauty is 0 if none of the above conditions is satisfied.
Our goal is to calculate the sum of beauty for all such nums[i]
.
Intuition
The solution builds on the key observation that to find the beauty of an index i
, it suffices to determine the maximum element to the left of i
and the minimum element to the right of i
. This leads us to an efficient way to evaluate the beauty for each index.
The approach is as follows:
- Create two additional arrays,
lmx
andrmi
, to record the maximum element observed from the beginning up toi - 1
and the minimum element observed from the end down toi + 1
. - Iterate through the
nums
array from left to right, populatinglmx
by recording the maximum value seen so far. - Iterate through the
nums
array from right to left, populatingrmi
with the minimum value seen so far. - Now, traverse the array again and for each
i
(from1
tonums.length - 2
), check the following:- If
lmx[i] < nums[i] < rmi[i]
, add2
to the answer sincenums[i]
satisfies the condition for beauty 2. - Else if
nums[i - 1] < nums[i] < nums[i + 1]
and the first condition is not satisfied, add1
to the answer, marking beauty 1.
- If
- Sum the beauty values calculated for each
i
to get the final answer.
Solution Approach
To implement the solution, we follow these steps, making use of sequential iterations and auxiliary space for the arrays needed to keep track of maximum and minimum boundaries:
-
Initialization:
- Calculate the length
n
of the arraynums
. - Initialize two arrays
lmx
andrmi
of sizen
to keep track of the left maximum and right minimum values, respectively.lmx[i]
will store the maximum value from the start of the array to indexi - 1
, andrmi[i]
will store the minimum value from the end of the array to indexi + 1
. lmx
is initially filled with0
because there is no number before the start of the array.rmi
is filled with a very large number,100001
, to ensure that any real number in the arraynums
will be less than this placeholder value.
- Calculate the length
-
Populate
lmx
:- Iterate through
nums
from left to right starting from index1
up ton - 1
. - Update
lmx[i]
such that it holds the maximum value seen up tonums[i - 1]
. This is done using the formulalmx[i] = max(lmx[i - 1], nums[i - 1])
.
- Iterate through
-
Populate
rmi
:- Iterate through
nums
from right to left starting from indexn - 2
down to0
. - Update
rmi[i]
such that it holds the minimum value seen fromnums[i + 1]
to the end of the array. The formula used here isrmi[i] = min(rmi[i + 1], nums[i + 1])
.
- Iterate through
-
Calculate the total beauty:
- Initialize a variable
ans
to hold the sum of beauty scores. - Iterate through the elements of
nums
from index1
ton - 2
(inclusive). - Check if the beauty of
nums[i]
is2
by comparing iflmx[i] < nums[i] < rmi[i]
. If this condition is true, incrementans
by2
. - Else if
nums[i]
does not qualify for a beauty of2
, check if it is greater than the element to its left and less than the element to its right (i.e., check ifnums[i - 1] < nums[i] < nums[i + 1]
). If true, incrementans
by1
. - If neither condition is satisfied, the beauty for that element is
0
, soans
remains the same.
- Initialize a variable
-
Return the result:
- After the loop completes,
ans
contains the sum of beauty for allnums[i]
, and we return this value.
- After the loop completes,
The main data structures used in this solution are the arrays lmx
and rmi
for dynamic programming, which store computed values that can be used to determine the beauty of each element efficiently. The algorithm makes use of max()
and min()
functions for comparisons, and a single pass through the array (ignoring the separate passes for lmx
and rmi
initializations) to calculate the sum of beauty. This approach ensures that we have all the necessary information to evaluate the beauty of each element without using nested loops, which would result in a higher computational complexity.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through a small example to illustrate the solution approach. Consider the integer array nums = [1, 2, 3, 4, 2]
.
Step 1: Initialization
n = 5
(length ofnums
)- Initialize
lmx = [0, 0, 0, 0, 0]
andrmi = [100001, 100001, 100001, 100001, 100001]
Step 2: Populate lmx
- Starting from
i = 1
, iterate toi = 4
:lmx[1] = max(0, nums[0]) = 1
lmx[2] = max(1, nums[1]) = 2
lmx[3] = max(2, nums[2]) = 3
lmx[4] = max(3, nums[3]) = 4
- Now
lmx = [0, 1, 2, 3, 4]
Step 3: Populate rmi
- Starting from
i = 3
, iterate toi = 0
:rmi[3] = min(100001, nums[4]) = 2
rmi[2] = min(2, nums[3]) = 2
rmi[1] = min(2, nums[2]) = 2
rmi[0] = min(2, nums[1]) = 2
- Now
rmi = [2, 2, 2, 2, 100001]
Step 4: Calculate the total beauty
- Initialize
ans = 0
- For
i = 1
ton - 2
:- For
i = 1
:lmx[1]
is1
,nums[1]
is2
,rmi[1]
is2
.nums[1]
is greater thanlmx[1]
but not less thanrmi[1]
, so check next condition.nums[0]
is1
,nums[1]
is2
,nums[2]
is3
. It satisfiesnums[0] < nums[1] < nums[2]
, so add1
toans
.
- For
i = 2
:lmx[2]
is2
,nums[2]
is3
,rmi[2]
is2
.nums[2]
does not satisfy any beauty conditions, soans
stays the same.
- For
i = 3
:lmx[3]
is3
,nums[3]
is4
,rmi[3]
is2
.nums[3]
is greater than bothlmx[3]
andrmi[3]
, so it adds nothing toans
.
- For
- The final value of
ans
after the loop is1
.
Step 5: Return the result
The result, which is the sum of beauty for all nums[i]
, is 1
. This is the final answer to the problem.
In this particular example, the only element to contribute to the beauty sum was nums[1]
with a beauty of 1
.
Solution Implementation
1from typing import List
2
3class Solution:
4 def sumOfBeauties(self, nums: List[int]) -> int:
5 num_elements = len(nums) # Get the number of elements in the list
6 max_left = [0] * num_elements # Initialize a list to store the maximum to the left of each position
7 min_right = [100001] * num_elements # Initialize a list to store the minimum to the right of each position
8
9 # Populate max_left by finding the maximum on the left for each position in nums
10 for i in range(1, num_elements):
11 max_left[i] = max(max_left[i - 1], nums[i - 1])
12
13 # Populate min_right by finding the minimum on the right for each position in nums
14 for i in range(num_elements - 2, -1, -1):
15 min_right[i] = min(min_right[i + 1], nums[i + 1])
16
17 beauty_sum = 0 # This variable will hold the cumulative beauty of the array
18
19 # Loop through each element of the array except the first and last
20 for i in range(1, num_elements - 1):
21 # Check if the element is greater than the max to the left and less than the min to the right
22 if max_left[i] < nums[i] < min_right[i]:
23 beauty_sum += 2 # If it is, the beauty score for this number is 2
24 # Otherwise, check if the element is greater than its previous and less than its next element
25 elif nums[i - 1] < nums[i] < nums[i + 1]:
26 beauty_sum += 1 # If so, the beauty score for this number is 1
27
28 return beauty_sum # Return the total accumulated beauty
29
1class Solution {
2 public int sumOfBeauties(int[] nums) {
3 int n = nums.length; // Get the length of the input array
4 int[] leftMax = new int[n]; // Initialize an array to keep track of maximum values from the left
5 int[] rightMin = new int[n]; // Initialize an array to keep track of minimum values from the right
6 rightMin[n - 1] = 100001; // Set the last element to a high value as a sentinel
7
8 // Fill the leftMax array with the maximum value encountered from the left up to that index
9 for (int i = 1; i < n; ++i) {
10 leftMax[i] = Math.max(leftMax[i - 1], nums[i - 1]);
11 }
12
13 // Fill the rightMin array with the minimum value encountered from the right up to that index
14 for (int i = n - 2; i >= 0; --i) {
15 rightMin[i] = Math.min(rightMin[i + 1], nums[i + 1]);
16 }
17
18 int totalBeauty = 0; // Variable to hold the total sum of beauty
19 // Loop through the array, omitting the first and last element
20 for (int i = 1; i < n - 1; ++i) {
21 // Check if the current element is larger than the maximum to its left and smaller than the minimum to its right
22 if (leftMax[i] < nums[i] && nums[i] < rightMin[i]) {
23 totalBeauty += 2; // Add 2 to beauty as it satisfies the special condition
24 } else if (nums[i - 1] < nums[i] && nums[i] < nums[i + 1]) {
25 totalBeauty += 1; // Add 1 to beauty if it's simply larger than its adjacent elements
26 }
27 }
28 // Return the sum of beauty of all elements
29 return totalBeauty;
30 }
31}
32
1class Solution {
2public:
3 int sumOfBeauties(vector<int>& nums) {
4 int size = nums.size();
5 vector<int> leftMax(size); // Stores the maximum to the left of each element.
6 vector<int> rightMin(size, 100001); // Stores the minimum to the right of each element, initially set high
7
8 // Populate leftMax by keeping track of the maximum number seen so far from the left.
9 for (int i = 1; i < size; ++i) {
10 leftMax[i] = max(leftMax[i - 1], nums[i - 1]);
11 }
12
13 // Populate rightMin by keeping track of the minimum number seen so far from the right.
14 for (int i = size - 2; i >= 0; --i) {
15 rightMin[i] = min(rightMin[i + 1], nums[i + 1]);
16 }
17
18 int totalBeauty = 0; // This will store the total beauty of the array.
19
20 // Calculate the beauty for each number in the array excluding the first and last element.
21 for (int i = 1; i < size - 1; ++i) {
22 // If the current element is greater than the maximum on its left
23 // and less than the minimum on its right, add 2 to total beauty.
24 if (leftMax[i] < nums[i] && nums[i] < rightMin[i]) {
25 totalBeauty += 2;
26 }
27 // If it doesn't meet the first condition but is still increasing with respect
28 // to its immediate neighbors, add 1 to total beauty.
29 else if (nums[i - 1] < nums[i] && nums[i] < nums[i + 1]) {
30 totalBeauty += 1;
31 }
32 }
33
34 // Return the total beauty of the array.
35 return totalBeauty;
36 }
37};
38
1// Function to calculate the sum of beauties for all elements in the array except the first and last.
2function sumOfBeauties(nums: number[]): number {
3 // Determine the length of input array.
4 let n: number = nums.length;
5 // Initialize prefix and postfix arrays to keep track of max and min values seen so far from either end.
6 let prefixMax: number[] = new Array(n).fill(0);
7 let postfixMin: number[] = new Array(n).fill(0);
8
9 // Set the first element of prefix and the last element of postfix to be the corresponding values from 'nums'.
10 prefixMax[0] = nums[0];
11 postfixMin[n - 1] = nums[n - 1];
12
13 // Fill the prefixMax and postfixMin arrays.
14 for (let i: number = 1, j: number = n - 2; i < n; ++i, --j) {
15 prefixMax[i] = Math.max(nums[i], prefixMax[i - 1]);
16 postfixMin[j] = Math.min(nums[j], postfixMin[j + 1]);
17 }
18
19 // Initialize the sum of beauties.
20 let sumOfBeautyPoints: number = 0;
21
22 // Check the beauty for each element, based on the conditions and update the sum accordingly.
23 for (let i: number = 1; i < n - 1; ++i) {
24 // Check for beauty level 2 condition.
25 if (prefixMax[i - 1] < nums[i] && nums[i] < postfixMin[i + 1]) {
26 sumOfBeautyPoints += 2;
27 // Check for beauty level 1 condition.
28 } else if (nums[i - 1] < nums[i] && nums[i] < nums[i + 1]) {
29 sumOfBeautyPoints += 1;
30 }
31 }
32
33 // Return the total sum of beauty points.
34 return sumOfBeautyPoints;
35}
36
Time and Space Complexity
Time Complexity
The given code consists of three separate for
loops that are not nested. Each of these loops runs linearly with respect to the length of the input array nums
, which is denoted as n
.
- The first loop initializes the
lmx
array, which takesO(n)
time as it iterates from1
ton-1
. - The second loop initializes the
rmi
array, which also takesO(n)
time as it iterates fromn-2
to0
. - The third loop calculates the
ans
(answer) by iterating once again in linear time over the range from1
ton-1
, resulting inO(n)
time.
When we add these up, since they are executed in sequence and not nested, the overall time complexity of the code is O(n) + O(n) + O(n)
, which simplifies to O(n)
.
Space Complexity
The space complexity of the code is due to the additional arrays lmx
and rmi
that are both of length n
, and the space used for variables like n
, i
, and ans
.
- The
lmx
array usesO(n)
space. - The
rmi
array also usesO(n)
space.
Besides these arrays, only a constant amount of extra space is used for the loop indices and the ans
variable. Thus, the total auxiliary space used by the algorithm is O(n)
+ O(n)
which simplifies to O(n)
.
In conclusion, the time complexity of the algorithm is O(n)
and the space complexity is O(n)
.
Learn more about how to find time and space complexity quickly using problem constraints.
Which of these pictures shows the visit order of a depth-first search?
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.