Scale Engineer

Sum of Beauty in the Array

Med
#1832Time: 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: 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.
Data structures
Array

Prompt

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 <= 105
  • 1 <= nums[i] <= 105

Approaches

2 approaches with complexity analysis and trade-offs.

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.

Walkthrough

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.

  1. 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.

  2. 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.

  3. 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

Time

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

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.

Trade-offs

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.

Solutions

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 walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem