Get Minimal Cost
Updated
Problem statement
An online retailer offers products in n different dimensions as specified in the array dimensions. The category supervisor notices that several dimensions are redundant and do not offer a favorable customer experience. To optimize the available stock, the product should be offered in unique dimensions. The dimension of the i-th product, dimensions[i], can be augmented by one unit for a fee given in the adjustmentCosts array, adjustmentCosts[i]. A dimension can be augmented any number of times (the fee is paid for each unit), and a dimension never decreases. Indices are 0-based.
Determine the minimal total fee required to ensure that all product dimensions are unique.
Function
getMinimalCost(dimensions: int[], adjustmentCosts: int[]) → long
Complete the function getMinimalCost in the editor.
getMinimalCost has the following parameters:
int dimensions[n]: the dimension of each productint adjustmentCosts[n]: the fee for augmenting each product by one unit
Returns
long: the minimal total fee to make all dimensions unique
Examples
Example 1
dimensions = [3, 7, 9, 7, 8]adjustmentCosts = [5, 2, 5, 7, 5]return = 6Indices are 0-based. Indices 1 and 3 both have dimension 7, so one of them must grow. Dimensions 8 and 9 are already taken, so growing index 1 (fee 2 per unit) to 10 costs 3 * 2 = 6 and gives [3, 10, 9, 7, 8], which are all different. Changing only one product means moving one of the two 7s past 8 and 9, and index 1 is the cheaper of the two. Changing two or more products costs at least 2 + 5 = 7, because every product other than index 1 has a fee of at least 5. The answer is 6.
Example 2
dimensions = [3, 3, 4, 5]adjustmentCosts = [5, 2, 2, 1]return = 5Indices are 0-based. Grow index 1 (fee 2) from 3 to 5 for 2 * 2 = 4, then grow index 3 (fee 1) from 5 to 6 for 1: the dimensions become [3, 5, 4, 6] for a total of 5. Growing index 1 to 4 instead, then index 2 from 4 to 5 and index 3 from 5 to 6, also costs 2 + 2 + 1 = 5, and growing it straight to 6 costs 6. Growing index 0 (fee 5) instead costs at least 6 in total, because its first unit alone costs 5 and lands on dimension 4, which is taken. The answer is 5.
Example 3
dimensions = [2, 3, 3, 2]adjustmentCosts = [2, 4, 5, 1]return = 7Indices are 0-based. Both 2s (indices 0 and 3) and both 3s (indices 1 and 2) clash, so one product of each value must grow. Grow index 1 (fee 4) from 3 to 4 for 4, and grow index 3 (fee 1) from 2 to 5 for 3 * 1 = 3: the dimensions become [2, 4, 3, 5] for a total of 7. No cheaper way exists. A 3 always costs at least 4 to move, since both 3s have fees of 4 or more. If exactly one 3 and one 2 move and the 3 stops at 4, then 2, 3 and 4 are all taken, so the moved 2 must reach 5 or more, which costs at least 3 more. A 3 that goes to 5 or higher alone costs at least 2 * 4 = 8. Moving both 3s costs at least 4 + 5 = 9, and moving both 2s plus a 3 costs at least 1 + 2 + 4 = 7. The answer is 7.
Constraints
1 <= n <= 2 * 10^5, wherenis the length of bothdimensionsandadjustmentCosts1 <= dimensions[i] <= 10^91 <= adjustmentCosts[i] <= 10^4
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
- Maximum Easy Tasks After RearrangingIBM · OAIBM interview questions
- Minimum Cost K-Capable ModelsMicrosoft · OAMicrosoft interview questions
- Maximum Distinct Values After Unit AdjustmentsBirla Pivot · OA
- Maximize Revenue from Decreasing InventoryChubb · OAChubb interview questions
- Minimum Distinct Prefix CostGoldman Sachs · OAGoldman Sachs interview questions
- Maximize Minimum Deployment DifficultyJP Morgan Chase · OAJP Morgan Chase interview questions
- Latest Arrival to Catch a BusAutodesk · OAAutodesk interview questions
- EV Charging Cost OptimizationTata Consultancy Services · OATata Consultancy Services interview questions
- Maximize Workday EarningsCitadel · OA · PHONE SCREEN · ONSITE INTERVIEWCitadel interview questions
- Minimum Removals to Balance ArraySalesforce · OASalesforce interview questions