Sum of Beauty in the Array

LeetCode 2138 | Difficulty: Medium

Medium

Problem 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^5`

- `1 <= nums[i] <= 10^5`

Topics: Array

---

Solutions

Solution 1: C# (Best: 495 ms)

Metric	Value
Runtime	495 ms
Memory	47.6 MB
Date	2021-09-20

Solution

public class Solution {
    public int SumOfBeauties(int[] nums) {
        int n = nums.Length;
    int beautiesSum = 0;
    int[] maxSoFar = new int[n];
    int[] minFromHere = new int[n];
    maxSoFar[0] = nums[0];
    minFromHere[n - 1] = nums[n - 1];

    for (int i = 1; i < nums.Length; i++)
    {
        maxSoFar[i] = Math.Max(maxSoFar[i - 1], nums[i]);
    }

    for (int i = n - 2; i >= 0; i--)
    {
        minFromHere[i] = Math.Min(nums[i], minFromHere[i + 1]);
    }
    for (int i = 1; i < n - 1; i++)
    {
        // add 2 if the max upto i-1 is less than nums[i] and min from i+1 to the end is less than i
        if (maxSoFar[i - 1] < nums[i] && minFromHere[i + 1] > nums[i])
        {
            beautiesSum += 2;
        }
        else if (nums[i - 1] < nums[i] && nums[i] < nums[i + 1])
        {
            beautiesSum++;
        }
    }
    return beautiesSum;
    }
}

---

Complexity Analysis

Approach	Time	Space
Solution	$O(n)$	$O(1) to O(n)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.
• LeetCode provides 3 hint(s) for this problem — try solving without them first.

💡 Hints

Hint 1: Use suffix/prefix arrays.

Hint 2: prefix[i] records the maximum value in range (0, i - 1) inclusive.

Hint 3: suffix[i] records the minimum value in range (i + 1, n - 1) inclusive.