Minimize Variation
Updated
Problem statement
You are given an array productSize of n numbers. The value productSize[i] is the size of product i. You can put the products in any order you like.
For an order, variation[i] is the largest size minus the smallest size among the first i + 1 products in that order. The total variation is variation[0] + variation[1] + ... + variation[n - 1].
Return the smallest total variation you can get by choosing the order.
For example, if the order of the sizes is [1, 2, 4], then variation = [0, 1, 3] and the total variation is 4.
Function
minimizeVariation(productSize: int[]) → long Complete the function minimizeVariation in the editor.
minimizeVariation has the following parameter:
int[] productSize: the size of each product
Returns long: the smallest total variation
Examples
Example 1
productSize = [3, 1, 2]return = 3Put the products in the order [2, 3, 1]. The first product alone gives variation[0] = 2 - 2 = 0. The first two give variation[1] = 3 - 2 = 1. All three give variation[2] = 3 - 1 = 2. The total is 0 + 1 + 2 = 3. No order gives less, so the answer is 3.
Example 2
productSize = [6, 1, 4, 2]return = 9Put the products in the order [1, 2, 4, 6]. Then variation[0] = 1 - 1 = 0, variation[1] = 2 - 1 = 1, variation[2] = 4 - 1 = 3 and variation[3] = 6 - 1 = 5. The total is 0 + 1 + 3 + 5 = 9. No order gives less, so the answer is 9.
Example 3
productSize = [4, 5, 4, 2, 6, 1, 1]return = 16Put the products in the order [1, 1, 2, 4, 4, 5, 6]. Then the variations are 0, 0, 1, 3, 3, 4 and 5. For example, variation[3] = 4 - 1 = 3 and variation[6] = 6 - 1 = 5. The total is 0 + 0 + 1 + 3 + 3 + 4 + 5 = 16. No order gives less, so the answer is 16.
Example 4
productSize = [3, 1, 3, 3, 6, 6]return = 11Put the products in the order [3, 3, 3, 6, 6, 1]. Then the variations are 0, 0, 0, 3, 3 and 5. For example, variation[5] = 6 - 1 = 5. The total is 0 + 0 + 0 + 3 + 3 + 5 = 11. No order gives less, so the answer is 11.
Constraints
1 <= n <= 2000, wherenis the length ofproductSize1 <= productSize[i] <= 10^9
More Amazon interview questions
- Get Smallest Base SegmentOA · Seen Nov 2026
- Number of IslandsPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Minimum Cost of Left and Right PropagationOA · Seen Nov 2026
- Minimum Grid InconvenienceOA · Seen Nov 2026
- 3SumPHONE SCREEN · Seen Nov 2026
- Circular Primes Below a LimitPHONE SCREEN · Seen Nov 2026
- Maximize K-Element AND with an Increment BudgetOA · Seen Nov 2026
- Maximize Shipment Order by Sorting One WindowOA · Seen Nov 2026
- Cheapest Flights Within K StopsPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Course SchedulePHONE SCREEN · ONSITE INTERVIEW · 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
Amazon interview experiences
- Amazon SWE OA with AI Coding: 1 Experience
- Amazon SWE Intern Phone Screen Interview Experience: 1 Experience
- Amazon New Grad SDE I OA and Virtual Onsite: 1 Experience
- Amazon BIE Intern SQL and Interview Questions: 17 Experiences
- Amazon Experienced SWE AI-Assisted Debugging OA: 1 Experience
- Amazon SDE II (L5) Interview Questions: 5 Experiences