Amazon OA || Question number 2

If you are reading this I hope you have came across my another post regarding question 1 in Amazon OA.

At first glance my second question looks bit easier, i thought yes it would be a cake walk, a normal sorting + sliding window might help but i failed like 13 times.

Thanks to atcoder for the problem cause it was a variant of some contest at atcoder that, i will not say you the topic cause i want you feel the exact OA pattern.

Question :

🧮 Problem: Minimize Total Variation

You are given an array productSize of n integers.

You want to rearrange the elements of the array in some order, and define the total variation of the arrangement as:

total variation = sum_{i=1}^{n} ( max_{1 <= j <= i} a_j - min_{1 <= j <= i} a_j )

Where:

• a_1, a_2, ..., a_n is your chosen permutation of productSize.
• For every prefix a[1..i], you compute the max and min, and take their difference.

Total Variation = ∑ᵢ₌₁ⁿ ( max₁≤ⱼ≤ᵢ aⱼ − min₁≤ⱼ≤ᵢ aⱼ )

i wrote again for your understanding. it is same as above Total variation.

Your task is to compute the minimum possible total variation over all possible rearrangements of the input array.

🔧 Input

• An integer n — the number of elements.
• An array productSize of n integers.

Constraints:

• 1 <= n <= 2000
• 1 <= productSize[i] <= 10^4

🎯 Output

• A single integer — the minimum total variation achievable by some rearrangement.

🧪 Example

Input: 4 6 1 4 2

Output: 9

Explanation: One optimal arrangement is: [1, 2, 4, 6].

• Prefixes:
  • [1]: max-min = 0
  • [1,2]: 2-1 = 1
  • [1,2,4]: 4-1 = 3
  • [1,2,4,6]: 6-1 = 5
  • Total = 0 + 1 + 3 + 5 = 9

✅ Goal

Implement a function:

long minimizeVariation(vector<int> productSize);

which returns the minimum total variation over all rearrangements.

Another input from my side:-

Input: 6 10 1 3 8 2 9 Explanation:

Try the optimal order: [1, 2, 3, 8, 9, 10]

Compute prefix max/min differences:

Prefix [1]: 0

[1,2]: 2−1 = 1

[1,2,3]: 3−1 = 2

[1,2,3,8]: 8−1 = 7

[1,2,3,8,9]: 9−1 = 8

[1,2,3,8,9,10]: 10−1 = 9

Total variation = 0 + 1 + 2 + 7 + 8 + 9 = 27

Expected Output: 27

Don't try sorting + sliding window the only given testcases will pass for that

Even no AI can solve it. I tried sorting + sliding window like 13 times it failed don't waste your time it's just a hint.

I belive the problem is around 1800+ rating on codefoces.

Thanks to god i hit the solution at last and gave a try on that approach but i was not hoping it was the correct one, but it passed all testcases on last 2 min.

I think it was most hardest OA of my life.

AMAZON literally plays easy for some and hard a** for some :) Just kidding.

Please post your solutions i will let you know regarding your approach.

Please upvote too so that it can reach to maximum.

Ansuman Das NIT RKL 2025.

Happy Leetcoding :)