LeetCode 2012 - Sum of Beauty in the Array

LeetCode Problem 2012

Difficulty: 🟡 Medium
Topics: Array

Solution

Problem Understanding

The problem asks us to compute a "beauty" score for each element in an array nums, excluding the first and last elements. Specifically, for each index i in the range 1 <= i <= nums.length - 2, the beauty of nums[i] is determined by two conditions:

Beauty 2: nums[i] is strictly greater than every element to its left and strictly smaller than every element to its right.
Beauty 1: If the above condition fails, but nums[i] is greater than the immediate left neighbor and smaller than the immediate right neighbor.
Beauty 0: If neither condition holds.

The final result is the sum of all these beauty scores.

The input is an array of integers with at least 3 elements, each between 1 and 100,000. The output is a single integer representing the total beauty. The problem constraints indicate that a brute-force approach of comparing each element with all others on the left and right will likely be too slow, especially for arrays of size up to 10^5.

Edge cases to consider include strictly increasing or decreasing arrays, arrays where all elements are equal, and arrays where only the first or last elements are extreme values. The problem guarantees at least three elements, so we do not have to handle empty arrays or single-element arrays.

Approaches

The brute-force approach involves iterating over each valid index i and checking every element to the left and right to see if the beauty-2 condition is satisfied. If not, we check the immediate neighbors for beauty-1. While correct, this is inefficient because it requires checking potentially O(n) elements on both sides for each index i, giving an overall O(n^2) time complexity.

The key insight for an optimal solution is that we can precompute arrays to store the maximum element to the left and the minimum element to the right for each index. This allows constant-time checks for the beauty-2 condition. Checking the immediate neighbors for beauty-1 is already O(1). Using this approach reduces the time complexity to O(n).

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n^2)	O(1)	Compare each element with all elements on the left and right
Optimal	O(n)	O(n)	Precompute left-max and right-min arrays for constant-time checks

Algorithm Walkthrough

Initialize two arrays, left_max and right_min, both of length n. left_max[i] will store the maximum value among all elements to the left of index i, and right_min[i] will store the minimum value among all elements to the right of index i.
Populate left_max by iterating from left to right, updating left_max[i] = max(left_max[i - 1], nums[i - 1]). This ensures left_max[i] always holds the largest value before index i.
Populate right_min by iterating from right to left, updating right_min[i] = min(right_min[i + 1], nums[i + 1]). This ensures right_min[i] always holds the smallest value after index i.
Initialize a variable total_beauty = 0.
Iterate over all indices i from 1 to n - 2. For each i, check the beauty conditions:

If left_max[i] < nums[i] < right_min[i], increment total_beauty by 2.
Else if nums[i - 1] < nums[i] < nums[i + 1], increment total_beauty by 1.

Return total_beauty.

Why it works: Precomputing the left-max and right-min arrays ensures that we know the extreme values on either side of an index in constant time, allowing us to check the beauty-2 condition efficiently. The beauty-1 condition is checked directly with immediate neighbors, so the algorithm correctly computes the sum of beauty scores.

Python Solution

from typing import List

class Solution:
    def sumOfBeauties(self, nums: List[int]) -> int:
        n = len(nums)
        if n < 3:
            return 0

        left_max = [0] * n
        right_min = [0] * n

        left_max[0] = float('-inf')
        for i in range(1, n):
            left_max[i] = max(left_max[i - 1], nums[i - 1])

        right_min[-1] = float('inf')
        for i in range(n - 2, -1, -1):
            right_min[i] = min(right_min[i + 1], nums[i + 1])

        total_beauty = 0
        for i in range(1, n - 1):
            if left_max[i] < nums[i] < right_min[i]:
                total_beauty += 2
            elif nums[i - 1] < nums[i] < nums[i + 1]:
                total_beauty += 1

        return total_beauty

Implementation explanation: We first compute left_max and right_min arrays to store precomputed extreme values, then iterate through the array checking the two beauty conditions. Using float('-inf') and float('inf') at the edges avoids index errors. The iteration over the array accumulates the total beauty score.

Go Solution

func sumOfBeauties(nums []int) int {
    n := len(nums)
    if n < 3 {
        return 0
    }

    leftMax := make([]int, n)
    rightMin := make([]int, n)

    leftMax[0] = -1 << 31
    for i := 1; i < n; i++ {
        if nums[i-1] > leftMax[i-1] {
            leftMax[i] = nums[i-1]
        } else {
            leftMax[i] = leftMax[i-1]
        }
    }

    rightMin[n-1] = 1 << 31 - 1
    for i := n - 2; i >= 0; i-- {
        if nums[i+1] < rightMin[i+1] {
            rightMin[i] = nums[i+1]
        } else {
            rightMin[i] = rightMin[i+1]
        }
    }

    totalBeauty := 0
    for i := 1; i < n-1; i++ {
        if leftMax[i] < nums[i] && nums[i] < rightMin[i] {
            totalBeauty += 2
        } else if nums[i-1] < nums[i] && nums[i] < nums[i+1] {
            totalBeauty += 1
        }
    }

    return totalBeauty
}

Go-specific notes: Go uses slices instead of lists. Integer boundaries are set using -1 << 31 for negative infinity and 1 << 31 - 1 for positive infinity. Loops and conditional logic follow standard Go syntax.

Worked Examples

Example 1: nums = [1,2,3]

left_max = [-inf, 1, 2]
right_min = [2, 3, inf]
Index 1: left_max[1] = 1 < 2 < 3 = right_min[1] → beauty = 2
Total beauty = 2

Example 2: nums = [2,4,6,4]

left_max = [-inf, 2, 4, 6]
right_min = [4, 4, 4, inf]
Index 1: left_max[1] = 2 < 4 < 4 = right_min[1] → fails, check neighbors: 2 < 4 < 6 → beauty = 1
Index 2: left_max[2] = 4 < 6 < 4 = right_min[2] → fails, check neighbors: 4 < 6 < 4 → fails → beauty = 0
Total beauty = 1

Example 3: nums = [3,2,1]

left_max = [-inf, 3, 3]
right_min = [2, 1, inf]
Index 1: 3 < 2 < 1 → false, 3 < 2 < 1 → false
Total beauty = 0

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each element is visited a constant number of times during left_max, right_min computation, and beauty summation
Space	O(n)	Additional arrays `left_max` and `right_min` of size n

The space complexity is linear due to the precomputed arrays, but the time complexity is linear as each array is traversed only once.

Test Cases

# Basic examples
assert Solution().sumOfBeauties([1,2,3]) == 2  # beauty 2
assert Solution().sumOfBeauties([2,4,6,4]) == 1  # beauty