1.
Introduction
1.1.
Problem statement
1.2.
Sample Examples
2.
Brute-force approach
2.1.
Step of algorithm
2.2.
Implementation in C++
2.2.1.
Complexity Analysis
3.
Efficient approach
3.1.
Steps of algorithm
3.2.
Implementation in C++
3.2.1.
Complexity Analysis
4.
5.
Key Takeaways
Last Updated: Mar 27, 2024

# Sum of beauty in the array

## Introduction

### Problem statement

We are given an array of length n. Our task is to find the sum of beauty in the array of every index ( 1<= index < n-1 )

Beauty of each ith element equals, where 1 <= i < n-1,

• 2, if all the elements on the left of the ith element are smaller and all the elements on its right are greater than the ith element, a[j] < a[i] < a[k] for all 0 <= j < i < k < n
• 1, if the element just before the ith element is smaller and the element just after the ith element is greater than the ith element, a[i-1] < a[i] < a[i+1] and the previous condition is not satisfied.
• 0, if none of the previous conditions is satisfied.

### Sample Examples

Example 1:

``````Input: a[] = { 5, 7, 8, 1, 4, 9 }
Output: 2

Explanation
The beauty of a[1] = 1
The beauty of a[2] = 0
The beauty of a[3] = 0
The beauty of a[4] = 1
Sum of beauty in the array = 1 + 0 + 0 + 1 = 2``````

Example 2:

``````Input: a[] = { 6, 3, 4, 8, 2 }
Output: 1

Explanation
The beauty of a[1] = 0
The beauty of a[2] = 1
The beauty of a[3] = 0
Sum of beauty in the array = 0 + 1 + 0 = 1``````

Also see, Euclid GCD Algorithm

## Brute-force approach

For the ith element to have a beauty value of 2, it must be larger than all the elements on its left and smaller than all the elements on its right. As a result, it should be greater than the maximum of all left elements and smaller than the minimum of all the right elements.

For the beauty value of the ith element to be 1, it should firstly not satisfy the above condition, and secondly, the ith element should be greater than the (i - 1)th element and lesser than (i + 1)th element

### Step of algorithm

• For each ith element ( 1 <= i < n-1 ), traverse to its left and right.
• Create a variable ans = 0 to store the sum of beauty in the Array.
• If all elements on the left side are smaller and all elements on the right side are greater than the current element, add 2 to the ans.
• If the above condition is false and the element just before the current element is smaller, and the element just after the current element is greater than the current element, add 1 to ans.
• After checking for all the elements, return the value of ans.

Let's understand the above approach with an example:

• For a[1] = 3, it doesnâ€™t satisfy any of the above condition, beauty = 0

• For a[2] = 4, a[1] < a[2] < a[3], beauty = 1

• For a[3] = 8, it doesn't satisfy any of the above conditions, beauty = 0

### Implementation in C++

``````#include<bits/stdc++.h>
using namespace std;

int sum_of_beauty(int a[], int n)
{
int ans = 0; // stores the sum of beauty in the array

for (int i = 1; i < n - 1; i++)
{
bool flag = true;

for (int j = 0; j < i; j++) // checking left side
{
if ( a[j] >= a[i])
flag = false;
}

for (int k = i + 1; k < n; k++) // checking right side
{
if (a[k] <= a[i])
flag = false;
}

if (flag == true)
ans += 2;
else if (a[i - 1] < a[i] && a[i + 1] > a[i])
ans += 1;
}

return ans;
}

int main()
{
int a[] = { 5, 7, 8, 1, 4, 9 };

int n = sizeof(a) / sizeof(a[0]);

cout << sum_of_beauty(a, n) << endl;
}``````

Output:

``2``

#### Complexity Analysis

Time complexity: O(n^2), as we are using two nested loops, one for traversing the array and the other for checking its left and the right side, where n is the size of the given array.

Space complexity: O(1), as we are using constant extra space.

## Efficient approach

In this approach, instead of traversing its left and right side for every ith element, we will precompute the minimum element found till that index on the right side in an array, say min_right.

