Sum of Beauty in The Array in Java
You are given a 0-indexed integer array arr. For each index i (1 <= i <= arr.length - 2) the beauty of arr[i] equals:
2, if arr[j] < arr[i] < arr[k], for all 0 <= j < i and for all i < k <= arr.length - 1.
1, if arr[i - 1] < arr[i] < arr[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: arr[] = [4,5,6]
Output: 2
Explanation: In the arr array we have 3 elements and elements are in decreasing order hence it satisfies the rule 1 which is arr[j] < arr[i] < arr[k] for all 0 <= j < i and i < k <= arr.length – 1. So the answer is 3.
Example 2:
Input: arr[] = [7,4,2]
Output: 0
Explanation: The following do not follow any of the above rules of the beauty number so it’s beauty sum is 0.
Brute Force Approach
In this approach, The total sum of beauty in the array is calculated by iterating through each element of the array and calculating if it satisfies the conditions for beauty scores of 2 and 1. It does this by comparing each element with all elements that come before and after it and updating the sum accordingly.
FileName: SumofBeautyArray.java
public class SumofBeautyArray {
public int sumOfBeauties(int[] nums) {
int sum = 0;
int n = nums.length;
for (int i = 1; i < n - 1; i++) {
int beauty = 0;
for (int j = 0; j < i; j++) {
boolean condition1 = true;
for (int k = i + 1; k < n; k++) {
if (!(nums[j] < nums[i] && nums[i] < nums[k])) {
condition1 = false;
break;
}
}
if (condition1) {
beauty = 2;
break;
}
}
// checking the condition for the beauty of the number
if (beauty == 0 && nums[i] > nums[i - 1] && nums[i] < nums[i + 1]) {
beauty = 1;
}
sum += beauty;
}
return sum;
}
public static void main(String[] args) {
int[] arr = {2, 4, 6, 4};
SumofBeautyArray obj = new SumofBeautyArray();
int sumOfBeauty = obj.sumOfBeauties(arr);
System.out.println("Sum of beauty: " + sumOfBeauty);
}
}
Output:
Sum of beauty : 1
Complexity Analysis:
Time Complexity: The outer loop performs O(n) iterations, where n is the length of the input array, by iterating through each element of the array once. For every outer loop iteration, the inner loop iterates through every element that comes before and after the current element, producing an O(n) number of iterations. overall time complexity is O(n^3).
Space Complexity: O(1) – Constant Space.
Prefix and Suffix Approach
In this approach calculates the maximum element up to each index and the minimum element from each index to the end of the array, respectively, in an efficient manner by using prefix and suffix arrays. The beauty scores are then determined by iterating through the array once using the prefix and suffix arrays that have been generated, and the total beauty scores are returned.
FileName : SumofBeautyArray1.java
public class SumofBeautyArray1 {
public int sumOfBeauties(int[] nums) {
int n = nums.length;
// prefix array and suffix array
int[] prefixMax = new int[n];
int[] suffixMin = new int[n];
prefixMax[0] = nums[0];
for (int i = 1; i < n; i++) {
// maximum of elements in the range
prefixMax[i] = Math.max(prefixMax[i - 1], nums[i]);
}
suffixMin[n - 1] = nums[n - 1];
for (int i = n - 2; i >= 0; i--) {
suffixMin[i] = Math.min(suffixMin[i + 1], nums[i]);
}
int sum = 0;
for (int i = 1; i < n - 1; i++) {
if (prefixMax[i - 1] < nums[i] && nums[i] < suffixMin[i + 1]) {
sum += 2;
} else if (nums[i - 1] < nums[i] && nums[i] < nums[i + 1]) {
sum += 1;
}
}
return sum;
}
public static void main(String[] args) {
int[] arr = {2, 4, 6, 4};
SumofBeautyArray1 obj = new SumofBeautyArray1();
int sumOfBeauty = obj.sumOfBeauties(arr);
System.out.println("Sum of beauty: " + sumOfBeauty);
}
}
Output:
Sum of beauty : 1
Complexity Analysis:
Time Complexity: O(n) , where n is the length of the array.
Space Complexity : O(n), where n is the length of the array.
Approach: Using Stack
In this approach, we keep track of possible candidates for the middle element and utilize a stack to efficiently discover elements with beauty score 2. The beauty scores are then determined by looking at the features on each candidate's left and right. Lastly, it returns the total after adding up each element's beauty score.
FileName: BeautyCalulator.java
import java.util.Stack;
public class BeautyCalculator {
public int sumOfBeauties(int[] nums) {
int n = nums.length;
Stack<Integer> stack = new Stack<>();
int sum = 0;
for (int i = 0; i < n; i++) {
while (!stack.isEmpty() && nums[i] > nums[stack.peek()]) {
int idx = stack.pop();
if (!stack.isEmpty() && nums[idx] > nums[stack.peek()]) {
sum += 2; // Current element has beauty score 2
} else {
sum += 1; // Current element has beauty score 1
}
}
stack.push(i);
}
return sum;
}
public static void main(String[] args) {
int[] arr = {2, 3, 4};
BeautyCalculator calculator = new BeautyCalculator();
int sumOfBeauty = calculator.sumOfBeauties(arr);
System.out.println("Sum of beauty: " + sumOfBeauty);
}
}
Output:
Sum of beauty : 2
Complexity Analysis:
Time Complexity: O(n), Where n is the number of elements in the array
Space Complexity: O(n), Where n is the number of elements in the array