Jobs

Interviews

Discussions

Sum of Beauty in the Array

Medium

Asked by:

3 views

Topics:

Arrays

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⁵

Try coding it in LeetCode

Sum of Beauty in the Array

Medium

Asked by:

3 views

Topics:

Arrays

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⁵

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for the numbers in the array? Can they be negative?
What is the maximum size of the array, and should I be concerned about potential integer overflow issues when calculating the sum?
What should I return if the array is empty or has fewer than three elements?
Are duplicate values allowed in the array, and if so, how do they affect the definition of 'beauty'?
Could you provide a few examples of the array and the expected beauty sum to clarify the problem definition?

Brute Force Solution

Approach

We're trying to find the 'beauty' of each number in a list based on its neighbors. The brute force method just checks every number in the list and directly calculates its beauty based on examining all possible smaller and larger neighboring numbers.

Here's how the algorithm would work step-by-step:

Look at the very first number in the list.
Find the smallest number among all the numbers that come before it.
Find the largest number among all the numbers that come after it.
Decide how 'beautiful' the first number is based on these smallest and largest neighboring values according to the beauty rules.
Write down how beautiful the first number is.
Repeat this process for the second number in the list, then the third, and so on, until you've looked at every number.
Finally, add up all the beauty scores you wrote down to get the total beauty.

Code Implementation

def sum_of_beauty_brute_force(numbers):
    total_beauty = 0
    list_length = len(numbers)

    for current_index in range(list_length):
        current_number = numbers[current_index]

        # Find the maximum number to the left
        maximum_left = -1
        for left_index in range(current_index):
            maximum_left = max(maximum_left, numbers[left_index])

        # Find the minimum number to the right
        minimum_right = 100001  
        for right_index in range(current_index + 1, list_length):
            minimum_right = min(minimum_right, numbers[right_index])

        beauty_value = 0
        # Determine beauty value according to the conditions
        if maximum_left < current_number < minimum_right:
            beauty_value = 1
        elif current_number > maximum_left and current_number > minimum_right:
            beauty_value = 0

        total_beauty += beauty_value

    return total_beauty

Big(O) Analysis

Time Complexity

O(n²) – For each of the n elements in the array, we iterate through all preceding elements to find the maximum value before the element and all succeeding elements to find the minimum value after the element. Finding the maximum preceding element requires examining at most n-1 elements. Similarly, finding the minimum succeeding element requires examining at most n-1 elements. Therefore, for each of the n elements, we potentially perform 2*(n-1) operations, leading to approximately n * 2n operations, which simplifies to O(n²).

Space Complexity

O(1) – The algorithm iterates through the input array, calculating the beauty of each element based on its neighbors. It determines the smallest number before the current element and the largest number after it, but it doesn't store these numbers or indices in any auxiliary data structures. Only a few constant space variables are used to store the current element's beauty and the total beauty sum. Therefore, the auxiliary space used is constant, independent of the input size N.

Optimal Solution

Approach

The efficient approach avoids recalculating the smallest and largest values for each element. Instead, we precompute these values to quickly determine the beauty of each element in the array.

Here's how the algorithm would work step-by-step:

Find the smallest number to the left of each number in the array. Keep track of these smallest numbers.
Find the largest number to the right of each number in the array. Keep track of these largest numbers.
For each number in the array, check if it's bigger than the smallest number to its left and smaller than the largest number to its right.
If it is, then we've found a 'beautiful' number and give it a score of 1. Otherwise, it's not beautiful and gets a score of 0.
Add up all the beauty scores to get the total 'beauty' of the array.

Code Implementation

def sum_of_beauty_in_the_array(number_array):
    array_length = len(number_array)
    left_smallest = [0] * array_length
    right_largest = [0] * array_length
    total_beauty = 0

    left_smallest[0] = number_array[0]
    for index in range(1, array_length):
        left_smallest[index] = min(left_smallest[index - 1], number_array[index])

    right_largest[array_length - 1] = number_array[array_length - 1]
    for index in range(array_length - 2, -1, -1):
        right_largest[index] = max(right_largest[index + 1], number_array[index])

    # Exclude edge elements as they cannot be 'beautiful'
    for index in range(1, array_length - 1):
        if number_array[index] > left_smallest[index - 1] and \
           number_array[index] < right_largest[index + 1]:
            # Checks if the current number is a 'beautiful' number
            total_beauty += 2
        elif number_array[index] > left_smallest[index - 1] or \
             number_array[index] < right_largest[index + 1]:
            # Award 1 point if either condition is met
            total_beauty += 1

    return total_beauty

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the array three times. First, it iterates once to find the smallest number to the left of each element. Second, it iterates once to find the largest number to the right of each element. Finally, it iterates once to calculate the beauty values based on the precomputed smallest and largest values. Each of these iterations is linearly proportional to the input size n. Therefore the overall time complexity is O(n).

Space Complexity

O(N) – The algorithm precomputes two arrays: one to store the smallest number to the left of each element and another to store the largest number to the right of each element. Both these arrays have the same size as the input array, which is N. Therefore, the auxiliary space required is proportional to the size of the input array, N, leading to O(N) space complexity.

Edge Cases

Case	How to Handle
Empty array	Return 0 since an empty array has no beauty.
Array with less than 3 elements	Return 0, as at least three elements are needed to assess beauty.
Array with all identical elements	The beauty values will either be all 0s (if the middle element is not strictly between the min/max) or all 1s (if the middle elements are also min/max), handled correctly by the conditions.
Array with extremely large or small numbers (potential integer overflow)	Use a data type with sufficient range (e.g., long) to prevent integer overflow during comparisons or calculations of min/max.
Array with all elements in strictly increasing order	The last element will have beauty 0, other elements will depend on the algorithm's definition of beauty.
Array with all elements in strictly decreasing order	The first element will have beauty 0, other elements will depend on the algorithm's definition of beauty.
Array with negative numbers, zeros, and positive numbers	The solution should correctly compare numbers regardless of their sign, ensuring the beauty is determined by relative magnitude.
Large array size and potentially inefficient prefix min/max calculations	Utilize efficient prefix min/max calculation using dynamic programming to avoid redundant computations and ensure scalability.

Empty array

How to Handle:

Return 0 since an empty array has no beauty.

Array with less than 3 elements

How to Handle:

Return 0, as at least three elements are needed to assess beauty.

Array with all identical elements

How to Handle:

The beauty values will either be all 0s (if the middle element is not strictly between the min/max) or all 1s (if the middle elements are also min/max), handled correctly by the conditions.

Array with extremely large or small numbers (potential integer overflow)

How to Handle:

Use a data type with sufficient range (e.g., long) to prevent integer overflow during comparisons or calculations of min/max.

Array with all elements in strictly increasing order

How to Handle:

The last element will have beauty 0, other elements will depend on the algorithm's definition of beauty.

Array with all elements in strictly decreasing order

How to Handle:

The first element will have beauty 0, other elements will depend on the algorithm's definition of beauty.

Array with negative numbers, zeros, and positive numbers

How to Handle:

The solution should correctly compare numbers regardless of their sign, ensuring the beauty is determined by relative magnitude.

Large array size and potentially inefficient prefix min/max calculations

How to Handle:

Utilize efficient prefix min/max calculation using dynamic programming to avoid redundant computations and ensure scalability.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for the numbers in the array? Can they be negative?
What is the maximum size of the array, and should I be concerned about potential integer overflow issues when calculating the sum?
What should I return if the array is empty or has fewer than three elements?
Are duplicate values allowed in the array, and if so, how do they affect the definition of 'beauty'?
Could you provide a few examples of the array and the expected beauty sum to clarify the problem definition?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Look at the very first number in the list.
Find the smallest number among all the numbers that come before it.
Find the largest number among all the numbers that come after it.
Decide how 'beautiful' the first number is based on these smallest and largest neighboring values according to the beauty rules.
Write down how beautiful the first number is.
Repeat this process for the second number in the list, then the third, and so on, until you've looked at every number.
Finally, add up all the beauty scores you wrote down to get the total beauty.

Code Implementation