We also calculate the maximum element found till the current index and store it in max_left.

Now, for the ith element to have a beauty value of 2, it must be larger than max_left and smaller than min_right[i+1].

For the beauty value of the ith element to be 1, it should firstly not satisfy the above condition. Secondly, the ith element should be greater than the (i - 1)th element and lesser than (i + 1)th element.

### Steps of algorithm

• Create a min_right array of size n, traverse the array from the right end and fill with the maximum value found in the given array till that index.
• Create a max_left variable and initialise it with the first element of the given array, max_left = a[0].
• Create an ans variable to store the sum of beauty in the array, ans = 0.
• Now, traverse the array from i = 1 to i < n-1,
• If the ith element in the given array is greater than the max_left and smaller than the value of min_right[i+1], increment the ans by 2, ans = ans + 2.
• Else if the value of the ith element is greater than (i-1)th element and smaller than the (i+1)th element, increment the ans by 1,  ans = ans+1.
• Update the max_left.
• After completely traversing the given array, return the value of ans.

Let's understand the above approach with an example:

max_left = 6

• For a[1] = 3, it doesnâ€™t satisfy any of the above conditions, beauty = 0.
• For a[2] = 4, a[1] < a[2] < a[3], beauty = 1.
• For a[3] = 8, it doesnâ€™t satisfy any of the above conditions, beauty = 1 and max_left = 8.

### Implementation in C++

``````#include<bits/stdc++.h>
using namespace std;

int sum_of_beauty(int a[], int n)
{
int min_right[n];

min_right[n - 1] = a[n - 1];

for (int i = n - 2; i >= 2; i--)
{
min_right[i] = min(min_right[i + 1], a[i]);
}

int max_left = a[0];

int ans = 0;

for (int i = 1; i < n - 1; i++)
{
if (a[i] > max_left && a[i] < min_right[i + 1])
ans += 2;
else if (a[i] > a[i - 1] && a[i] < a[i + 1])
ans += 1;

max_left = max(a[i], max_left);
}

return ans;
}
int main()
{
int a[] = {6, 3, 4, 8, 2};

int n = sizeof(a) / sizeof(a[0]);

cout << sum_of_beauty(a, n) << endl;
}``````

Output:

``2``

#### Complexity Analysis

Time complexity: O(n), as we use a loop of size n to traverse the given array, where n is the size of the array.

Space complexity: O(n), as we use a min_right array to store the minimum element on the right side.

Q1. Is it possible to alter the size of an unsorted array?

Answer: No, we cannot change the size of an array after it has been created. we can either allocate it larger than we think we'll need it or accept the cost of reallocating it if it grows in size.

Q2. What is a prefix sum array, and how does it work

Answer: Prefix Sum array is a data structure that allows us to answer multiple queries in constant time, such as sum in a given range, which would otherwise take linear time. It is widely used because of its simplicity and effectiveness. It requires linear time preprocessing.

Q3. In C++, how do you find the smallest value in a list?

Answer: One variable, minElement, should be set to the first element of the inputArray. Traverse inputArray from index 0 to N -1 using a loop, comparing each element to minElement. If the current element is less than minElement, minElement should be updated to include the current element.

Q4. What is the benefit of taking a greedy approach?

Answer: The benefit of using a greedy algorithm is that solutions to smaller problem instances can be simple and straightforward. The disadvantage is that even the best short-term solutions may result in the worst possible long-term outcome.

## Key Takeaways

This article discussed the different approaches to finding the sum of beauty in the array. We first learnt the brute force approach. After that, we optimised its time complexity by using an array that stores the minimum element on the right side and their implementation in C++.

If you are an absolute beginner, interested in coding, and want to learn DSA, you can look for our guided path for DSA, which is free! If you already have some previous knowledge about the above topic, then you can try out some similar problems, such as sum of two arraysmerge K sorted arrays, etc.

To learn more about Data Structures and Algorithms, you can enroll in our DSA in C++ Course.