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.
Example 1:
Input: arr = [1, 2, 3, 2, 4, 5], pairs = [[0, 1], [3, 4], [0, 0], [3, 4]]
Output: 9
Explanation: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.
🥑
input:
output: