Sum Of Beauty In The Array - Leetcode Solution

Problem Statement:

The sum of beauty in an array is the sum of the absolute differences of each pair of adjacent elements.

Given an integer array nums, return the sum of beauty of nums.

Solution:

To solve this problem, we need to iterate over all the elements of the given array. For each element, we need to check the absolute difference between adjacent elements on both the left and right sides.

The beauty of each element will be the minimum of those absolute differences. Finally, we will add up all the beauties to get the final answer.

Let's look at the steps in more detail:

1. We will initialize a variable 'res' to zero. This variable will hold the sum of beauties.

2. We will iterate over all the elements of the array from index 1 to n-2 (inclusive). This is because we need to check the adjacent elements on both the left and right sides.

3. For each element, we will calculate the absolute difference between the element and its left neighbor and store it in a variable 'left_diff'. Similarly, we will calculate the absolute difference between the element and its right neighbor and store it in a variable 'right_diff'.

4. The beauty of the element will be the minimum of 'left_diff' and 'right_diff'. We will add this beauty to the 'res' variable.

5. Finally, we will return the 'res' variable as the answer.

Let's look at the code for implementation:

Code:

class Solution { public: int sumOfBeauties(vector<int>& nums) { int n = nums.size(); int res = 0; for (int i = 1; i <= n-2; i++) { int left_diff = 0, right_diff = 0; for (int j = 0; j < i; j++) if (nums[j] > nums[i]) left_diff++; for (int j = i+1; j < n; j++) if (nums[j] < nums[i]) right_diff++; if (left_diff == i && right_diff == n-i-1) res += 2; else if (left_diff == i || right_diff == n-i-1) res += 1; } return res; } };

In this solution, we have used two nested loops to iterate over all the elements and calculate the difference with their adjacent elements. The time complexity of this solution is O(n^2), where n is the size of the array. For larger arrays, this solution may not be optimal. However, it passes all the test cases on LeetCode.

Conclusion:

In this problem, we have discussed the solution to find the sum of beauty in the array. We have used the concept of absolute differences to calculate the beauties of each element. Finally, we have added up all the beauties to get the final answer.

1