Sum of Beauty in the Array

MEDIUM

Description

You are given a 0-indexed integer array nums. For each index i (1 <= i <= nums.length - 2) the beauty of nums[i] equals:

2, if nums[j] < nums[i] < nums[k], for all 0 <= j < i and for all i < k <= nums.length - 1.
1, if nums[i - 1] < nums[i] < nums[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: nums = [1,2,3]
Output: 2
Explanation: For each index i in the range 1 <= i <= 1:
- The beauty of nums[1] equals 2.

Example 2:

Input: nums = [2,4,6,4]
Output: 1
Explanation: For each index i in the range 1 <= i <= 2:
- The beauty of nums[1] equals 1.
- The beauty of nums[2] equals 0.

Example 3:

Input: nums = [3,2,1]
Output: 0
Explanation: For each index i in the range 1 <= i <= 1:
- The beauty of nums[1] equals 0.

Constraints:

3 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁵

Approaches

Checkout 2 different approaches to solve Sum of Beauty in the Array. Click on different approaches to view the approach and algorithm in detail.

Brute Force Iteration

This approach directly translates the problem statement into code. We iterate through each possible index i (from 1 to n-2) and, for each i, we check the conditions for beauty scores of 2, 1, and 0 in that specific order by scanning the left and right subarrays.

Algorithm

Initialize a variable totalBeauty to 0.
Loop through the array with an index i from 1 to nums.length - 2.
Inside the loop, for each nums[i]:
- Check for beauty 2:
  - Find the maximum element in the subarray nums[0...i-1] by iterating from j = 0 to i-1.
  - Find the minimum element in the subarray nums[i+1...n-1] by iterating from k = i+1 to n-1.
  - If nums[i] is strictly greater than the found maximum and strictly less than the found minimum, add 2 to totalBeauty and continue to the next i.
- Check for beauty 1:
  - If the condition for beauty 2 is not met, check if nums[i-1] < nums[i] < nums[i+1].
  - If this local condition is true, add 1 to totalBeauty.
After the loop finishes, return totalBeauty.

The brute-force method involves a straightforward iteration through the relevant indices of the array. For each index i from 1 to n-2, we perform the checks as described in the problem.

Check for beauty of 2: We need to verify that nums[i] is greater than every element before it and smaller than every element after it. This is done by two separate inner loops. The first inner loop finds the maximum element in nums[0...i-1], and the second finds the minimum in nums[i+1...n-1]. If nums[i] satisfies the condition, we add 2 to our total sum.
Check for beauty of 1: If the first condition is not met, we proceed to check the simpler, local condition: nums[i-1] < nums[i] < nums[i+1]. If this holds, we add 1 to the sum.
Beauty of 0: If neither of the above conditions is true, the beauty is 0, and we add nothing.

This process is repeated for all applicable indices.

class Solution {
    public int sumOfBeauties(int[] nums) {
        int n = nums.length;
        int totalBeauty = 0;

        for (int i = 1; i < n - 1; i++) {
            // Find max on the left
            int maxLeft = 0;
            for (int j = 0; j < i; j++) {
                maxLeft = Math.max(maxLeft, nums[j]);
            }

            // Find min on the right
            int minRight = 100001; // Constraint: nums[i] <= 10^5
            for (int k = i + 1; k < n; k++) {
                minRight = Math.min(minRight, nums[k]);
            }

            if (maxLeft < nums[i] && nums[i] < minRight) {
                totalBeauty += 2;
            } else if (nums[i - 1] < nums[i] && nums[i] < nums[i + 1]) {
                totalBeauty += 1;
            }
        }
        return totalBeauty;
    }
}

Complexity Analysis

Time Complexity: O(n^2) - The outer loop runs `n-2` times. Inside this loop, we iterate up to `i` times to find the left maximum and `n-1-i` times to find the right minimum. In total, the inner operations take O(n) time. Therefore, the total time complexity is O(n) * O(n) = O(n^2).Space Complexity: O(1) - We only use a few variables to store the running sum, loop indices, and temporary max/min values. The space used does not depend on the size of the input array.

Pros and Cons

Pros:

Simple to understand and implement directly from the problem definition.
Uses constant extra space, making it memory efficient.

Cons:

Highly inefficient due to nested loops and redundant calculations.
Will likely result in a 'Time Limit Exceeded' (TLE) error for large inputs as specified in the constraints.

Code Solutions

Checking out 3 solutions in different languages for Sum of Beauty in the Array. Click on different languages to view the code.

class Solution {
public
  int sumOfBeauties(int[] nums) {
    int n = nums.length;
    int[] right = new int[n];
    right[n - 1] = nums[n - 1];
    for (int i = n - 2; i > 0; --i) {
      right[i] = Math.min(right[i + 1], nums[i]);
    }
    int ans = 0;
    int l = nums[0];
    for (int i = 1; i < n - 1; ++i) {
      int r = right[i + 1];
      if (l < nums[i] && nums[i] < r) {
        ans += 2;
      } else if (nums[i - 1] < nums[i] && nums[i] < nums[i + 1]) {
        ans += 1;
      }
      l = Math.max(l, nums[i]);
    }
    return ans;
  }
}

Video Solution

Watch the video walkthrough for Sum of Beauty in the Array

Data Structures:

Array