Sum of beauty in the array

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.

Frequently Asked Questions

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 arrays, merge K sorted arrays, etc.

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

Thank you for reading!