Compute Beauty of Array Products
Updated
Problem statement
The Amazon distribution center consists of arrays of products, each possessing unique attributes. The task at hand is to compute the beauty of these product arrays, with the goal of achieving an efficient selection process.
More specifically, there are arrays of products, and each array corresponds to a list of attributes. The beauty of a subarray B = [products[l], products[l+1], ..., products[r]] is quantified by counting the indices i that satisfy these conditions:
- l ≤ i ≤ r
- for every index j such that i < j ≤ r, products[i] > products[j]
An array B is a subarray of an array A if B can be obtained from A by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end. In particular, an array is a subarray of itself.
The beautiness of the entire array of products is determined by the sum of beauty values across all subarrays of a given size k.
Given an array products of size n and an integer k. Compute the total beautiness of the array of products.
Function
computeBeauty(products: int[], k: int) → int Complete the function computeBeauty in the editor.
computeBeauty has the following parameters:
int[] products: an array of integers representing the productsint k: the size of the subarray
Returns int: the total beautiness of the array of products
Examples
Example 1
products = [3, 6, 2, 9, 4, 1]k = 3return = 8
There are 4 windows of size 3.
- [3, 6, 2]: the values 6 and 2 are greater than everything after them, so the beauty is 2.
- [6, 2, 9]: only 9 counts, so the beauty is 1.
- [2, 9, 4]: the values 9 and 4 count, so the beauty is 2.
- [9, 4, 1]: all three values count, so the beauty is 3.
So the beauty of the array is 2 + 1 + 2 + 3 = 8.
Constraints
1 <= k <= n = products.length <= 5 * 10^41 <= products[i] <= 10^9
More Amazon interview questions
- LRU Cache for Query ResultsPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Maximal SquareONSITE INTERVIEW · Seen Nov 2026
- Serialize and Deserialize a Binary TreeONSITE INTERVIEW · Seen Nov 2026
- Course SchedulePHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Course Schedule IIPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Diagonal Traversal of a Binary TreeONSITE INTERVIEW · Seen Nov 2026
- Minimum Time to Spread Through a GridPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Consistent-Hash Packet RouterPHONE SCREEN · Seen Nov 2026
- Count Connected ComponentsPHONE SCREEN · Seen Nov 2026
- Maximize K-Element AND with an Increment BudgetOA · Seen Nov 2026
Similar questions at other companies
- Closest Pair Among the Latest K ReadingsRippling · ONSITE INTERVIEWRippling interview questions
- Sliding Window MedianAuxoAI · OA
- Distribute Elements Into Two Arrays IIRubrik · OARubrik interview questions
- Incident MonitorStripe · OAStripe interview questions
- Count Pairs with K Divisible Values in the IntervalChubb · OAChubb interview questions
- Fastest Average Speed over a Rolling KilometerOptiver · OAOptiver interview questions
- Most Items Within Budget from a Start IndexHudson River Trading · OAHudson River Trading interview questions
- Binary Sorting Rounds After FlipsVisa · OAVisa interview questions
- Longest Subarray with Sum at Most KGoogle · OAGoogle interview questions
- Minimum Cars to RemoveMicrosoft · OAMicrosoft interview questions