How should I practice Find Sum of Beauties?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Amazon online assessment problems in FastPrep.

Is Find Sum of Beauties associated with Amazon?

FastPrep tags this as a Amazon coding interview or online assessment practice problem when the problem catalog has that company context.

FastPrep

Problem · Array

Find Sum of Beauties

● MediumAmazonNEW GRADOA

See Amazon hiring insights

Amazon's development team is working on a feature for a new product, a smart array processor. A user has provided an integer array called arr of size n and a 2-dimensional array called pairs of size m x 2. Each pair in pairs represents the starting and ending indices of a subarray within arr.

For each subarray of arr represented by the array pairs, the goal is to merge and concatenate them into a new array called beautiful.

The beauty of an element at index i in arr is defined as follows: if the index i has not contributed to the formation of the array beautiful, the beauty is the count of integers in beautiful that have a value strictly smaller than arr[i]. If the index i has contributed to the formation of the array beautiful, its beauty is 0.

Find the sum of the beauties of all the elements in the array arr.

Examples

01 · Example 1

arr = [1, 2, 3, 2, 4, 5]
pairs = [[0, 1], [3, 4], [0, 0], [3, 4]]
return = 9

Note 📝 - Not entirely sure about the explanation and the example output of 9. If you find any mistakes, pls feel free to lmk! I am more than happy to fix it!! I will add more info once I find more clarity / references of this problem! Extract the subarrays based on the pairs and concatenate them into the beautiful array: From pair [0, 1], extract subarray arr[0:2] = [1, 2]. From pair [3, 4], extract subarray arr[3:5] = [2, 4]. From pair [0, 0], extract subarray arr[0:1] = [1]. From pair [3, 4] (again), extract subarray arr[3:5] = [2, 4]. Now, concatenate all these subarrays to form beautiful: beautiful = [1, 2, 2, 4, 1, 2, 4] Identify the indices of the elements in arr that contribute to beautiful: From pair [0, 1], indices 0 and 1 contribute. From pair [3, 4], indices 3 and 4 contribute. From pair [0, 0], index 0 contributes. From pair [3, 4] again, indices 3 and 4 contribute. Therefore, the contributing indices are: 0, 1, 3, 4. These elements from arr have already been included in beautiful. Calculate the beauty of each element in arr: Element at index 0 (arr[0] = 1): Already included in beautiful, so its beauty is 0. Element at index 1 (arr[1] = 2): Already included in beautiful, so its beauty is 0. Element at index 2 (arr[2] = 3): Not included in beautiful. The beauty of arr[2] is the count of elements in beautiful that are strictly smaller than 3. In beautiful = [1, 2, 2, 4, 1, 2, 4], we have 3 elements smaller than 3 (the 1, 2, 2). Therefore, its beauty is 3. Element at index 3 (arr[3] = 2): Already included in beautiful, so its beauty is 0. Element at index 4 (arr[4] = 4): Already included in beautiful, so its beauty is 0. Element at index 5 (arr[5] = 5): Not included in beautiful. The beauty of arr[5] is the count of elements in beautiful that are strictly smaller than 5. In beautiful = [1, 2, 2, 4, 1, 2, 4], we have 6 elements smaller than 5 (all except 5 itself). Therefore, its beauty is 6. Sum the beauties of all elements: Beauty of arr[0] = 0 Beauty of arr[1] = 0 Beauty of arr[2] = 3 Beauty of arr[3] = 0 Beauty of arr[4] = 0 Beauty of arr[5] = 6 Total beauty = 0 + 0 + 3 + 0 + 0 + 6 = 9. Final Output: The sum of beauties is 9.

Constraints

🥑