def sum_of_beauty_brute_force(numbers):
    total_beauty = 0
    list_length = len(numbers)

    for current_index in range(list_length):
        current_number = numbers[current_index]

        # Find the maximum number to the left
        maximum_left = -1
        for left_index in range(current_index):
            maximum_left = max(maximum_left, numbers[left_index])

        # Find the minimum number to the right
        minimum_right = 100001  
        for right_index in range(current_index + 1, list_length):
            minimum_right = min(minimum_right, numbers[right_index])

        beauty_value = 0
        # Determine beauty value according to the conditions
        if maximum_left < current_number < minimum_right:
            beauty_value = 1
        elif current_number > maximum_left and current_number > minimum_right:
            beauty_value = 0

        total_beauty += beauty_value

    return total_beauty

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

The efficient approach avoids recalculating the smallest and largest values for each element. Instead, we precompute these values to quickly determine the beauty of each element in the array.

Here's how the algorithm would work step-by-step:

Find the smallest number to the left of each number in the array. Keep track of these smallest numbers.
Find the largest number to the right of each number in the array. Keep track of these largest numbers.
For each number in the array, check if it's bigger than the smallest number to its left and smaller than the largest number to its right.
If it is, then we've found a 'beautiful' number and give it a score of 1. Otherwise, it's not beautiful and gets a score of 0.
Add up all the beauty scores to get the total 'beauty' of the array.

Code Implementation

def sum_of_beauty_in_the_array(number_array):
    array_length = len(number_array)
    left_smallest = [0] * array_length
    right_largest = [0] * array_length
    total_beauty = 0

    left_smallest[0] = number_array[0]
    for index in range(1, array_length):
        left_smallest[index] = min(left_smallest[index - 1], number_array[index])

    right_largest[array_length - 1] = number_array[array_length - 1]
    for index in range(array_length - 2, -1, -1):
        right_largest[index] = max(right_largest[index + 1], number_array[index])

    # Exclude edge elements as they cannot be 'beautiful'
    for index in range(1, array_length - 1):
        if number_array[index] > left_smallest[index - 1] and \
           number_array[index] < right_largest[index + 1]:
            # Checks if the current number is a 'beautiful' number
            total_beauty += 2
        elif number_array[index] > left_smallest[index - 1] or \
             number_array[index] < right_largest[index + 1]:
            # Award 1 point if either condition is met
            total_beauty += 1

    return total_beauty

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty array	Return 0 since an empty array has no beauty.
Array with less than 3 elements	Return 0, as at least three elements are needed to assess beauty.
Array with all identical elements	The beauty values will either be all 0s (if the middle element is not strictly between the min/max) or all 1s (if the middle elements are also min/max), handled correctly by the conditions.
Array with extremely large or small numbers (potential integer overflow)	Use a data type with sufficient range (e.g., long) to prevent integer overflow during comparisons or calculations of min/max.
Array with all elements in strictly increasing order	The last element will have beauty 0, other elements will depend on the algorithm's definition of beauty.
Array with all elements in strictly decreasing order	The first element will have beauty 0, other elements will depend on the algorithm's definition of beauty.
Array with negative numbers, zeros, and positive numbers	The solution should correctly compare numbers regardless of their sign, ensuring the beauty is determined by relative magnitude.
Large array size and potentially inefficient prefix min/max calculations	Utilize efficient prefix min/max calculation using dynamic programming to avoid redundant computations and ensure scalability.

Empty array

How to Handle:

Return 0 since an empty array has no beauty.

Array with less than 3 elements

How to Handle:

Return 0, as at least three elements are needed to assess beauty.

Array with all identical elements

How to Handle:

The beauty values will either be all 0s (if the middle element is not strictly between the min/max) or all 1s (if the middle elements are also min/max), handled correctly by the conditions.

Array with extremely large or small numbers (potential integer overflow)

How to Handle:

Use a data type with sufficient range (e.g., long) to prevent integer overflow during comparisons or calculations of min/max.

Array with all elements in strictly increasing order

How to Handle:

The last element will have beauty 0, other elements will depend on the algorithm's definition of beauty.

Array with all elements in strictly decreasing order

How to Handle:

The first element will have beauty 0, other elements will depend on the algorithm's definition of beauty.

Array with negative numbers, zeros, and positive numbers

How to Handle:

The solution should correctly compare numbers regardless of their sign, ensuring the beauty is determined by relative magnitude.

Large array size and potentially inefficient prefix min/max calculations

How to Handle:

Utilize efficient prefix min/max calculation using dynamic programming to avoid redundant computations and ensure scalability.